快速幂取余算法

计算a的b次方模m：

$$ a^b\ %\ m $$

暴力的做法是将a乘b次，最后对m取模。不过，这样可能导致溢出，时间复杂度也很高。

现在考虑，求3的10次方，最少需要做几次乘法运算。

很显然，当计算完3×3后，可以将结果“缓存”起来，后面计算3×3就不需要计算了，直接用“缓存”的结果即可。再之后也是利用同样的思路进行计算，这样可以减少需要进行的乘法计算的次数。显然，求3的10次方，最少需要做4次乘法运算。

设 $ f(b) $ 为计算 $ a^b $ 最少需要做的乘法运算次数，显然:

$$ f(1) = 0, f(2) = 1 \ f(2x) = f(x) + 1 \ f(2x+1) = f(2x) + 1 $$

其中，$ x $ 为正整数。

对于求大数余数的问题，同余模定理是很常用的：

$$ (a + b) % c = (a % c + b % c) % c $$

$$ (a × b) % c = (a % c × b % c) % c $$

由上面的思路，就可以得到快速幂取余算法:

1
2
3
4
5
6
7
8
9

int qmi(int a, int b, int m) {
    int r = 1 % m;
    while (b) {
        if (b & 1) r = r * a % m;
        a = a * a % m;
        b >>= 1;
    }
    return r;
}

按照这样的思路，由于乘法可以看成是多次加法，所以，也可以利用快速幂取余算法的思想计算两个大整数相乘取余。