快速幂 | 洛灵酱的小窝

洛灵酱的小窝

闻道有先后,术业有专攻。

0%

快速幂

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

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

例如:

a10=a(1010)2=a123+022+121+120=a123a121a^{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}

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

下面请看代码实现:

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