快速幂 — 二进制拆分加速

问题

计算 $a^b \bmod m$，其中 $b$ 最高可达 $10^9$。如果直接循环 $b$ 次，$O(b)$ 的时间复杂度必然 TLE。

怎么想？

把 $b$ 写成二进制形式：

$$b = (b_k b_{k-1} \dots b_1 b_0)_2 = b_0 \cdot 2^0 + b_1 \cdot 2^1 + \dots + b_k \cdot 2^k$$

于是：

$$a^b = a^{b_0 \cdot 2^0} \times a^{b_1 \cdot 2^1} \times \dots \times a^{b_k \cdot 2^k}$$

其中每个 $b_i \in \{0, 1\}$。当 $b_i = 1$ 时，乘上对应的 $a^{2^i}$；$b_i = 0$ 时跳过。

而 $a^{2^i}$ 可以通过反复平方得到：$(a^{2^{i-1}})^2 = a^{2^i}$。

这样只需要 $O(\log b)$ 次运算，$b=10^9$ 时 $\log_2 b \approx 30$ 次，比 $10^9$ 次循环快了三千多万倍！

位运算实现

如何判断 $b$ 的二进制第 $i$ 位是 $0$ 还是 $1$？—— 答案：位运算！

运算	含义	示例
b & 1	取 $b$ 的最低位（第 $0$ 位）	13 & 1 = 1
b >>= 1	$b$ 右移一位（去掉最低位）	13 >> 1 = 6

算法流程：

1. b & 1 检查当前最低位，若为 $1$ 则乘入答案
2. a = a * a % m 计算下一次的基底（平方）
3. b >>= 1 右移一位，继续处理下一个二进制位
4. 当 b == 0 时结束

以 $a=2, b=13$ 为例：

$$13 = 1101_2 = 2^3 + 2^2 + 2^0$$

轮次	$b$（二进制）	$b \& 1$	$a$ 的幂次	乘入？	答案
1	1101	1	$2^1$	✓	$2$
2	110	0	$2^2$	✗
3	11	1	$2^4$	✓	$2 \times 16 = 32$
4	1		$2^8$		$32 \times 256 = 8192$
5	0	—			$8192$

$2^{13} = 8192$，仅需 $4$ 轮！

复杂度

• 时间：$O(\log b)$，每次循环做常数次乘法和位运算
• 空间：$O(1)$

代码

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

typedef long long ll;

ll fast_pow(ll a, ll b, ll m) {
    ll res = 1 % m;   // 注意 m 可能为 1
    a %= m;
    while (b) {
        if (b & 1)            // 最低位是 1 吗？
            res = (res * a) % m;
        a = (a * a) % m;      // 平方，准备下一位
        b >>= 1;              // 右移，处理下一个二进制位
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false), cin.tie(NULL);
    ll a, b, m;
    cin >> a >> b >> m;
    cout << fast_pow(a, b, m) << '\n';
    return 0;
}