快速幂取余算法
文章目录
计算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 $$
由上面的思路,就可以得到快速幂取余算法:
|
|
按照这样的思路,由于乘法可以看成是多次加法,所以,也可以利用快速幂取余算法的思想计算两个大整数相乘取余。