快速幂取模

xiaoxiao2021-02-28  100

在平常的练习中,我们经常需要求a的b次幂模p的结果。这次就专门讲讲这个。

之前,b的规模不是很大。所以我们都是这样做的:

for(int i = 1; i <= b; i++) ans *= a, ans %= p; 然而,当b很大时,如10^9时,这种方法就大大滴超时了。。。

为了搞定b较大时的幂取模运算,在这里提一下快速幂取模的方法。

以27^11为例:

1、将11转化为二进制得:1011

2、则原式可转换为:27^(2^3)*27^(2^1)*27(2^0)......(同底数幂的计算)

但感觉这里的27^(2^n)还是很难算。。。还是先看看代码实现吧。

int h = a; while(b) { if(b & 1) ans *= h, ans %= p; h*= h, h %= p, b >>= 1; }

看到这一小段程序的变量h。它就完美地实现了求a^(2^n)的过程(a^n*a^n=a^(2^n) (n≠0))

转载请注明原文地址: https://www.6miu.com/read-81022.html

最新回复(0)