题目描述
求 a 的 b 次方对 p 取模的值。0≤a,b≤1e9,1≤p≤1e9
输入:
三个整数 a,b,p ,在同一行用空格隔开。
输出:
输出一个整数,表示a^b mod p的值。
样例
输入:
3 2 7
输出:
2
算法1
(暴力模拟) $O(b)$
思路:直接使用for循环,做b次乘法。然而b<=1e9,超时无疑
C++ 代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a,b,p,ans=1;
int main(){
cin>>a>>b>>p;
for(ll i=1;i<=b;i++)
ans=ans*a%p;
cout<<ans;
return 0;
}
算法2
(快速幂) $O(log b)$
思路:考虑到二进制拆分,可将b拆成不超过log b向上取整位。
可以存储一个变量,维护第k位的因数(比如,第一位就是1,第二位是a%p
将所有二进制位是1的加起来,模p,就是答案。
C++ 代码
#include<bits/stdc++.h>
using namespace std;
int a,b,p,ans;
int main(){
cin>>a>>b>>p;
ans=1%p;
for(;b;b>>=1){
if(b&1)ans=(long long)ans*a%p;
a=(long long)a*a%p;
}
cout<<ans;
return 0;
}