快速幂 题解

一、问题

计算 a^b mod m。b 最大到 10^9。 如果直接循环 b 次：for i in range(b): result = result * a % m，10^9 次循环直接 TLE

二、核心原理：二分

幂运算有个性质：

$a^8 = (a^4)^2$ ← 算一次 $a^4$，再平方一次就行 $a^9 = a × (a^8)$ ← 奇数的话拆一个 $a$ 出来

每一步把指数对半砍，$10^9$ 只要砍约 30 次就到 1 了

三、算法：快速幂

把指数 b 写成二进制。例如 b = 10：

10 的二进制 $= 1010$ $= 1×8 + 0×4 + 1×2 + 0×1$ $= 8 + 2$

所以 $a$^$10$ $=$ $a^8$ × $a^2$ 只需要两个关键值：$a^2$ 和 $a^8$

四、$a^2$ 和 $a^8$ 怎么得出来？

初始: $a = a^1$

看第 $0$ 位（最低位）: $a = a^1$ 看第 $1$ 位: $a = a^2$ ← 平方 看第 $2$ 位: $a = a^4$ ← 再平方 看第 $3$ 位: $a = a^8$ ← 再平方

b的二进制哪位是 1，就把当前 a 乘进答案

五、手算验证：$2$^$10$ $mod 1000$

b=10，二进制 1010，从低到高看：

步骤	B	B最低位	A（当前值）	RESULT	解释
初始	10	-	$2^1 = 2$	1
1	10	$0$	$2^2 = 4$	$1$	最低位 0，不乘，a 平方
2	5	$1$	$2^4 = 16$	$1×4 = 4$	最低位 1，乘入，a 平方
3	2	$0$	$2^8 = 256$	$4$	最低位 0，不乘，a 平方
4	1	$1$	-	$4×256 = 1024$	最低位 1，乘入

最后 result = 1024，mod 1000 = 24

六、代码

a, b, m = map(int, input().split())

result = 1
a = a % m

while b > 0:
    if b % 2 == 1:               # b 的二进制最低位是 1
        result = (result * a) % m
    a = (a * a) % m              # a 平方，准备看下一位
    b //= 2                      # b 右移，砍掉最低位

print(result)

using System;

class Program
{
    static void Main()
    {
        string[] input = Console.ReadLine().Split();
        long a = long.Parse(input[0]);
        long b = long.Parse(input[1]);
        long m = long.Parse(input[2]);

        long result = 1;
        a = a % m;

        while (b > 0)
        {
            if (b % 2 == 1)              // 二进制最低位是 1
                result = (result * a) % m;

            a = (a * a) % m;             // a 平方
            b /= 2;                      // b 右移
        }

        Console.WriteLine(result);
    }
}

快速幂 — 二进制拆分加速

问题

计算 $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;
}