快速幂的递归写法
typedef long long ll;
ll binaryPow(ll a,ll b,ll m){
if(m==1) return 0;
if(b==0) return 1;
a%=m;
if(b&1) return a*binaryPow(a,b-1,m)%m;
else {
ll mul=binaryPow(a,b/2,m);
return mul*mul%m;
}
}
快速幂的迭代写法
typedef long long ll;
ll binaryPow(ll a,ll b,ll m){
if(m==1) return 0;
ll ans=1%m;
while(b>0){
if(b&1) ans=ans*a%m;
a=a*a%m;
b>>=1;
}
return ans;
}
ps:
- b&1等价于b%2==1
- b>>=1等价于b=b/2
细节注意:
- 如果初始是a有可能大于等于m,那么需要先让a对m取模。
- 如果m为1,可以直接特判为0(因为任何正整数对1取模一定等于0)。