(4) 倍增法

GESP C++ 八级考试大纲知识点梳理系列文章：

1. 计数原理：加法与乘法
2. 排列与组合
3. 杨辉三角与组合数
4. 倍增法
5. 代数与平面几何 {: .prompt-tip}

继上一篇我们探讨了杨辉三角与组合数之后，我们继续深入 GESP C++ 八级大纲。今天的主角是算法竞赛中极其常用且高效的思想——倍增法。

（4）掌握倍增法概念。了解倍增法的时间复杂度。 {: .prompt-info}

倍增法（Doubling Method）不仅仅是一个特定的算法，更像是一种“思想”。它的核心在于“成倍增长”，利用二进制的性质，将线性级别的处理转化为对数级别的处理，极大地优化了时间复杂度。

本人也是边学、边实验、边总结，且对考纲深度和广度的把握属于个人理解。因此本文更多的不是一个教程，而是个人知识梳理，如有遗漏、疏忽，欢迎指正、交流。 {: .prompt-warning}

一、什么是倍增法？

顾名思义，倍增就是“成倍增加”。

想象一下，你要从起点 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}$：

所以：

你会发现，每一项 $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++)

/**
 * 快速幂计算 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：说明不需要这一项，直接跳过。
• 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)$

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)$。

其中矩阵的 $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 级的考点，更是在向高级算法思维迈进了一大步。

本文由coderli.com原创，按照CC BY-NC-SA 4.0 进行授权

所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code

“luogu-”系列题目可在 洛谷题库 在线评测。

“bcqm-”系列题目可在 编程启蒙题库 在线评测。

GESP/CSP认证交流QQ群： 688906745

GESP/CSP 认证学习微信公众号