第5章 倍增法

---

🎯 本章学习目标

通过本章的学习，你将能够：

1. 理解倍增思想：掌握"二进制跳跃"的核心——把任意数拆成2的幂之和
2. 精通快速幂：熟练写出快速幂模板，理解每一步的含义
3. 掌握快速幂取模：理解模运算性质，避免溢出
4. 理解LCA：知道最近公共祖先问题的倍增解法
5. 理解RMQ：知道ST表求解区间最值的倍增思想
6. 分析复杂度：清楚倍增算法的时间复杂度 O(log n)
7. 掌握位运算：熟练使用 b&1、b>>=1 等位操作
8. 避免溢出：知道用 long long 防止乘法溢出
9. 手动模拟：能手动画出快速幂的执行过程
10. 应对真题题型：能解决选择、判断、编程等各类倍增题目

---

🗺️ 本章知识图谱

倍增法
├── 核心思想
│   ├── 任意整数 = 若干2的幂之和（二进制）
│   ├── 预处理 1, 2, 4, 8, ... 步的信息
│   ├── 需要时拼二进制
│   └── O(n) → O(log n)
├── 快速幂（最经典）
│   ├── 求 a^b mod p
│   ├── 模板
│   │   ├── ans = 1
│   │   ├── while b > 0
│   │   │   ├── if b & 1: ans = ans * a % p
│   │   │   ├── a = a * a % p（底数平方）
│   │   │   └── b >>= 1（指数右移）
│   │   └── return ans
│   ├── 时间复杂度：O(log b)
│   └── 注意：用long long防溢出
├── LCA 最近公共祖先
│   ├── 树上两个点的最近公共祖先
│   ├── up[j][i] = i的2^j级祖先
│   ├── 递推：up[j][i] = up[j-1][up[j-1][i]]
│   ├── 预处理：O(n log n)
│   └── 查询：O(log n)
├── RMQ 区间最值（ST表）
│   ├── 求数组区间最大值/最小值
│   ├── f[j][i] = 从i开始长度2^j的区间最值
│   ├── 递推：f[j][i] = max(f[j-1][i], f[j-1][i+2^(j-1)])
│   ├── 预处理：O(n log n)
│   └── 查询：O(1)（两个区间拼）
├── 位运算基础
│   ├── b & 1：取最低位
│   ├── b >>= 1：右移一位（除以2）
│   └── 2^j：1 << j
├── 易错点
│   ├── 复杂度是O(log b)不是O(log a)
│   ├── 乘法要用long long防溢出
│   ├── ans初始值为1（乘法单位元）
│   ├── 循环条件while(b>0)不是while(b>1)
│   └── 每步都要取模
└── 应用场景
    ├── 快速幂（模意义下幂运算）
    ├── LCA（树上最近公共祖先）
    ├── RMQ（区间最值查询）
    ├── 二进制跳跃
    └── 算法优化

---

一、什么是倍增？——先讲一个"跳格子"的故事

🐸 一个直觉场景

假设青蛙要从第 0 格跳到第 15 格：

• 普通跳法：每次跳 1 格，要跳 15 次；
• 倍增跳法：青蛙学会了"翻倍跳"，一次可以跳 1、2、4、8、…、2ᵏ 格。那么 15 = 8 + 4 + 2 + 1，先跳 8 格、再跳 4 格、再跳 2 格、最后跳 1 格，只跳 4 次就到了！

目标距离	一步一格	倍增跳（2 的幂次）
15 格	15 次	8+4+2+1，共 4 次
100 格	100 次	64+32+4，共 3 次
10⁹ 格	10⁹ 次	最多 30 次

📐 折纸比喻：一张纸对折 1 次厚度 ×2，对折 30 次，厚度是原来的 2³⁰ ≈ 10.7 亿倍（约 107 千米，比珠穆朗玛峰还高 12 倍！）。这就是"翻倍"的恐怖速度。

🧠 倍增法的核心思想

倍增（Binary Lifting）：不再"一次走 1 步"，而是预处理出"走 1、2、4、8、…、2ᵏ 步"的能力，需要走任意 n 步时，把 n 拆成若干个 2 的幂之和，用这些"大跨步"组合出目标。

数学本质——二进制拆分：

任何一个正整数 n，都可以唯一表示为若干个 2 的幂之和，这正是它的二进制表示：

$$13 = 8 + 4 + 1 = (1101)_2$$

$$100 = 64 + 32 + 4 = (1100100)_2$$

所以，无论 n 多大，最多只需要 ⌊log₂n⌋ + 1 个"倍增步"就能拼出它。

⚡ 复杂度对比

方法	步数/运算次数	n = 10⁹ 时
朴素线性	O(n)	约 10 亿次（超时 TLE ❌）
倍增	O(log n)	约 30 次（飞快 ✅）

🔥 高频考点：倍增法把线性过程 O(n) 加速为对数过程 O(log n)。选择题常问"以下哪个算法利用了倍增思想"或"快速幂的时间复杂度是多少"——答案永远是 O(log 指数)，不是 O(log 底数)！

🔑 倍增法的三件套

任何倍增算法都可以拆成三个固定动作，记住这个框架，后面学 LCA、ST 表都能套用：

环节	做什么	快速幂里的对应	倍增跳跃里的对应
① 定基准	明确"1 步 / 2⁰"是什么	a 本身（a¹）	up[0][i] = nxt[i]
② 翻倍递推	由 2ᵏ⁻¹ 推出 2ᵏ	a = a * a（指数翻倍）	up[j][i] = up[j-1][up[j-1][i]]
③ 拆分使用	把目标按二进制拆开，为 1 的位就取用	if (b & 1) ans *= a	if ((k>>j)&1) s = up[j][s]

🧭 什么样的问题适合倍增？

不是所有问题都能倍增。它要求**"大步"可以由"小步"拼接出来**，即满足"复合性"：

• ✅ 幂运算：a^(2×2ᵏ⁻¹) = a^(2ᵏ⁻¹) × a^(2ᵏ⁻¹)，两步相乘即可；
• ✅ 跳跃/祖先：跳 2ʲ 步 = 跳两个 2ʲ⁻¹ 步，路径首尾相接；
• ✅ 区间最值：长度 2ʲ 的区间 = 两个长度 2ʲ⁻¹ 的区间，最值可以合并；
• ❌ 相邻两步互相冲突、无法拼接的过程（比如带"撤销"且方向不确定的操作），不能直接倍增。

🤔 倍增 vs 二分：别搞混！

两者都是 O(log n)，都是"玩 2 的幂"，但方向相反，选择题常设陷阱：

对比	二分查找	倍增法
动作方向	折半：范围每次缩小一半（n → n/2）	翻倍：步子每次扩大一倍（1 → 2 → 4）
直觉	在电话簿里翻人名，每次撕掉一半	跳远时先试 1 米、再 2 米、4 米……
前提	数据有序，可判断"往左还是往右"	操作可复合拼接（2ᵏ = 两个 2ᵏ⁻¹）
典型应用	二分查找、二分答案	快速幂、LCA、ST 表

一句话记忆：二分是"对半砍"，倍增是"翻着倍往上凑"。

📊 log₂n 速记表（考场估算用）

n 的量级	log₂n 约为	含义
10²	7	100 个数，倍增约 7 步
10⁶	20	百万级数据，倍增约 20 步
10⁹	30	十亿级数据（快速幂常见），约 30 步
10¹⁸	60	long long 上限量级，约 60 步

看到数据范围 n ≤ 10⁹，就能立刻反应：O(log n) ≈ 30 次循环，稳；O(n) ≈ 10 亿次，超时。这正是第 8 期"复杂度分析"的基本功。

---

二、快速幂：倍增思想的"第一战"（必讲）

2.1 问题引入

求 aᵇ mod p。其中 a, b, p 可以很大（比如 b ≤ 10⁹，p ≤ 10⁹+7）。

朴素写法——循环乘 b 次：

// C++：朴素幂，O(b)
long long power(long long a, long long b, long long p) {
    long long ans = 1;
    for (long long i = 0; i < b; i++)
        ans = ans * a % p;
    return ans;
}

b = 10⁹ 时循环 10 亿次，必然超时。

📌 顺便记住几个边界约定：任何数的 0 次方都是 1（a⁰ = 1），所以 b = 0 时快速幂直接返回 1 % p；而 1 % p 这个写法同时兼顾了 p = 1 的特殊情形——任何数 mod 1 都等于 0，若初值直接写 1，在 p = 1 时会错误返回 1。这类"初值取模"细节，是判断题和代码填空的常客。

2.2 倍增推导：以 a¹³ 为例

13 = (1101)₂ = 8 + 4 + 1，所以：

$$a^{13} = a^8 \times a^4 \times a^1$$

而底数平方一次，指数就翻倍：

循环轮次	底数 a 的"身价"	指数 b	b 的最低位	动作
第1轮	a¹	13 (1101)	1	ans ×= a¹；底数平方为 a²；b → 6
第2轮	a²	6 (110)	0	不乘；底数平方为 a⁴；b → 3
第3轮	a⁴	3 (11)	1	ans ×= a⁴；底数平方为 a⁸；b → 1
第4轮	a⁸	1 (1)	1	ans ×= a⁸；底数平方为 a¹⁶；b → 0

最终 ans = a¹ × a⁴ × a⁸ = a¹³ ✔️。只循环了 4 次（= 13 的二进制位数）。

2.3 快速幂模板

// C++11：快速幂 a^b mod p，O(log b)
#include <iostream>
using namespace std;
typedef long long ll;

ll fastPow(ll a, ll b, ll p) {
    ll ans = 1 % p;   // 结果初值为 1；%p 是为了防止 p == 1
    a %= p;           // 底数先取模，防止 a 本身过大
    while (b > 0) {           // 指数还有未处理的二进制位
        if (b & 1)            // 等价于 b % 2 == 1：当前最低位是 1
            ans = ans * a % p;// 把当前"身价"的底数乘进答案
        a = a * a % p;        // 底数平方，身价翻倍：a^1 -> a^2 -> a^4 ...
        b >>= 1;              // 等价于 b /= 2：处理下一个二进制位
    }
    return ans;
}

int main() {
    ll a, b, p;
    cin >> a >> b >> p;
    cout << fastPow(a, b, p) << endl;
    return 0;
}

2.4 逐行解析

代码	含义	为什么这样写
ans = 1 % p	答案初值	a⁰ = 1；% p 防止 p=1 时结果应为 0
a %= p	底数先取模	(a mod p)ᵇ mod p 与 aᵇ mod p 相等，先缩小底数防溢出
if (b & 1)	判断指数最低位	位运算，等价于 b % 2 == 1，更快更地道
ans = ans * a % p	乘入答案	每次乘法后立即取模，防止数值爆炸
a = a * a % p	底数平方	指数翻倍：a^(2ᵏ) → a^(2ᵏ⁺¹)
b >>= 1	指数右移一位	等价于 b /= 2，转去处理更高位
while (b > 0)	循环条件	指数的所有二进制位处理完毕即结束

🔥 真题再现：GESP 八级（2026年3月）单选题第 3 题，给出快速幂代码问时间复杂度，正确答案是 O(log e)（e 为指数）。底数平方多少次，只取决于指数的二进制位数！

2.5 为什么取模可以"边走边取"？

快速幂能在每一步都取模，依据的是同余运算的三条性质（选择题也常考判断）：

性质	公式
加法	(a + b) mod p = [(a mod p) + (b mod p)] mod p
乘法	(a × b) mod p = [(a mod p) × (b mod p)] mod p
幂	aᵇ mod p = (a mod p)ᵇ mod p

正因为乘法对取模"封闭"，我们才能把巨大的 a^(2ᵏ) 始终压缩在 [0, p−1] 范围内，既防溢出又保正确。

⚠️ 注意：减法和除法要小心！减法可能出现负数（C++ 中负数取模结果为负），需要 (x % p + p) % p；而除法在取模意义下要改用"乘法逆元"，那是更高级的数论话题，本章不展开。

2.6 递归版快速幂（分治视角）

倍增与分治是"近亲"：把 b 次幂对半切——

$$a^b = \begin{cases} 1 & b = 0 \\ a^{b/2} \times a^{b/2} & b \text{ 为偶数} \\ a^{b-1} \times a & b \text{ 为奇数} \end{cases}$$

// C++11：递归版快速幂
long long fastPowRec(long long a, long long b, long long p) {
    if (b == 0) return 1 % p;
    long long half = fastPowRec(a, b / 2, p);
    long long ans = half * half % p;      // 两半相乘
    if (b & 1) ans = ans * a % p;         // 奇数再补一个 a
    return ans;
}

递归版与迭代版完全等价，复杂度都是 O(log b)。考场推荐写迭代版（无递归开销、不怕栈深度），但递归版更能体现"对半翻倍"的思想，判断题中可能给出让你识别。

---

三、例题精讲（4 道递进）

📝 例 1：快速幂模板（洛谷 P1226）

题目：输入三个整数 a、b、p，求 aᵇ mod p 的值。（1 ≤ a, b, p ≤ 2×10⁹）

样例输入：

2 10 1000

样例输出：

24

解析：2¹⁰ = 1024，1024 mod 1000 = 24。

解题思路：直接套用 2.3 节快速幂模板。b 最大 2×10⁹，二进制约 31 位，循环 31 次即可。

💡 数据范围估算：朴素写法要循环 b ≤ 2×10⁹ 次，按每秒约 10⁸ 次简单运算估算，需要约 20 秒——远超 1 秒时限，TLE 无疑；快速幂只循环 ⌈log₂b⌉ ≈ 31 次，耗时约 0.00003 秒。这就是 O(n) → O(log n) 在实感上的差距。

参考代码即上方 2.3 节模板（C++ 实现）。

⚠️ 易错点：C++ 中 ans * a 是两个 long long 相乘。当 p ≤ 2×10⁹ 时，乘积最大约 4×10¹⁸ < 9.2×10¹⁸（long long 上限），刚好安全；但如果题目 p 更大（如 10¹⁸ 级别），就需要 __int128 或"快速乘"了。GESP 范围内记住：一律用 long long，每次相乘后立刻 % p。

---

📝 例 2：求 a 的 b 次方的末 k 位

题目：输入 a、b、k，求 aᵇ 的末 k 位（不足 k 位时前面补 0）。

样例输入：

2 100 3

样例输出：

376

解题思路：末 k 位 = aᵇ mod 10ᵏ。这就是快速幂换了个模数！注意前导零要用格式化补零输出。

// C++11
#include <cstdio>
#include <iostream>
using namespace std;
typedef long long ll;

ll fastPow(ll a, ll b, ll mod) {
    ll ans = 1 % mod;
    a %= mod;
    while (b > 0) {
        if (b & 1) ans = ans * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return ans;
}

int main() {
    ll a, b; int k;
    cin >> a >> b >> k;
    ll mod = 1;
    for (int i = 0; i < k; i++) mod *= 10;  // 10^k
    ll ans = fastPow(a, b, mod);
    printf("%0*lld\n", k, ans);  // 不足 k 位时补前导零
    return 0;
}

⚠️ 易错点：末 3 位是 mod 1000，不是 mod 999！且结果可能是 024 这样带前导零的形式，C++ 用 %03lld（或 %0*lld 动态宽度） 输出。

---

📝 例 3：青蛙跳台阶变式 & "凑数"问题（二进制拆分计数）

题目：青蛙从第 0 格出发，每次只能跳 2 的幂次 格（1、2、4、8、16……），要跳到第 n 格，最少要跳几次？

样例：n = 13 → 13 = 8 + 4 + 1，最少跳 3 次。

解题思路：

• 任何 n 都能拆成若干 2 的幂之和（二进制表示）；
• 为什么二进制里 1 的个数就是最少次数？因为两个相同的 2ᵏ 可以合并成一个 2ᵏ⁺¹——最优方案中每个幂次最多用一次，这恰好就是二进制表示。
• 所以答案 = n 的二进制中 1 的个数（popcount）。

💰 同款模型——凑硬币：面值为 1、2、4、8、… 元的硬币各若干，凑 n 元最少需要几枚？答案同样是 popcount(n)。这就是"倍增凑数"。

// C++11：统计二进制中 1 的个数，O(log n)
#include <iostream>
using namespace std;

int main() {
    long long n;
    cin >> n;
    int cnt = 0;
    while (n > 0) {
        cnt += n & 1;   // 最低位是 1 就计数
        n >>= 1;
    }
    cout << cnt << endl;
    return 0;
}

拓展：把拆分方案也打印出来（看看用了哪些"大跨步"）：

long long n = 13;
for (int k = 0; n > 0; k++) {
    if (n & 1) cout << (1LL << k) << " ";  // 输出 1 4 8
    n >>= 1;
}

同模型的常见问法（选择题爱考结论）：

问法	答案
用天平砝码 1、2、4、8…克（每种一个），最多能称多少种整数质量？	1 ~ 2ᵏ⁺¹−1 都能称（二进制全覆盖）
n 颗药，每天吃的数量必须是 2 的幂，最少几天吃完？	popcount(n) 天
1~1000 中，二进制里恰有 3 个 1 的数有多少个？	C(10,3) = 120（组合数 + 二进制，第3期知识联动）

💡 注意区分：如果每种 2ᵏ 步长可以用任意多次（比如普通青蛙跳 1 或 2 格），那是动态规划问题；"每个大步最多用一次、求最少次数"才是二进制拆分题。审题时盯住"步长种类"和"使用次数限制"。

---

📝 例 4：倍增跳跃——线性表上的 2ᵏ 步跳跃（LCA / ST 表 · 📚 拓展 · 超纲）

题目：有 n 个位置（1~n），每个位置 i 有一个固定"下一跳" nxt[i]。共 m 次询问，每次问：从位置 s 出发，连续跳 k 步，到达哪个位置？（n, m ≤ 10⁵，k ≤ 10⁹）

朴素做法：每次询问模拟跳 k 步 → O(mk)，m 和 k 都上亿，严重超时。

倍增做法（三步）：

步骤	内容	公式
① 预处理基准	up[0][i]：从 i 跳 2⁰=1 步到哪	up[0][i] = nxt[i]
② 倍增递推	up[j][i]：从 i 跳 2ʲ 步到哪	up[j][i] = up[j-1][ up[j-1][i] ]
③ 查询拆分	把 k 拆成二进制，为 1 的位就跳对应大步	逐位检查 k

🧩 递推直觉：跳 2ʲ 步 = 先跳 2ʲ⁻¹ 步，再跳 2ʲ⁻¹ 步。跳两次"半程"拼成一个"全程"！

预处理 O(n log k)，每次询问 O(log k)，总复杂度 O((n+m) log k)。

// C++11
#include <iostream>
using namespace std;

const int MAXN = 100005;
const int LOG = 31;          // log2(1e9) ≈ 30，留 31 层足够
int up[LOG][MAXN];           // up[j][i]：从 i 跳 2^j 步到达的位置

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> up[0][i];   // 跳 1 步

    for (int j = 1; j < LOG; j++)                    // 倍增预处理
        for (int i = 1; i <= n; i++)
            up[j][i] = up[j-1][ up[j-1][i] ];

    while (m--) {
        int s; long long k;
        cin >> s >> k;
        for (int j = 0; j < LOG; j++)
            if ((k >> j) & 1)        // k 的第 j 个二进制位为 1
                s = up[j][s];        // 就跳一个 2^j 的大步
        cout << s << "\n";
    }
    return 0;
}

🔭 延伸阅读（📚 拓展 · 超纲）：把这道题的"线性表/函数图"换成"一棵树"，up[0][i] 定义为"父亲"，up[j][i] 就是节点 i 的 2ʲ 级祖先——这就是竞赛高频考点 倍增求 LCA（最近公共祖先）——不在八级考纲内，了解思想即可！而"区间起点 i、长度 2ʲ 的区间最值"用同样的递推预处理，就是 ST 表（RMQ 区间最值查询）：预处理 O(n log n)、查询 O(1)。判断题已考过这个结论，务必记牢！

🚀 番外：快速幂思想还能"乘"什么？

快速幂的"倍增"对象不只是数字。只要一种运算满足结合律，就能套用同一套模板：

• 矩阵快速幂（📚 拓展 · 超纲）：把底数 a 换成矩阵，乘法换成矩阵乘法，可以 O(log n) 求斐波那契数列第 n 项——递推式 [F(n+1), F(n)]ᵀ = A × [F(n), F(n−1)]ᵀ 中的矩阵 A 自乘 n 次即可；
• 线性变换 / 置换的复合：对同一操作执行 k 次，也能倍增预处理。

这已经是 GESP 之上的竞赛内容，但理解"倍增模板与具体运算无关"这一点，对八级选择题中"这段代码的复杂度/功能"类题目非常有帮助。

---

四、⚠️ 易错点清单

#	易错点	正确做法
1	用 int 存乘法结果导致溢出	C++ 一律 long long；相乘后立刻 % p
2	忘记取模或最后才取模，中间数值爆炸	每一步乘法后立即 % p：ans = ans * a % p
3	ans 初值写成 1 后直接返回	写 1 % p，防止 p = 1 时答案应为 0
4	循环条件写成 while (b > 1)，漏掉最高位	必须是 while (b > 0)，处理完所有二进制位
5	位运算写错：b & 1 误写为 b && 1	& 是按位与，&& 是逻辑与，语义完全不同
6	混淆 >> 与 >>=	右移后要赋值：b >>= 1（等价 b /= 2）
7	以为复杂度是 O(log a)	快速幂复杂度是 O(log b)（指数的位数）
8	倍增表层数 LOG 开太小	k ≤ 10⁹ 时 log₂ ≈ 30，LOG 取 31 或 32；数组开大一点点没关系
9	递推 up[j][i] 时 j、i 循环顺序写反	先枚举 j（层数）再枚举 i，因为第 j 层依赖第 j-1 层

🔥 高频考点速记：

• 快速幂时间复杂度 O(log b)；倍增跳跃/LCA 预处理 O(n log n)，单次查询 O(log n)；
• ST 表预处理 O(n log n)，区间查询 O(1)；
• 任何正整数都能拆成若干个 2 的幂之和（二进制表示唯一）；
• "凑数/跳格子最少次数" = 二进制中 1 的个数。

口诀速记：

🎵 底数平方指数移，低位是 1 乘进去；long long 不能忘，步步取模保平安；循环终止看指数，归零收工 ans 出。

---

五、备考建议

1. 模板先背后理解：快速幂模板只有 8 行核心代码，建议 默写 3 遍，做到肌肉记忆；
2. 动手模拟：拿 a³、a¹³ 这种小指数，手动画出"底数平方 + 指数右移"的表格，选择题秒杀；
3. 盯住三个 1：ans = 1 % p、if (b & 1)、while (b > 0)——这是阅卷视角最常见的扣分点；
4. 建立"倍增条件反射"：以后看到"跳 k 步 / 第 k 个祖先 / 长度 2ʲ 的区间"，立刻想到 up[j][i] = up[j-1][up[j-1][i]] 这个递推式；
5. 错题归因：倍增相关的失分几乎集中在三处——复杂度记成 O(log a)、乘法忘记 long long 而溢出、循环条件 while (b > 0) 写成 while (b > 1)。把这三行抄在错题本扉页，考前看一眼，本章分数就稳了。

---

六、📝 实战练习

练习题 1（单选题）

题目： 用快速幂算法计算 a²⁰ 时，底数 a 会被平方多少次？（ ）

A. 4 次
B. 5 次
C. 10 次
D. 20 次

🔑 点击查看答案与解析

答案： B。20 = (10100)₂，共 5 个二进制位，循环执行 5 次（每次都平方底数，共 5 次），与指数大小无关、只与位数有关。

---

练习题 2（单选题）

题目： ST 表（稀疏表，用于 RMQ 区间最值查询）的单次查询时间复杂度是？（ ）

A. O(n)
B. O(log n)
C. O(1)
D. O(n log n)

🔑 点击查看答案与解析

答案： C。ST 表（RMQ）查询区间最值是 O(1)：用两个长度为 2ʲ 的重叠区间覆盖目标区间，直接取两个最值的最值，不需要逐位跳。这正是 GESP 八级判断题考过的结论。

---

练习题 3（判断题）

题目： 在快速幂算法中，底数 a 和答案变量 ans 都可以用 int 类型存储，不会出现溢出问题。（ ）

🔑 点击查看答案与解析

答案： 错误（✗）。a、ans 均可达 10⁹ 量级，乘积可达 10¹⁸，远超 int 上限（约 2.1×10⁹），必须用 long long 承接乘法结果。

---

练习题 4（单选题）

题目： 快速幂算法的时间复杂度是？（ ）

A. O(a)
B. O(b)
C. O(log a)
D. O(log b)

🔑 点击查看答案与解析

答案： D

解析： 快速幂的时间复杂度是 O(log b)，其中 b 是指数。

因为循环次数等于指数 b 的二进制位数。比如 b = 13（二进制 1101），循环 4 次 = log₂13 ≈ 3.7。

注意：不是 O(log a)！a 是底数，和循环次数无关。

选 D。

🔥 高频考点：快速幂复杂度是 O(log 指数)，不是 O(log 底数)！

---

练习题 5（判断题）

题目： 快速幂算法中，答案变量 ans 的初始值应该设为 0。（ ）

🔑 点击查看答案与解析

答案： 错误 ❌

解析： 快速幂中 ans 的初始值应该是 1，不是 0。

为什么？因为快速幂是乘法运算，乘法的单位元是 1（任何数乘 1 等于它本身）。

• ans = 1（乘法单位元）
• 每次乘上对应的 a^(2^k)

如果初始值是 0，那最后结果永远是 0（0 乘任何数都是 0）。

💡 类比：累加初始值是 0（加法单位元），累乘初始值是 1（乘法单位元）。

---

练习题 6（判断题）

题目： b & 1 的作用是？（ ）

A. 将 b 加 1
B. 将 b 乘 2
C. 判断 b 的最低位是不是 1
D. 将 b 右移一位

🔑 点击查看答案与解析

答案： C

解析：b & 1 是按位与运算，作用是取 b 的最低位（判断奇偶）。

• 如果最低位是 1（b 是奇数），结果为 1（真）
• 如果最低位是 0（b 是偶数），结果为 0（假）

在快速幂中，if (b & 1) 就是判断"当前二进制位是不是 1"，如果是 1 就要把对应的 a^(2^k) 乘到结果里。

其他选项：

• B：b <<= 1（左移）才是乘 2
• D：b >>= 1（右移）才是除以 2

选 C。

💡 记忆：& 1 = 看最后一位。

---

练习题 7（判断题）

题目： 计算快速幂时，每次乘法后都要取模，否则可能溢出。（ ）

🔑 点击查看答案与解析

答案： 正确 ✅

解析： 快速幂中，底数 a 每次都平方，增长非常快。即使 a 和 p 都在 int 范围内（约 10⁹），a × a 也能达到 10¹⁸，远远超出 int 的范围（约 2×10⁹）。

所以：

1. 变量要用 long long 类型
2. 每次乘法后都要 取模（(a * b) % p）

模运算性质：(a × b) % p = [(a % p) × (b % p)] % p

🔥 高频考点：快速幂的溢出问题是判断题和代码填空题的常客。记住：用 long long，每步取模！

---

练习题 8（编程题）

题目： 实现快速幂：给定 a, b, p，计算 a^b mod p。

输入：三个整数 a, b, p
输出：a^b mod p 的值

样例输入：2 10 1000
样例输出：24

🔑 点击查看答案与解析

答案：

#include <iostream>
using namespace std;

long long qpow(long long a, long long b, long long p) {
    long long ans = 1 % p;   // 初始值1，先取模防止p=1的情况
    a %= p;                  // 底数先取模
    while (b > 0) {
        if (b & 1) {          // 最低位是1
            ans = ans * a % p; // 乘上当前a^(2^k)
        }
        a = a * a % p;        // 底数平方
        b >>= 1;              // 指数右移一位
    }
    return ans;
}

int main() {
    long long a, b, p;
    cin >> a >> b >> p;
    cout << qpow(a, b, p) << endl;
    return 0;
}

解析： 快速幂核心三步（每次循环）：

1. 看最低位：if (b & 1) → 是 1 就乘 ans
2. 底数平方：a = a * a % p → a 变成 a², a⁴, a⁸...
3. 指数右移：b >>= 1 → 处理下一位

样例验证：2^10 = 1024，1024 mod 1000 = 24 ✓

🔥 必背模板：快速幂只有 8 行核心代码，一定要背下来！记住"ans=1，while(b>0)，看位、平方、右移"。

---

练习题 9（程序阅读题）

题目： 用快速幂计算 pow(3, 13, 7)（即 3¹³ mod 7），请逐步分析并回答：

（1）循环共执行多少次？
A. 3 次　　B. 4 次　　C. 5 次　　D. 13 次

（2）最终结果是多少？（提示：先口算 3^k mod 7 的规律）
A. 3　　B. 5　　C. 6　　D. 1

🔑 点击查看答案与解析

答案： （1）B　（2）A

解析：（1）循环次数：

13 的二进制是 1101，共 4 位，所以循环执行 4 次。

选 B。

（2）逐步计算 3¹³ mod 7：

先列出 3 的幂 mod 7 的值：

• 3¹ mod 7 = 3
• 3² mod 7 = 9 mod 7 = 2
• 3⁴ mod 7 = (3²)² mod 7 = 2² = 4
• 3⁸ mod 7 = (3⁴)² mod 7 = 4² = 16 mod 7 = 2

13 = 8 + 4 + 1（二进制 1101），所以： 3¹³ = 3⁸ × 3⁴ × 3¹

mod 7： = 2 × 4 × 3 mod 7 = 24 mod 7 = 3

选 A。

快速幂完整执行过程：

轮次	b (二进制)	b最低位	ans	a (底数)
初始	1101	-	1	3
第1轮	1101	1	1×3=3	3²=2
第2轮	110	0	3 (不变)	2²=4
第3轮	11	1	3×4=12→5	4²=2
第4轮	1	1	5×2=10→3	2²=4

最终 ans = 3，与我们的计算一致 ✓

💡 手算小指数快速幂是选择题的常考题型，掌握"二进制拆分 + 逐位处理"的思路就能秒杀。

---

练习题 10（单选题）

题目： 关于矩阵快速幂求斐波那契数列第 n 项，下列说法错误的是？

A. 矩阵快速幂的时间复杂度是 O(log n)
B. 其核心思想是利用转移矩阵的 n 次幂来计算第 n 项
C. 矩阵快速幂比递推法更快，所以所有情况下都应该用矩阵快速幂
D. 当 n 达到 10⁹ 时，递推法会超时，矩阵快速幂仍可处理

🔑 点击查看答案与解析

答案： C

解析：

• A 正确：矩阵快速幂每次矩阵乘法是 O(1)（2×2矩阵只有8次乘法），共 log n 次，总复杂度 O(log n)
• B 正确：利用恒等式 [[F(n+1), F(n)], [F(n), F(n-1)]] = [[1,1],[1,0]]^n，通过矩阵自乘 n 次得到结果
• C 错误 ❌："所有情况下都应该用"太绝对。当 n 较小时（如 n ≤ 10⁶），递推法代码更简单、常数更小，反而更实用。矩阵快速幂只有在 n 非常大（如 n ≥ 10⁹）时才体现优势
• D 正确：递推法 O(n) 在 n=10⁹ 时需要跑 10 亿次（约 10 秒），必然超时；矩阵快速幂 O(log n) 只需约 30 次矩阵乘法，瞬间完成

🎯 核心思想：算法选择要看数据规模。n 小的时候用简单方法，n 大的时候用高级方法。没有"最好"的算法，只有"最合适"的算法。

---

练习题 11（判断题）

题目： 倍增法和二分查找都是 O(log n) 的算法，它们的核心思想是一样的，都是"每次把规模折半"。（ ）

🔑 点击查看答案与解析

答案： 错误 ❌

解析： 两者虽然都是 O(log n)，但方向和思想相反：

对比	二分查找	倍增法
方向	折半缩小：从大到小，每次范围砍一半	翻倍增大：从小到大，每次步子翻一倍
直觉	翻电话簿找名字，每次撕掉一半	跳远先试 1 米、再 2 米、4 米……凑目标
前提	数据有序，可判断"该往左还是往右"	操作可复合拼接（2ᵏ = 两个 2ᵏ⁻¹）
典型应用	二分查找、二分答案	快速幂、LCA、ST 表

一句话记忆：二分是"对半砍"，倍增是"翻着倍往上凑"。

🔥 考试陷阱：选择题常把倍增和二分混在一起考，问"以下哪个说法正确"。记住：两者都是 O(log n)，但方向相反、前提不同、应用场景不同。

---

七、📊 考点总结表

考点	重要程度	出题形式	易错点
倍增核心思想	⭐⭐⭐⭐⭐	选择/判断	二进制拆分，O(log n)
快速幂模板	⭐⭐⭐⭐⭐	编程题/代码填空	ans初始为1，不是0
快速幂时间复杂度	⭐⭐⭐⭐⭐	选择/判断	O(log b)，不是O(log a)
位运算 b&1	⭐⭐⭐⭐⭐	选择/代码填空	取最低位，判断奇偶
位运算 b>>=1	⭐⭐⭐⭐⭐	代码填空/选择	右移一位，除以2
取模防溢出	⭐⭐⭐⭐⭐	选择/编程/判断	用long long，每步取模
LCA倍增	⭐⭐⭐⭐	选择/判断	up[j][i] = 2^j级祖先
RMQ/ST表	⭐⭐⭐⭐	选择/判断	预处理O(nlogn)，查询O(1)
循环条件	⭐⭐⭐⭐	代码填空/判断	while(b>0)不是while(b>1)
模运算性质	⭐⭐⭐⭐	选择/判断	(ab)%p = [(a%p)(b%p)]%p

---

⭐ 必背速记卡

┌─────────────────────────────────────────────┐
│         倍增法 · 必背速记卡                 │
├─────────────────────────────────────────────┤
│  1. 倍增核心：二进制拆分，O(log n)           │
│  2. 快速幂求 a^b mod p，时间O(log b)        │
│  3. 复杂度是O(log指数)，不是O(log底数)       │
│  4. ans初始值 = 1（乘法单位元）             │
│  5. while (b > 0)，不是while(b>1)          │
│  6. b & 1：取最低位，判断奇偶               │
│  7. b >>= 1：右移一位，除以2                │
│  8. 每次循环：看位→平方→右移                │
│  9. a = a * a % p（底数平方）               │
│ 10. ans = ans * a % p（乘到结果）           │
│ 11. 用long long防止乘法溢出                 │
│ 12. 每步都要取模                           │
│ 13. LCA：up[j][i] = i的2^j级祖先            │
│ 14. ST表/RMQ：预处理O(nlogn)，查询O(1)     │
│ 15. 倍增 = 预处理2的幂 + 拼二进制           │
└─────────────────────────────────────────────┘

---