快速幂算法通常用在求 A^B%C 的时候,因为当B足够大的时候 n与logn 的差距就非常巨大了。并且B十分巨大的时候通常我们已经存不下这个数值了。所以一般要对一个C 取模。
如果B十分大,那么有可能会产生a的2^n次方时比 long long 还大。这时就有可能输出负数也就是溢出了。所以这个时候可以用加法来模拟乘法,并且每次相加都对C取模,这样就不会溢出了。
加法模拟乘法:
列如:求7*5:
n=5的二进制是101,
此时n为奇数,则ans=ans+tmp;tmp=tmp+tmp;n右移一位;(ans=0+7,tmp=7*2)
此时n为偶数,则直接tmp=tmp+tmp;n右移一位;(ans=7,tmp=7*4)
此时n为奇数,则ans=ans+tmp;tmp=tmp+tmp;n右移一位;(ans=7+7*4,tmp=7*8);
快速幂算法:https://blog.csdn.net/wuyileiju__/article/details/81056150
此时n为奇数,则ans=ans+tmp;tmp=tmp+tmp;n右移一位;(ans=0+7,tmp=7*2)
此时n为偶数,则直接tmp=tmp+tmp;n右移一位;(ans=7,tmp=7*4)
此时n为奇数,则ans=ans+tmp;tmp=tmp+tmp;n右移一位;(ans=7+7*4,tmp=7*8);
快速幂算法:https://blog.csdn.net/wuyileiju__/article/details/81056150
列如求5^19:
n=19的二进制是10011,
此时n为奇数,则ans=ans*tmp;tmp=tmp*tmp;n右移一位;(ans=1*5,tmp=5*5=25)
此时n为奇数,则ans=ans*tmp;tmp=tmp*tmp;n右移一位;(ans=5*25,tmp=25*25)
此时n为偶数,则直接tmp=tmp*tmp;n右移一位;(ans=125,tmp=625*625)
此时n为偶数,则直接tmp=tmp*tmp;n右移一位;(ans=125,tmp=390625*390625)
此时n为奇数,则ans=ans*tmp;tmp=tmp*tmp;n右移一位;(ans=125*390625*390625,tmp=(390625*390625)^2);
此时n为奇数,则ans=ans*tmp;tmp=tmp*tmp;n右移一位;(ans=1*5,tmp=5*5=25)
此时n为奇数,则ans=ans*tmp;tmp=tmp*tmp;n右移一位;(ans=5*25,tmp=25*25)
此时n为偶数,则直接tmp=tmp*tmp;n右移一位;(ans=125,tmp=625*625)
此时n为偶数,则直接tmp=tmp*tmp;n右移一位;(ans=125,tmp=390625*390625)
此时n为奇数,则ans=ans*tmp;tmp=tmp*tmp;n右移一位;(ans=125*390625*390625,tmp=(390625*390625)^2);
模板:
#include<bits/stdc++.h> using namespace std; long long pow_mul(long long a,long long b,long long mod) { long long ans=0; while(b) { if(b&1) ans=(ans+a)%mod; a=(a+a)%mod; b>>=1; } return ans; } long long pow_mod(long long a,long long b,long long mod) { long long ans=1; while(b) { if(b&1) ans=pow_mul(ans,a,mod); a=pow_mul(a,a,mod); b>>=1; } return ans; } int main() { long long t,a,b,p; scanf("%d",&t); while(t--) { scanf("%lld%lld%lld",&a,&b,&p); printf("%lld\n",pow_mod(a,b,p)); } return 0; }