快速幂取余算法
· 阅读需 2 分钟
计算a的b次方模m:
暴力的做法是将a乘b次,最后对m取模。不过,这样可能导致溢出,时间复杂度也很高。
现在考虑,求3的10次方,最少需要做几次乘法运算。
很显然,当计算完3×3后,可以将结果“缓存”起来,后面计算3×3就不需要计算了,直接用“缓存”的结果即可。再之后也是利用同样的思路进行计算,这样可以减少需要进行的乘法计算的次数。显然,求3的10次方,最少需要做4次乘法运算。
设 为计算 最少需要做的乘法运算次数,显然:
其中, 为正整数。
对于求大数余数的问题,同余模定理是很常用的:
由上面的思路,就可以得到快速幂取余算法:
int qmi(LL a, int b, int m) {
LL r = 1 % m;
while (b) {
if (b & 1) r = r * a % m;
a = a * a % m;
b >>= 1;
}
return r;
}
按照这样的思路,由于乘法可以看成是多次加法,所以,也可以利用快速幂取余算法的思想计算两个大整数相乘取余。