快速幂

时间复杂度为 O(logN)，比朴素的方法快很多

核心思想是减少乘法的次数

比如：

朴素方法：需要乘9次

快速幂： = = = = ，故我们只需要用算出，用算出，奇数次方只需乘以，总共需要乘以4次，当指数越大时，快速幂就越优

1. 递归版（慢于迭代）

思想：拆分

1. 当指数n为偶数： =

2. 当指数n为奇数： = *

int fastpow1(int a,int n){
    if(n == 0)
        return 1;
    if(n == 1)
        return a;
    //注意：这里必须缓存下来，这样才保证只算了一次，否则多次计算，又变回了朴素方法
    long long int t = fastpow1(a, n / 2);
    if((n & 1) == 0){
        //偶数
        return t * t % MOD;
    }else{
        //奇数
        return t * t % MOD * a % MOD;
    }
}

2. 迭代版（建议使用）

11的二进制码: 1011

=

​ =

​ = （第三行）

​ =

对于每一项（第三行）：

而 = 的平方

而 = 的平方

而 = 的平方

......依此类推

对于11的二进制码：1011

最后乘积的结果，

而对于每一项，

那么我们需要检测每个bit位，可以使用>>，然后与1&，即可判断

int fastpow2(int a,int n){
    long long int t = a;
    int res = 1;
    //当n == 0时，说明所有1的项都乘了，即得到了结果
    while(n){
        //检查最低为是否为1，为1则乘以该项
        if(n & 1){
            res = res * t % MOD;
        }
        //t对应 a^(2^i)，平方使得i++，即得到下一项
        t = t * t % MOD;
        //右移1位，用以检测
        n >>= 1;
    }
    return res;
}