第 50 章翻倍的力量——倍增与快速幂

🏗️ 前情回顾：第 49 章的分治"把问题砍一半"——越来越小。而本章的倍增反其道而行之：从 1 开始，每次翻倍。它虽然不是独立的"算法范式"，但和分治同源（都基于二进制拆分），且快速幂在竞赛中无处不在。你还将初次触碰到 ST 表和 LCA 的伏笔。

🎯 本章目标

学完这一章，你能：

感受翻倍的力量——指数增长的直观震撼
理解快速幂（二分幂）的二进制拆分原理
熟练掌握 a^b mod p 的 O(log b) 计算
了解倍增的基本思想：每次跳 2^k 步
了解倍增查找（类 ST 表思想）
对 LCA（最近公共祖先）的倍增解法有初步印象

📖 故事引入

如果给你一张足够大的纸，厚度 0.1 毫米。把它对折一次，厚度变成 0.2mm。对折两次：0.4mm。对折三次：0.8mm……

你猜，对折 30 次有多厚？

0.1mm × 2^30 ≈ 0.1mm × 1,073,741,824 ≈ 107 公里！比大气层的对流层还厚，超过地球到太空的分界线（卡门线 100km）！

这就是指数增长（翻倍）的力量——一开始不显眼，越往后越恐怖。

在编程中，这个思想转化为快速幂和倍增：利用"二进制拆分"，把 O(n) 的操作降到 O(log n)。

怎么拆？比如计算 a^13。你不需要把 a 乘 13 次。13 的二进制是 1101：

a^13 = a^(8+4+1) = a^8 × a^4 × a^1

只需要算出 a^1, a^2, a^4, a^8（每次平方即可得到下一个），然后把对应二进制位为 1 的乘起来。只用 3 次乘法！

🧱 知识讲解

50.1 快速幂：a^b mod p

问题：计算 a^b mod p。a, b 可能很大（b ≤ 10^9），不能一个个乘。

核心思想——二进制拆分：

把指数 b 写成二进制，比如 b = 13₁₀ = 1101₂，那么：

a^13 = a^8 × a^4 × a^1

我们只需要预计算 a^1, a^2, a^4, a^8, ... ——每个是前一个的平方。然后看 b 的二进制哪些位是 1，把对应的乘起来。

cpp

long long qpow(long long a, long long b, long long p) {
    long long result = 1;
    a %= p;                // 先取模，防溢出
    while (b > 0) {
        if (b & 1)         // b 的当前最低位是 1
            result = (result * a) % p;
        a = (a * a) % p;   // a 平方：a^1 → a^2 → a^4 → a^8 ...
        b >>= 1;           // b 右移一位
    }
    return result;
}

跟踪一下：计算 2^13 mod 1000。

轮次	b (二进制)	b&1	result	a (底数)
初始	1101	—	1	2
1	1101	1	1×2=2	2²=4
2	110	0	2	4²=16
3	11	1	2×16=32	16²=256
4	1	1	32×256=8192→192	256²(太大,mod)
结果	0	—	192	—

验证：2^13 = 8192，8192 mod 1000 = 192。✅

时间复杂度：O(log b)，b=10^9 时只需约 30 次循环。

50.2 "翻倍"映射到"二进制"

为什么二进制拆分这么神？因为任何正整数都能唯一地表示成 2 的幂之和（二进制的基本性质）。

b = 2^k₁ + 2^k₂ + ... + 2^kₘ

所以：

a^b = a^(2^k₁) × a^(2^k₂) × ... × a^(2^kₘ)

而 a^(2^k) 可以通过反复平方得到：

a^(2^0) = a
a^(2^1) = a²
a^(2^2) = a⁴ = (a²)²
a^(2^3) = a⁸ = (a⁴)²
...

每次翻倍（平方），恰好对应二进制的高一位。

🔍 类比：就像你要凑出 13 块钱，可以拿 1 张 8 块 + 1 张 4 块 + 1 张 1 块。二进制就是这个"面额"——1, 2, 4, 8, 16... 恰好是翻倍关系。

50.3 倍增思想：每次跳 2^k

快速幂是倍增在一个具体问题上的应用。倍增这个思想更通用：预处理出"从当前位置走 2^k 步"的信息，然后二进制拆分要走的步数。

比如：你要从数组的第 1 个位置往后跳 13 步，到达第 14 个位置。可以分解成：

跳 13 步 = 跳 8 步 + 跳 4 步 + 跳 1 步
          (2^3)   (2^2)   (2^0)

如果你已经预处理好了"从每个位置跳 2^k 步到达的位置"（一个二维数组 f[i][k]），那么跳 13 步就是查 3 次表：f[f[f[1][0]][2]][3]。

50.4 倍增查找（类似 ST 表思想）

问题：有一个很长的数组，你需要多次查询"从位置 pos 开始往后走 steps 步，到达的位置"。

如果 steps 每次不同且可能很大，最笨的方法是一次次加。倍增做法：

预处理：go[i][k] = 从位置 i 跳 2^k 步后到达的位置
查询：把 steps 二进制拆分，逐段跳

cpp

// 预处理
for (int i = 1; i <= n; i++) go[i][0] = i + 1;  // 跳1步
for (int k = 1; k <= 20; k++)
    for (int i = 1; i <= n; i++)
        go[i][k] = go[go[i][k-1]][k-1];  // 跳2^k = 跳2^(k-1)再跳2^(k-1)

// 查询：从 pos 跳 steps 步
int query(int pos, int steps) {
    for (int k = 0; steps > 0; k++, steps >>= 1) {
        if (steps & 1) pos = go[pos][k];
    }
    return pos;
}

50.5 LCA 算法预告

LCA（Lowest Common Ancestor，最近公共祖先）是树上最经典的问题之一。倍增法解决 LCA 的复杂度是 O(n log n) 预处理 + O(log n) 每次查询。

核心思想（建立直觉即可，详细内容在后续模块）：

① 用 DFS 预处理每个节点的深度 depth[u] 和它的 2^k 级祖先 up[u][k]
② 查询 LCA(u, v)：
   - 先把较深的节点往上跳到和另一个同一深度（用倍增跳）
   - 然后两个节点一起往上跳（同样用倍增），直到它们的父节点相同

这里的 up[u][k] 就是倍增的体现：up[u][k] = 节点 u 往上跳 2^k 步到达的祖先节点。

cpp

// up[u][k] 的预处理
up[u][0] = parent[u];  // 往上 2^0 = 1 步，就是父节点
up[u][k] = up[ up[u][k-1] ][k-1];  // 往上 2^k = 先往上 2^(k-1)，再往上 2^(k-1)

🧠 这个"跳两次 2^(k-1) 等于跳一次 2^k"的递推关系，和快速幂中"a 平方再平方得到 a^4"是同一个逻辑，只是从"乘法"变成了"位置跳跃"。

✋ 动手试试

试试 1：实现快速幂，计算 3^100 mod 7。手工跟踪二进制拆分的过程，然后用程序验证结果。（提示：3^6=729≡1 mod 7，周期是 6）

试试 2：用快速幂求斐波那契数列第 n 项（矩阵快速幂）。提示：[[F(n+1), F(n)], [F(n), F(n-1)]] = [[1,1],[1,0]]^n，用快速幂计算矩阵的 n 次方。

试试 3：实现"跳格子"的倍增查询。数组大小 n=16，初始时每个位置 i 跳到 i+1（最后一格不动）。预处理 go[i][k]，然后查询从位置 1 跳 13 步后在哪（应该是 14）。

⚠️ 容易犯的错

错 1：快速幂忘了先对 a 取模

❌ a^b mod p 中 a 本身可能很大，直接 a*a 溢出

✅ 一上来就 a %= p;

错 2：快速幂中结果初始化为 0

❌ int result = 0; → 0 乘任何数都是 0

✅ int result = 1;（乘法单位元是 1）

错 3：倍增预处理时边界写错

❌ go[i][k] = go[go[i][k-1]][k-1]，但 go[i][k-1] 可能越界

✅ 确保预处理数组足够大，或在到达边界时做特殊处理

错 4：把快速幂的底数和指数搞混

❌ a = a * 2（在翻倍底数？不，是平方）

✅ a = (a * a) % p;（底数平方，对应指数的二进制位权重翻倍）

📝 练习

基础题

1. 选择题

（1）快速幂计算 a^b 的时间复杂度是？
A. O(b) B. O(log b) C. O(a) D. O(b²)

（2）13 的二进制表示是？
A. 1011 B. 1101 C. 1110 D. 1001

（3）a^(2^k) 可以通过什么操作得到？
A. a 乘以 2^k B. a 反复平方 k 次 C. a 反复加自己 D. a 除以 2

2. 填空题

（1）快速幂的核心思想是把指数 b 拆成____之和。

（2）b & 1 用来判断 b 的二进制____位是否为 1。

（3）倍增递推公式：up[u][k] = ____[ ____[u][k-1] ][k-1]。

提高题

3. 编程题 — 快速幂

实现 long long qpow(long long a, long long b, long long p)，计算 a^b mod p。输入 a, b, p，输出结果。测试：2^10 mod 1000 = 24。

4. 编程题 — 快速幂求个位数

求 a^b 的个位数（即 mod 10）。输入 a, b（1 ≤ a ≤ 100, 1 ≤ b ≤ 10^9），输出 a^b 的个位数。

挑战题

5. 编程题 — 斐波那契第 n 项（矩阵快速幂）

用矩阵快速幂求斐波那契数列第 n 项 mod 1000000007。n ≤ 10^18。

提示：定义 2×2 矩阵乘法，快速幂计算 [[1,1],[1,0]]^n，结果在 [0][1] 或 [1][0] 位置。

🧠 本章小结

倍增 = 翻倍的力量

快速幂：
  核心：二进制拆分 b → a^b = Π a^(2^k)，其中 b 的第 k 位为 1
  底数 a 反复平方：a → a² → a⁴ → a⁸ ...
  指数 b 逐位检查：b & 1 判断最低位，b >>= 1 右移
  
  代码框架：
    result = 1
    while b>0:
      if b&1: result = result * a % p
      a = a * a % p
      b >>= 1

  复杂度：O(log b)

倍增查找：
  go[i][k] = 从 i 跳 2^k 步到达的位置
  递推：go[i][k] = go[ go[i][k-1] ][k-1]

LCA 预告：
  树上倍增：up[u][k] = u 的 2^k 级祖先
  关键递推：up[u][k] = up[ up[u][k-1] ][k-1]

📝 配套练习

共5题。快速幂→高精快速幂→矩阵快速幂→倍增思想，四种倍增应用。。★核心（课堂必做） ◆拓展（课后练习）

级别	题号	链接	覆盖知识点
★ 核心	luogu-P1226	https://hydro.ac/p/luogu-P1226	快速幂、迭代版、二进制拆分
◆ 拓展	luogu-P1045	https://hydro.ac/p/luogu-P1045	快速幂+高精度、麦森数
◆ 拓展	luogu-P1962	https://hydro.ac/p/luogu-P1962	矩阵快速幂、斐波那契O(logn)
◆ 拓展	luogu-P3390	https://hydro.ac/p/luogu-P3390	矩阵快速幂模板
◆ 拓展	luogu-P2886	https://hydro.ac/p/luogu-P2886	倍增思想、ST表启蒙
◆ 拓展	luogu-P6188	https://hydro.ac/p/luogu-P6188	NOI Online、贪心
◆ 拓展	luogu-P1065	https://hydro.ac/p/luogu-P1065	NOIP2006提高、大模拟综合
◆ 拓展	luogu-P9287	https://hydro.ac/p/luogu-P9287	ROI2018、复杂模拟
◆ 拓展	luogu-P9585	https://hydro.ac/p/luogu-P9585	MXOI、贪心/枚举
◆ 拓展	luogu-P8050	https://hydro.ac/p/luogu-P8050	ZYOI、模拟
◆ 拓展	luogu-P7199	https://hydro.ac/p/luogu-P7199	COCI、数学推导

💡 练习建议：先完成 1 道★核心题，确保掌握本章基本方法；再完成 10 道◆拓展题，覆盖不同变式和细节。

配套练习

共5题。快速幂→高精快速幂→矩阵快速幂→倍增思想，四种倍增应用。★核心（课堂必做） · ◆拓展（课后练习）

级别	题号	链接	覆盖知识点
★ 核心	luogu-P1226	https://hydro.ac/p/luogu-P1226	快速幂、迭代版、二进制拆分
◆ 拓展	luogu-P1045	https://hydro.ac/p/luogu-P1045	快速幂+高精度、麦森数
◆ 拓展	luogu-P1962	https://hydro.ac/p/luogu-P1962	矩阵快速幂、斐波那契O(logn)
◆ 拓展	luogu-P3390	https://hydro.ac/p/luogu-P3390	矩阵快速幂模板
◆ 拓展	luogu-P2886	https://hydro.ac/p/luogu-P2886	倍增思想、ST表启蒙
◆ 拓展	luogu-P6188	https://hydro.ac/p/luogu-P6188	NOI Online、贪心
◆ 拓展	luogu-P1065	https://hydro.ac/p/luogu-P1065	NOIP2006提高、大模拟综合
◆ 拓展	luogu-P9287	https://hydro.ac/p/luogu-P9287	ROI2018、复杂模拟
◆ 拓展	luogu-P9585	https://hydro.ac/p/luogu-P9585	MXOI、贪心/枚举
◆ 拓展	luogu-P8050	https://hydro.ac/p/luogu-P8050	ZYOI、模拟
◆ 拓展	luogu-P7199	https://hydro.ac/p/luogu-P7199	COCI、数学推导

练习建议：先在课堂完成 1 道★核心题，掌握本章基本方法；课后完成 10 道◆拓展题，覆盖不同变式和细节。

自查清单：

[ ] 我理解"二进制拆分"在快速幂中的作用
[ ] 我能手写快速幂（包括模运算的细节）
[ ] 我理解快速幂的 O(log b) 复杂度来源
[ ] 我了解倍增的基本思想——预处理 2^k 步的结果
[ ] 我能写出倍增查询的框架
[ ] 我对 LCA 的倍增解法有初步印象

🚀 下章预告：M7 模块到此全部结束！从递归深潜到记忆化，从二分到贪心，从分治到倍增——你已经掌握了算法竞赛中最核心的几种思维范式。下一模块 M8，我们将走进线性数据结构的世界——栈、队列、vector、链表……把这些兵器一件件收入囊中！🔧📚

第 50 章 翻倍的力量——倍增与快速幂 ​

🎯 本章目标 ​

📖 故事引入 ​

🧱 知识讲解 ​

50.1 快速幂：a^b mod p ​

50.2 "翻倍"映射到"二进制" ​

50.3 倍增思想：每次跳 2^k ​

50.4 倍增查找（类似 ST 表思想） ​

50.5 LCA 算法预告 ​

✋ 动手试试 ​

⚠️ 容易犯的错 ​

错 1：快速幂忘了先对 a 取模 ​

错 2：快速幂中结果初始化为 0 ​

错 3：倍增预处理时边界写错 ​

错 4：把快速幂的底数和指数搞混 ​

📝 练习 ​

基础题 ​

提高题 ​

挑战题 ​

🧠 本章小结 ​

📝 配套练习 ​

配套练习 ​