快速幂

思路

快速幂是在O(logn)的时间下计算a^n的技巧，常规的计算需要O(n)

幂运算中，同底数相乘，底数不变，指数相加，利用这一点，我们可以将幂运算拆分如下：

$$a^n = a^x+a^y+a^z+......$$

而将指数拆分的法则就是位运算：将指数以二进制分割成多个小任务，例如：9的二进制为1001，即：

$$a^9=a^8*a^1$$

代码

基于上述思路，快速幂的代码实现如下

long long quickPow(int a,int n){
    long long result = 1;
    while(n>0){
        // 如果n的二进制在某一位为1，则计算对应的幂
        if(n&1) result *= a;
        // 更新a，为下一次计算作准备
        a *= a;
        // 更新n，寻找下一个计算小任务
        n >>= 1;
    }
    return result;
}

进一步的，取模运算不影响乘法运算，对于某些需要进行取模的题目，可以有：

$$(a*b)\mod{m} = (a\mod{m})*(b\mod{m})\mod{m}$$

long long quickPow(int a,int n,int m){
    a %= m;
    long long result = 1;
    while(n>0){
        if(n&1) result *= a%m;
        // 这里更新的结果是(a^x)%m
        a *= (a%m);
        n >>= 1;
    }
    return result;
}