快速幂

written by oneman233

2019-08-22

算法

基本思想是把$a^b$当中的$b$拆分成二进制，在$log(b)$时间内完成幂次的计算。

qpow(int a,int b) {
    int ret=1;
    while(b) {
        if(b&1) ret=ret*a%mod;
        a=a*a%mod;
        b>>=1
    }
    return ret;
}
res=1,tmp=a;