快速幂

快速幂用于在 $O(\log n)$ 的速度计算一个数的 $n$ 次幂．

快速幂使用倍增的思想．

对于任意一个指数 $b$，将其用二进制表示，可以拆解为 $2^{a_1} + 2^{a_2} + \cdots + 2^{a_n}$ 的形式，其中 $a_i$ 为互不相同的非负整数．不难得出，设 $b$ 二进制表示中的第 $k$ 位为 1，则所有 $a_i$ 和所有 $k-1$ 对应相等．

根据幂的相关性质可知，$a^b=a^{2^{k_1} + 2^{k_2} + \cdots + 2^{k_n}}=a^{2^{k_1}}\times a^{2^{k_2}}\times \cdots \times a^{2^{k_n}}$，即指数的二进制表示中，所有位数值为 1 的位，记该位的权值为 $p$，答案就是 $\sum_{p_i \in P}a^p$，其中，$P$ 是所有满足要求的 $p$ 的取值．

例如，对于 $a=3$，$b=10$ 的情况，由于 $10_{10}$ 的二进制为 $1010_2$，其中，为 1 的位是右起第 2 位（对应权值为 $2^{2-1}=2$）和右起第四位（对应权值 $2^{4-1}=8$），所以，$P=\{2,8\}$，$3^{10} = 3^2\times 3^8$．

因此，检查 $b$ 二进制中的每一位．并对于权值为 $p$ 的位，通过递推记录当前位的 $a^p$ ，若 $b$ 二进制的该位为 1，则将 $a^p$ 计入答案．如何通过递推记录？只需要在从权值为 $p$ 的一位转移到左边一位时，由于左边一位的权值是 $2p$，将 $a^p$ 平方为 $a^{2p}$ 即可．

可以写出基本流程：

1. 检查 $b$ 二进制右起第一位是否为 1，若是，则将答案乘上 $a$．
2. 将 $b$ 左移一位，露出 $b$ 的二进制右起第二位．
3. 由于 $b$ 左移了一位，所以目前 $b$ 右起第一位的权值翻了倍，需要让 $a$ 平方才能让权值指数也翻倍．
4. 若当前 $b$ 大于等于 1，则回到步骤 1．

核心代码如下：

int exp = b; // 记录目前剩余的指数
int ans = 1; // 记录答案
int now = a; // 记录现在位的权值
while (exp >= 1) {
	if (exp % 2) // 如果当前位是1
		ans *= now; // 就将当前位的权值记录答案
	exp /= 2; // 指数右移一位
	now *= now; // 权值对应增加
}

此外，这道题还要注意取模和开 long long．

标程如下：

#include <bits/stdc++.h>
using namespace std;

int a, b, p;

int main() {
	cin >> a >> b >> p;
	long long exp = b, ans = 1, now = a;
	while (exp >= 1) {
		if (exp % 2)
			(ans *= now) %= p;
		exp /= 2;
		(now *= now) %= p;
	}
	cout << a << "^" << b << " mod " << p << "=" << ans;
	return 0;
}