首页 > itarticle > 快速幂

快速幂

admin 11月 13, 2020 0

求解

快速求解a的b次方。

原理

a的b次方求p的模

把b转化为二进制

如 b=13=8+4+1

pow(a,b)=a^8 a^4 a^1

可以先把a的1次、a的2次，a的4次。。。。预处理出来

再把b转成二进制，如果第i位是1，那么就乘上a的2i次方。

代码


#define M 1000000007
using namespace std;
int (){
    long long a,b,ans=1,base;
    cin>>a>>b;base=a;
    while(b>0){
        if(b&1) ans*=base,ans%=M;
        base*=base;base%=M;
        b>>=1;
    }
    cout<<ans;
    return 0;
}