← 目录 / 算法文档 · 模块一 数学基础 / 1.7 快速幂

1.7　快速幂

借助上一节学过的二进制，把算 a 的 b 次方从"乘 b 次"变成"乘几十次"。

本页目录
① 什么是快速幂

快速幂解决的问题很简单：算 a 的 b 次方（ab），但要算得比直接乘 b 次快得多。比如 2 的 13 次方，最直接的办法是把 2 连续乘 13 次；如果 b 变成一百万，直接乘一百万次就太慢了。这一节要解决的，就是怎么用少得多的乘法次数，算出同样的结果。

② 基础写法：累乘 b 次

最直接的想法：用一个变量保存结果，循环 b 次，每次都乘上一个 a。

C++ · 朴素写法：连续乘 b 次
1long long FastPow(long long a, long long b)
2{
3 long long result = 1;
4 for (long long i = 0; i < b; i++)
5 {
6 result *= a;
7 }
8 return result;
9}

算 2 的 13 次方，这种写法要循环 13 次，做 13 次乘法。如果 b 是一百万，就要做一百万次乘法——这就是要优化的地方。

③ 优化：按二进制位决定乘不乘

上一节学过，任何一个数都能拆成若干个 2 的次方相加——这正是二进制的意义。13 拆开就是 8 + 4 + 1（二进制 1101）。指数也是数字，同样可以这么拆：

把指数 13 拆成二进制 —— 哪些"翻倍幂"需要乘进去
1
a8
第4位
1
a4
第3位
0
a2
第2位
1
a1
第1位
13 = 8 + 4 + 1　→　a13 = a8 × a4 × a1
13 的二进制是 1101——绿色格子（位是 1）对应的"翻倍幂"要乘进最终结果，灰色虚线格子（位是 0）对应的直接跳过。a1、a2、a4、a8 这一串"翻倍幂"，每一个都只需要把前一个平方一次就能得到——这正是快速幂比朴素写法快的根本原因：用很少的几次"平方"，就能凑出任意大小的指数。
C++ · 快速幂（迭代写法）
1long long FastPow(long long a, long long b)
2{
3 long long result = 1;
4 while (b > 0)
5 {
6 if (b % 2 == 1) // 当前最低位是 1，要乘进去
7 {
8 result *= a;
9 }
10 a *= a; // a 翻倍：a, a², a⁴, a⁸, ...
11 b /= 2; // 处理下一个二进制位
12 }
13 return result;
14}

每一轮循环，b % 2 看的正好是 b 当前最低位的二进制——和 1.1、1.6 节拆数字的方式一模一样，只是这里是对 b 做"二进制版的拆数字"。a 每轮自己翻倍（平方一次），b 每轮除以 2（去掉已经处理过的那一位）。用 FastPow(2, 13) 走一遍：

FastPow(2, 13) 的执行过程
b末位是否乘进 resultresulta（下一轮的值）
131乘：1×222×2=4
60跳过24×4=16
31乘：2×163216×16=256
11乘：32×2568192256×256=65536
b 变成 0，循环结束 —— result = 8192
只用了 4 轮循环、4 次平方，外加 3 次乘进 result，一共 7 次乘法，就算出了 213 = 8192——比朴素写法的 13 次乘法明显更少，而且 b 越大，省下来的乘法次数差距会越夸张。
📌
递归写法同样很自然："算 a 的 b 次方"可以转化成"先算 a 的 b/2 次方，再把结果平方一次；如果 b 是奇数，平方完之后再多乘一个 a"——这正是把问题规模直接砍半，和前面学过的递归思路完全一致：
C++ · 快速幂（递归写法）
1long long FastPow(long long a, long long b)
2{
3 if (b == 0) return 1; // 递归出口：任何数的0次方是1
4 long long half = FastPow(a, b / 2);
5 if (b % 2 == 0)
6 {
7 return half * half;
8 }
9 else
10 {
11 return half * half * a;
12 }
13}
FastPow(2, 13) 的递归调用链
FastPow(2, 13)
调用
↓
FastPow(2, 6)
调用
↓
FastPow(2, 3)
调用
↓
FastPow(2, 1)
调用
↓
FastPow(2, 0)
b == 0，递归到底 —— 直接返回 1
FastPow(2,1) 收到 half=1（b 是奇数）→ 返回 1×1×2 = 2
FastPow(2,3) 收到 half=2（b 是奇数）→ 返回 2×2×2 = 8
FastPow(2,6) 收到 half=8（b 是偶数）→ 返回 8×8 = 64
FastPow(2,13) 收到 half=64（b 是奇数）→ 返回 64×64×2 = 8192
每一层调用，指数都直接砍掉一半（b / 2），只需要 4 层调用就从 13 走到了 0——这和迭代版本"每轮循环 b 除以 2"是同一个过程，只是用函数调用代替了循环。
④ 模运算版本：避免数字爆炸

竞赛题里很少会让你算出 ab 真实的值——因为这个数往往大得惊人，连 long long 都装不下。比如 730，真实值有 26 位数字，远远超过 long long 能表示的范围（约 19 位数字）。所以题目通常会要求"答案对某个数取模"，比如"ab mod 1000000007"——这样答案永远是一个不大的数，不会溢出。

⚠️
诀窍：每一步都顺手取模，而不是算到最后再取模。取模运算有一个好用的性质：(x × y) mod m 和 ((x mod m) × (y mod m)) mod m 结果完全一样。也就是说，只要保证参与乘法的两个数本身都不大，乘积自然也不会大到溢出——所以只需要在每次乘法之后立刻取模，把数字"压"回一个安全的范围，而不是等最后数字已经爆炸了再处理（那时候已经晚了）。
C++ · 快速幂（带模运算）
1long long FastPow(long long a, long long b, long long mod)
2{
3 long long result = 1;
4 a %= mod; // 一开始先把 a 压到 mod 范围内
5 while (b > 0)
6 {
7 if (b % 2 == 1)
8 {
9 result = result * a % mod;
10 }
11 a = a * a % mod;
12 b /= 2;
13 }
14 return result;
15}

和不取模的版本相比，只多了三处 % mod：开头压一次 a，每次乘进 result 之后压一次，每次 a 自己翻倍之后再压一次。用 FastPow(7, 13, 1000) 走一遍（求 713 的末三位）：

FastPow(7, 13, 1000) 的执行过程 —— 数字始终保持在 1000 以内
b末位是否乘进 resultresulta（已取模）
131乘：1×7%100077×7%1000=49
60跳过749×49%1000=401
31乘：7×401%1000807401×401%1000=801
11乘：807×801%1000407801×801%1000=601
b 变成 0，循环结束 —— result = 407（即 713 mod 1000 = 407）
全程参与乘法的两个数都没有超过 1000，所以乘积最大也只有约 1000×1000=100万，long long 轻松装得下——而 713 真实的值是 96889010407，如果不取模直接硬乘，数字会越滚越大。
⑤ 完整代码与对比

用 b = 1000 数一数两种写法各需要多少次乘法：

算 a 的 1000 次方 —— 两种写法的乘法次数对比
朴素写法
999 次
快速幂
约 10 次
朴素写法要循环 999 次；快速幂只需要把 1000 不断除以 2 直到变成 0，大约 10 轮就能搞定——b 越大，这个差距越惊人：b 是十亿时，朴素写法要循环近十亿次，快速幂大约还是只需要 30 轮左右。
写法核心思路时间复杂度
朴素写法循环 b 次，每次乘一个 aO(b)
快速幂按 b 的二进制位决定要不要乘，a 每轮自己平方O(log b)
🎯
快速幂几乎是后面很多算法的"零件"——矩阵快速幂（把数字换成矩阵，同样的拆解思路）、模意义下求逆元（要用到快速幂算 amod-2）都直接建立在这一节的基础上。记住"按二进制位决定乘不乘，底数每轮自己平方"这个骨架，比死记代码更重要。