快速幂

引入

要求 a^b，最朴素的做法是把 a 连乘 b 次，时间复杂度为 O(b)。

当 b 很大时，这种做法显然不太行。

比如要求 2¹⁰⁹，总不能真的乘十亿次。

这时就需要用到快速幂。

---

快速幂的核心思想其实很简单：

把指数 b 拆成二进制，只保留有贡献的若干项。

这样就可以把时间复杂度优化到 O(log b)。

基本思想

先考虑一个例子： 3¹³

因为 13 = (1101)₂ = 8 + 4 + 1 所以有 3¹³ = 3^{8 + 4 + 1} = 3⁸ × 3⁴ × 3¹

于是问题就转化成：

• 如何快速求出 3¹, 3², 3⁴, 3⁸, ⋯
• 如何选出真正需要乘进去的那些项

而这两个问题都很好解决。

因为 a² = a × a a⁴ = (a²)² a⁸ = (a⁴)²

也就是说，每次把当前结果平方，就可以得到下一个 2 的幂次。

所以我们只需要不断平方，同时看指数当前这一位是否为 1 即可。

递归理解

从递归角度看，也很自然。

设我们要求 a^b。

当 b 为偶数时

如果 b = 2k，那么 a^b = a^2k = (a^k)²

当 b 为奇数时

如果 b = 2k + 1，那么 a^b = a^2k + 1 = a × (a^k)²

于是就得到了递归写法：

lint qpow(lint a, lint b) {
  if (b == 0) return 1;
  lint t = qpow(a, b / 2);
  if (b % 2 == 0) return t * t;
  return t * t * a;
}

这样的时间复杂度满足 所以时间复杂度为 O(log b)。

当然，上面的代码在数值很大时可能溢出，而且很多题目还要求取模，所以实际更常用迭代写法。

迭代实现

快速幂最常见的是下面这种写法：

lint qpow(lint a, lint b) {
  lint res = 1;
  while (b) {
    if (b & 1) res = res * a;
    a = a * a;
    b >>= 1;
  }
  return res;
}

这段代码在干什么？

设当前指数 b 的二进制表示为 b = (⋯b₂b₁b₀)₂

那么循环每进行一次：

• b & 1：判断当前最低位是否为 1
• 如果是 1，就把当前的 a 乘进答案里
• 然后令 a = a * a，表示幂次翻倍
• 再令 b >>= 1，把指数右移一位，继续处理下一位

整个过程本质上就是在枚举 b 的二进制位。

取模快速幂

在竞赛题里，更常见的是求 a^b mod  p

这时只需要在乘法的过程中不断取模即可。

根据模运算性质： (x × y) mod  p = ((x mod  p) × (y mod  p)) mod  p

所以可以写成：

lint qpow(lint a, lint b, lint p) {
  lint res = 1;
  a %= p;
  while (b) {
    if (b & 1) res = res * a % p;
    a = a * a % p;
    b >>= 1;
  }
  return res;
}

时间复杂度仍然是 O(log b)。

正确性理解

设初始时要求的是 a^b。

在算法执行过程中，维护这样一个不变量： res × a^b 的值始终等于初始的目标值。

为什么？

• 如果当前 b 是奇数，那么先把一个 a 乘到 res 上，于是指数少掉一个。
• 接着把底数平方，并把指数除以 2。

因为：

若 b = 2k，则 a^b = a^2k = (a²)^k

若 b = 2k + 1，则 a^b = a × a^2k = a × (a²)^k

所以每一步变换都是合法的。

最后当 b = 0 时，有 a⁰ = 1 于是答案就只剩下 res。

例题演示

求 3¹³ mod  100

初始：

• res = 1
• a = 3
• b = 13

第一次循环

13 是奇数，所以：

• res = 1 * 3 = 3
• a = 3 * 3 = 9
• b = 13 >> 1 = 6

第二次循环

6 是偶数，所以：

• res 不变，还是 3
• a = 9 * 9 = 81
• b = 6 >> 1 = 3

第三次循环

3 是奇数，所以：

• res = 3 * 81 = 243 \equiv 43 \pmod{100}
• a = 81 * 81 = 6561 \equiv 61 \pmod{100}
• b = 3 >> 1 = 1

第四次循环

1 是奇数，所以：

• res = 43 * 61 = 2623 \equiv 23 \pmod{100}
• a = 61 * 61 \equiv 21 \pmod{100}
• b = 0

循环结束，答案为 3¹³ mod  100 = 23

应用

快速幂的用途非常广。

1. 求大次幂取模

这是最直接的用途。

例如：

• 求 a^b mod  p
• 求 2ⁿ mod  p
• 求组合数公式中的幂

2. 求乘法逆元

当 p 为质数且 a ≢ 0 (mod  p) 时，由费马小定理： a^p − 1 ≡ 1 (mod  p) 所以 a^p − 2 ≡ a⁻¹ (mod  p)

因此可以用快速幂求逆元：

lint inv(lint a, lint p) {
  return qpow(a, p - 2, p);
}

3. 矩阵快速幂

如果把乘法从“整数乘法”推广到“矩阵乘法”，就得到矩阵快速幂。

它可以用来优化某些递推，例如斐波那契数列。

本质上，快速幂并不关心你乘的到底是什么，只要这种运算满足结合律即可。

4. 快速求函数复合 / 倍增思想

有些问题里，操作执行 2^k 次的结果可以从执行 2^k − 1 次推出。

这种时候本质上也和快速幂很像。

所以很多“倍增”算法，思想源头都和快速幂一致。

代码模板

普通快速幂

#include <bits/stdc++.h>
using lint = long long;

lint qpow(lint a, lint b) {
  lint res = 1;
  while (b) {
    if (b & 1) res = res * a;
    a = a * a;
    b >>= 1;
  }
  return res;
}

取模快速幂

#include <bits/stdc++.h>
using lint = long long;

lint qpow(lint a, lint b, lint p) {
  lint res = 1;
  a %= p;
  while (b) {
    if (b & 1) res = res * a % p;
    a = a * a % p;
    b >>= 1;
  }
  return res;
}

注意事项

1. 指数不能写成负数

上面的快速幂模板通常只讨论 b ≥ 0 的情况。

如果出现负指数，需要先看题目背景，一般会转化成逆元问题，而不是直接套快速幂。

2. 小心溢出

如果 a 和 p 很大，那么

a * a

可能会爆 long long。

这时可能需要使用：

• __int128
• 快速乘
• 或题目给出的特殊模数性质

例如：

using i128 = __int128_t;

lint qpow(lint a, lint b, lint p) {
  lint res = 1;
  a %= p;
  while (b) {
    if (b & 1) res = (i128)res * a % p;
    a = (i128)a * a % p;
    b >>= 1;
  }
  return res;
}

3. 0⁰ 的讨论

在很多编程题里，如果调用 qpow(a, 0)，通常直接返回 1。

这是一种算法约定，和组合数学里的约定保持一致，方便统一处理。

具体题目如果有特殊说明，就按题意来。

例题

洛谷 P1226 【模板】快速幂||取余运算

题意：求 b^p mod  k

直接套快速幂模板即可。

#include <bits/stdc++.h>
using lint = long long;

lint qpow(lint a, lint b, lint p) {
  lint res = 1;
  a %= p;
  while (b) {
    if (b & 1) res = res * a % p;
    a = a * a % p;
    b >>= 1;
  }
  return res;
}

int main() {
  std::cin.tie(0)->sync_with_stdio(0);
  lint b, p, k;
  std::cin >> b >> p >> k;
  std::cout << b << '^' << p << " mod " << k << '=' << qpow(b, p, k) << '\n';
  return 0;
}

总结

快速幂的本质就一句话：

利用二进制拆分指数，把原本需要做 b 次的乘法，优化成 log b 次。

它看起来只是一个模板，但实际上非常重要。

很多算法中的“倍增”“重复平方法”“矩阵幂优化”，本质上都和它有关系。

所以这玩意不只是要会背，更要知道它为什么对。