例题

https://ac.nowcoder.com/acm/contest/392/B?&headNav=acm

这题快速幂和快速乘都包括了

快速幂

应用

相对于正常的O(n)复杂度的求a的n次幂，要快一些，复杂度为O(logn)。
快速幂可以算pow(a, n) % mod;

原理

知道原理的基础上代码好记一些
比如我们要求a ^ b，那么b是可以用二进制表示的，比如a = 2, b = 11，
b的二进制为1011，即b = 2 ^ 0 + 2 ^ 1 + 2 ^ 3
所以a ^ b = a ^ (2 ^ 0 + 2 ^ 1 + 2 ^ 3) = a ^ (2 ^ 0) * a ^ (2 ^ 1) * a ^ (2 ^ 3)
也就是a ^ b = a ^ 1 * a ^ 2 * a ^ 8
即：如果b的二进制形式的第i位为1，结果就乘以a * (2 ^ i)
补充：记得当等于0时，快速幂的返回结果应该返回1！

代码

long long Mode(long long a, long long b, long long mode)
{
    if (b == 0){
        return 1l % p;
    }
    long long sum = 1; // 表示结果
    a = a % mode; // 为了保险先取个模
 
    while (b) { // 等价于b != 0
        if (b & 1) // b的最低位如果为1的话就乘
            sum = (sum * a) % mode;
        b >>= 1;  // 右移，继续判断下一位
        a = (a * a) % mode; 
    // a是拿来记录2的多少次幂的，根据循环次数依次取值为1, 2 , 4, 8, 16
    }
    return sum;
}

快速乘

跟快速幂的原理类似

IMG_0176.PNG
通过二进制的竖式乘法可以看见，当b的第i位是1的时候，最后的结果就会加上 a * (2 ^ i) (a左移相当于a * 2)

代码

long long multiply(long long a, long long b, long long mode){
    long long ans = 0;
    while (b){
        if (b & 1){
            ans = (ans + a) % mode;
        }
        a = (a + a) % mode;
        b >>= 1;
    }
    return ans;
}