传送门：P1226 【模板】快速幂
更佳的阅读体验：洛谷 P1226 题解
算法介绍
现在你需要计算 $a^n \bmod p$（即 $\underbrace{a \times a \times a \times \cdots \times a}_{n \text{ 个 } a} \ \bmod p$）。
当 $n \le 10$ 时，你知道可以手写 if 语句，通过条件判断直接输出 $n$ 为不同值时对应的答案。
当 $n \le 10^6$ 时，你知道可以通过循环语句来计算最后的答案。
那么，当 $n \le 10^9$ 呢？显然朴素的循环已经无法满足我们对程序的效率的要求，我们需要一个更快的算法。
陷入迷茫时，不妨回顾一下幂运算的基本性质：
- 幂的乘方，底数不变，指数相乘：$(a^m)^n = a^{m \times n}$。
- 同底数幂相乘，底数不变，指数相加：$a^m \times a^n = a^{m + n}$。
因此，我们有：
$$ \begin{align} & a^{m \times 2} = (a^{m})^2 \tag{1} \\ & a^{m + 1} = a^m \times a \tag{2} \end{align} $$
如果 $n$ 是偶数，我们就可以将 $m = \dfrac{n}{2}$ 代入 $(1)$ 式。得到：
$$ a^n = (a^{\tfrac{n}{2}})^2 $$
那么如果 $n$ 是奇数呢？如果可以把 $n$ 变为偶数，就有办法像上面那样继续代入了。我们发现 $n - 1$ 就是一个偶数，因此我们把 $m = n - 1$ 代入 $(2)$ 式，得到：
$$ a^n = a^{n - 1} \times a \tag{3} $$
发现出现了一个 $a^{n - 1}$，这是我们熟悉的形式。像我们刚才处理 $n$ 为偶数的情况一样，将 $m = \dfrac{n - 1}{2}$ 代入 $(1)$ 式，得到：
$$ a^{n - 1} = (a^{\tfrac{n - 1}{2}})^2 $$
代回到 $(3)$ 式，得到：
$$ a^n = (a^{\tfrac{n - 1}{2}}) ^ 2 \times a $$
整理一下，对于一个数 $a$ 的 $n$ 次幂，就有：
$$ a^n = \begin{cases} (a^{\tfrac{n}{2}})^2, & \text{if } n \text{ is even} \\ (a^{\tfrac{n - 1}{2}}) ^ 2 \times a, & \text{if } n \text{ is odd} \end{cases} $$
但 $\dfrac{n}{2}$ 与 $\dfrac{n - 1}{2}$ 写起来似乎有些复杂，我们想到借用 C++ 的整除特性，使用 $\left \lfloor \dfrac{n}{2} \right \rfloor$（即 $\dfrac{n}{2}$ 的向下取整）即可省去繁琐的条件判断。如果 $n$ 是奇数，只要在结果的后面再乘一个 $a$ 即可。
此时，我们就成功地把 $a^n$ 拆分成两个（或三个）数的乘积，那么只要一直拆分下去，一定会有一刻拆成 $a^0 = 1$。顺着这个思路，我们就可以写出递归的代码：
long long fastpow(long long a, long long n) {
if (n == 0) return 1;
long long res = fastpow(a, n / 2);
if (n % 2 == 1) res *= a;
return res * res;
}幂运算的问题已经解决，接下来我们讨论如何处理算式后面的取模（即 $\bmod p$）。
我们知道，模运算有如下性质：
- 模运算对加法的封闭性：$(a + b) \bmod p = (a \bmod p + b \bmod p) \bmod p$。
- 模运算对乘法的封闭性：$(a \times b) \bmod p = [(a \bmod p) \times (b \bmod p)] \bmod p$。
因此有：
$$ \begin{align*} a^n \bmod p & = \underbrace{a \times a \times a \times \cdots \times a}_{n \text{ 个 } a} \ \bmod p \\ & = [\underbrace{(a \bmod p) \times (a \bmod p) \times (a \bmod p) \times \cdots \times (a \bmod p)}_{n \text{ 个 } a \bmod p}] \bmod p \end{align*} $$
所以只需要在每次做乘法的时候继续做一次取模即可，代码修改如下：
long long fastpow(long long a, long long n, long long p) {
if (n == 0) return 1;
long long res = fastpow(a, n / 2);
if (n % 2 == 1) res = res * a % p;
return res * res % p;
}此时，代码已经可以通过本题，这样的算法被称为快速幂。
但，能否更优？
答案是肯定的。注意到，上面的代码是一个递归函数，而递归本身也会有一定的开销，因此，更常见的写法是非递归式的。
long long fastpow(long long a, long long b, long long p) {
long long res = 1;
while (b != 0) {
if (b % 2 == 1) res = res * a % p;
a = a * a % p, b /= 2;
} return res;
}复杂度分析
前面提到的拆分，实质是我们对指数 $n$ 在二进制下的每一位进行处理的过程。每次迭代中，如果当前二进制位为 $1$，则将当前底数乘入结果，同时底数不断平方。迭代次数等于 $n$ 的二进制位数。
我们设 $n$ 的二进制表示有 $k = \lfloor \log_2 n \rfloor + 1$ 位，显然有 $k = \Theta (\log n)$，因为 $\log_2 \le k \le \log_2 n + 1$。
每次迭代时，进行一次平方操作，如果当前位为 $1$，则再多一次乘法操作。因此：
- 最多需要进行 $2k = 2 \lfloor \log_2 n \rfloor + 2$ 次操作，故存在常数 $C$ 使得总时间不超过 $C \log n$，即有上界 $O(\log n)$；
- 最少需要处理所有 $k$ 位，每次至少一次平方操作，故存在常数 $C'$ 使得总时间至少为 $C' \log n$，即有下界 $\Omega (\log n)$。
因此，快速幂的时间复杂度为 $\Theta (\log n)$，效率远高于直接使用循环的 $\Theta (n)$。
代码实现
#include <iostream>
using namespace std;
long long a, b, p;
long long fastpow(long long a, long long b, long long p) {
long long res = 1;
while (b != 0) {
if (b % 2 == 1) res = res * a % p;
a = a * a % p, b /= 2;
} return res;
}
int main() {
cin >> a >> b >> p;
cout << a << '^' << b << " mod " << p << '=' << fastpow(a, b, p) << '\n';
return 0;
}