【算法学习笔记】33：快速幂的递归及循环实现

快速幂原理

要计算$a^b$，$a^{b}modp$，可以考虑用折半的方式缩小计算量。

例如要计算$2^{13}$，只要计算$2^6$乘以自己，再乘以一个多出来的2。

而要计算$2^6$，只要计算$2^3$乘以自己。

而要计算$2^3$，只要计算$2^1$乘以自己，再乘以一个多出来的2。

也就是每次把$b$折半下取整，当$b$是偶数时：
$$a^b=a^{\frac{b}{2}}\cdot a^{\frac{b}{2}}$$
当$b$是奇数时只要多乘以一个$a$：
$$a^b=a^{\frac{b}{2}}\cdot a^{\frac{b}{2}}\cdot a$$

如果需要对$p$取模，只要在每一步乘法之后取模就可以了。

例题：AcWing 875. 快速幂

递归实现

从前面的原理很容易得到如下的递归实现。

#include <iostream>using namespace std;typedef unsigned long long ULL;ULL qmi(ULL a, ULL b, ULL p) {if (b == 1) return a % p;ULL res = qmi(a, b >> 1, p);res = res * res % p;if (b & 1) res = res * a % p;return res;
}int main() {int t; cin >> t;while (t -- ) {ULL a, b, p; cin >> a >> b >> p;cout << qmi(a, b, p) << endl;}return 0;
}

循环实现

从前面的原理理解循环实现不直观。可以考虑$b$的二进制表示。例如$b=0b1101$也就是$2^3+2^2+2^0=13$，所以：

$$a^{2^3+2^2+2^0}=a^{2^3}\cdot a^{2^2}\cdot a^{2^0}$$

这正是因为$b$的从低到高0、2、3二进制位置是1导致的。

又因为
$$(a^{2^i}{)}^2=a^{2^{i+1}}$$
因此只需要循环的从最低位（第0位）开始，每次通过把$a$和自己相乘计算一下$a^{2^i}$，只要$b$的相应二进制位置是1，就把这个数乘进res里即可。

#include <iostream>using namespace std;typedef unsigned long long ULL;ULL qmi(ULL a, ULL b, ULL p) {ULL res = 1;while (b) {if (b & 1) res = res * a % p;b >>= 1;a = a * a % p;}return res;
}int main() {int t; cin >> t;while (t -- ) {ULL a, b, p; cin >> a >> b >> p;cout << qmi(a, b, p) << endl;}return 0;
}