快速幂取模代码如下，如有错误，欢迎指正

92 阅读 0 评论 61 点赞

我是靠谱客的博主动人冷风，这篇文章主要介绍快速幂取模代码如下，如有错误，欢迎指正，现在分享给大家，希望可以做个参考。

问题：

求 a的 b 次方对 p 取模的值。

对于较小的数，我们可以用暴力解法，用循环b次的方法来实现，算法复杂度为O(N)，但是对于b比较大的情况，那么这种算法时间复杂度就很大了，因此引出了快速幂的定义：

实例分析：

例如我们要求2^7,首先我们可以将7的2进表示出来

7 = 111；

那么有：

2^1 = 2；

2^2 = 4;

2^4 = 16;

要求2^7，只需要将以上三个数相乘即可，从而简化运算，时间复杂度也变成了O(logN)

代码如下，如有错误，欢迎指正

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
#include <cstdio>
using namespace std;
long long a,b,p;
int main()
{
scanf("%lld%lld%lld",&a,&b,&p);
long long ans = 1%p;
long long res = a,l
= b;
for(;l;l>>=1,res = (res*res)%p)
{
if(l&1)
{
ans = (ans*res)%p;
}
}
printf("%lldn",ans);
return 0;
}