今天学了倍增,终于把非递归快速幂看懂了。

还是把$a^n$拆分成二进制形式。

例如:
$$
a^{10} = a^{(1010) _ 2} = a^{1 * 2^3 + 0 * 2^2 + 1 * 2^1 + 1 * 2^0} = a^{1 * 2^3} * a^{1 * 2^1}
$$

我们可以通过倍增的方法先计算$\mod p$意义下的$a^1$,$a^2$,$a^4$,$a^8$,$a^{16}$,$a^{32}$,再把它们根据$b$的二进制拆分乘起来。

下面请看代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
// a ^ b % p
int quick_pow(int a, int b, int p) {
int t = a; // 倍增(a^1 a^2 a^3 ...)
int ans = 1;
while (b > 0) {
if (b & 1) // 二进制最后一位是1
ans = (ans * t) % p;
t = (t * t) % p;
b >>= 1; // 计算下一个二进制的值
}
return ans;
}

评论