【GESP】C++八级考试大纲知识点梳理 (4) 倍增法
继上一篇我们探讨了杨辉三角与组合数之后，我们继续深入 GESP C++ 八级大纲。今天的主角是算法竞赛中极其常用且高效的思想——倍增法。
（4）掌握倍增法概念。了解倍增法的时间复杂度。
倍增法（Doubling Method）不仅仅是一个特定的算法，更像是一种“思想”。它的核心在于“成倍增长”，利用二进制的性质，将线性级别的处理转化为对数级别的处理，极大地优化了时间复杂度。
本人也是边学、边实验、边总结，且对考纲深度和广度的把握属于个人理解。因此本文更多的不是一个教程，而是个人知识梳理，如有遗漏、疏忽，欢迎指正、交流。
一、什么是倍增法？
顾名思义，倍增就是“成倍增加”。
想象一下，你要从起点 A 走到终点 B。
- 普通方法：一步一步走，每次走 1 米。如果距离是 $N$ 米，需要走 $N$ 步。时间复杂度 $O(N)$。
- 倍增方法：通过“预处理能力”，我们可以一次跳 $1, 2, 4, 8, 16, \dots, 2^k$ 米。
- 如果距离是 15 米，我们可以先跳 8 米，再跳 4 米，再跳 2 米，再跳 1 米（$15 = 8+4+2+1$）。
- 总共只需要跳 4 次，而不是 15 次。
核心原理：
任何一个正整数 $N$ 都可以表示为若干个 $2$ 的幂次之和（这就是二进制的本质）。 例如 $19 = 16 + 2 + 1 = (10011)_2$。 因此，我们可以通过组合这些 $2^k$ 的跳跃，快速到达任何目标位置。
1.1 时间复杂度
倍增法的核心优势在于速度。 对于范围 $N$，我们只需要考虑 $2^0, 2^1, \dots, 2^k$ (其中 $2^k \le N$) 也就是 $\log_2 N$ 级别的数据。 因此，倍增法相关的查询操作通常具有 $O(\log N)$ 的时间复杂度。
二、倍增法的应用场景
快速幂 (Quick Pow)
这是倍增思想最基础、最典型的应用，用于快速计算 $a^b \pmod p$。
1. 核心思想：二进制拆分
普通做法：
写一个循环，执行 $b$ 次乘法。时间复杂度 $O(b)$。当 $b$ 很大（如 $10^{18}$）时，绝对会因超时（TLE）而得分 0。
倍增做法：
利用 $b$ 的二进制表示，我们将 $b$ 拆解为若干个 $2^k$ 的和。 例如计算 $3^{13}$：
\(13 = (1101)_2 = 8 + 4 + 1\) 所以：
\[3^{13} = 3^{(8+4+1)} = 3^8 \times 3^4 \times 3^1\]你会发现，每一项 $3^1, 3^2, 3^4, 3^8 \dots$ 都是前一项的平方。
- $3^1 = 3$
- $3^2 = (3^1)^2$
- $3^4 = (3^2)^2$
- $3^8 = (3^4)^2$
我们只需要简单的 $O(\log b)$ 次乘法，就可以算出结果。
2. 代码示例 (C++)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
* 快速幂计算 a^b % p
* 时间复杂度：O(log b)
* 空间复杂度：O(1)
*/
long long quick_pow(long long a, long long b, long long p) {
long long ans = 1; // 记录最终结果
a = a % p; // 预先取模，防止 a 很大导致溢出
while (b > 0) {
// 核心逻辑：判断 b 的二进制最后一位是 0 还是 1
// 如果是 1 (即 b 为奇数)，说明当前的权重 a 需要乘进结果里
if (b & 1) {
ans = (ans * a) % p;
}
// a 自身倍增：a^1 -> a^2 -> a^4 -> a^8 ...
// 无论当前位是否为 1，权值 a 都要翻倍等待下一位使用
a = (a * a) % p;
// b 右移一位，相当于除以 2，处理下一位二进制
b >>= 1;
}
return ans;
}
为了让大家更清晰地理解代码与上述数学原理的对应关系，我们可以看下面这个演示图：
b & 1(取当前最低位)：这是在检查 $b$ 的二进制表示中，当前处理到的这一位是 0 还是 1。- 如果是 1：说明指数 $b$ 包含当前的 $2^k$ (例如 $13 = 8+4+1$ 中的 $1$)。因此，我们需要把当前的底数
a(此时它的值是 $a^{2^k}$) 乘进结果ans里。 - 如果是 0：说明不需要这一项，直接跳过。
- 如果是 1：说明指数 $b$ 包含当前的 $2^k$ (例如 $13 = 8+4+1$ 中的 $1$)。因此，我们需要把当前的底数
a = a * a(基数倍增)：对应 $a^1 \to a^2 \to a^4 \to a^8 \dots$ 的过程。无论b的当前位是不是 1，底数a都要不断翻倍，为下一位做准备。b >>= 1(右移)：对应二进制位的遍历，从低位向高位移动。
演示：计算 $3^{13} \pmod p$ $(13 = 1101_2)$
| 循环轮次 | 当前 b (二进制) | 当前底数 a | 判断 b & 1 | 操作 | ans 变化 |
|---|---|---|---|---|---|
| 初始 | 1101 (13) | $3^1$ | 是 | 乘入 ans | $1 \times 3^1$ |
| 第 1 轮 | 110 (6) | $3^2$ | 否 | 不乘 | 不变 |
| 第 2 轮 | 11 (3) | $3^4$ | 是 | 乘入 ans | $3^1 \times 3^4$ |
| 第 3 轮 | 1 (1) | $3^8$ | 是 | 乘入 ans | $3^1 \times 3^4 \times 3^8$ |
| 结束 | 0 | - | - | - | $3^{13}$ |
3. 其他应用拓展举例
快速幂不仅仅用于算“幂”，它的本质是“利用二进制加速递推”。常见的变形和应用包括：
(1) 模运算乘法逆元 (Modular Multiplicative Inverse) 在计算组合数 $C(n, m) \pmod p$ 或有理数取模时，需要做除法 $a/b \pmod p$。 但是模运算没有除法（$(a/b) \% p \neq (a\%p / b\%p) \% p$）。 根据费马小定理，我们可以把除法转为乘法：
费马小定理：如果 $p$ 是质数，且 $a$ 不是 $p$ 的倍数，则 $a^{p-1} \equiv 1 \pmod p$。
符号解释：“$\equiv$” 是同余符号。这句话的通俗意思是：$a^{p-1}$ 除以 $p$ 的余数是 1。
变形一下：$a \times a^{p-2} \equiv 1 \pmod p$。 这说明 $a^{p-2}$ 就是 $a$ 在模 $p$ 意义下的倒数（即逆元）。 所以：$a / b \pmod p \iff a \times b^{p-2} \pmod p$。
即求 $b$ 的 $p-2$ 次方。这是快速幂最高频的使用场景。
(2) 矩阵快速幂 (Matrix Exponentiation) 如果把数字 $a$ 换成一个矩阵 $A$，把乘法换成矩阵乘法，原理一模一样。 这用于解决 $O(N)$ 递推问题（如斐波那契数列、线性递推式）加速到 $O(\log N)$。 \(\begin{bmatrix} F_{n+1} \\ F_n \end{bmatrix} = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^n \begin{bmatrix} F_1 \\ F_0 \end{bmatrix}\) 其中矩阵的 $n$ 次幂就用快速幂求解。
(3) 快速乘 (Quick Mul) 当 $a \times b \pmod p$ 中，$a$和$b$都高达 $10^{18}$，直接相乘会爆 long long 范围。 我们可以把“乘法”看作是“加法的幂”，用类似快速幂的逻辑（把 $x$ 换成 $+$）： $a \times 13 = a \times (8+4+1) = (a \times 8) + (a \times 4) + (a \times 1)$。 通过倍增 $a$ 来实现大数相乘取模。
(4) 字符串 Hash / 滚动 Hash 在计算字符串 Hash 值时，经常需要计算 $Base^k \pmod M$，为了快速获取子串 Hash，需要快速幂预处理或实时计算 $Base$ 的幂。
三、总结
倍增法是解决很多“线性变对数”问题的金钥匙。
- 核心：利用二进制拆分，将 $N$ 次操作压缩为 $\log N$ 次。
掌握了倍增，你不仅能解决 8 级的考点，更是在向高级算法思维迈进了一大步。
所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code
GESP 学习专题站：GESP WIKI
“luogu-”系列题目可在洛谷题库进行在线评测。
“bcqm-”系列题目可在编程启蒙题库进行在线评测。
欢迎加入：Java、C++、Python技术交流QQ群(982860385)，大佬免费带队，有问必答
欢迎加入：C++ GESP/CSP认证学习QQ频道，考试资源总结汇总
欢迎加入：C++ GESP/CSP学习交流QQ群(688906745)，考试认证学员交流，互帮互助
