快速幂取余算法

计算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 $$

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

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;
}

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

算法

上一篇 并查集初步
下一篇 简单又不简单的二分法

添加新评论

*
*