快速幂

一句话算法

快速幂把指数拆成二进制：当前位是 1 就乘进答案，底数每轮自乘一次。

问题模型

给定整数 $a,b,m$，要求快速计算：

如果直接做 $b$ 次乘法，时间复杂度是 $O(b)$。当 $b$ 达到 $10^9$ 或更大时，这个做法不可接受。

快速幂利用指数的二进制表示，把乘法次数降到 $O(\log b)$。

核心直觉

任意非负整数 $b$ 都能唯一写成若干个不同的 $2$ 的幂之和。例如：

所以：

而这些 $a^{2^i}$ 可以通过不断平方得到：

因此我们只需要从低位到高位扫描 $b$ 的二进制：

• 当前二进制位是 1：把当前 base 乘进答案。
• 每扫描一位：base = base * base，进入下一位的权值。

算法步骤

1. 令 ans = 1 % mod。
2. 令 base = base % mod。
3. 当 exp > 0：
   • 如果 exp & 1，说明当前最低位是 1，执行 ans = ans * base % mod。
   • 执行 base = base * base % mod。
   • 执行 exp >>= 1，删掉已经处理的最低位。
4. 返回 ans。

算法证明

核心不变量：每一轮开始时，尚未处理的指数部分仍然由 exp 表示，已经处理且需要保留的幂已经乘进 ans。

设原指数为：

其中 $c_i\in\{0,1\}$。

1. 第 $i$ 轮时，base 等于：

   $$a^{2^i}$$

2. 若第 $i$ 位 $c_i=1$，答案中必须包含这一项，所以乘入：

   $$ans \leftarrow ans \cdot a^{2^i}$$

3. 若第 $i$ 位 $c_i=0$，答案中不需要这一项，跳过即可。

4. 每一轮后：

   $$(a^{2^i})^2=a^{2^{i+1}}$$

   所以 base = base * base 正确进入下一位。

所有二进制位处理完后，ans 中正好乘入了所有 $c_i=1$ 的项，因此：

算法正确。

复杂度分析

• 时间复杂度：$O(\log b)$。
• 空间复杂度：$O(1)$。

如果 base * base 可能超过 long long，需要使用 __int128 或快速乘。

代码实现

        
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

        #include <bits/stdc++.h>
using namespace std;

using ll = long long;

// 计算 base^exp mod mod，要求 mod > 0。
ll quick_pow(ll base, ll exp, ll mod) {
    ll ans = 1 % mod;
    base %= mod;

    while (exp > 0) {
        if (exp & 1) ans = ans * base % mod;
        base = base * base % mod;
        exp >>= 1;
    }

    return ans;
}

int main() {
    ll base, exp, mod;
    cin >> base >> exp >> mod;
    cout << quick_pow(base, exp, mod) << "\n";
    return 0;
}
    

测试用例

输入：

2 13 1000

输出：

192

解释：

应用分类详解

快速幂的本质是：把“重复乘很多次”变成“按二进制选择若干个平方项”。只要题目出现大指数、重复合成、幂取模，就应该想到快速幂。

一、大指数幂取模

典型模式： 计算 $a^b\bmod m$，其中 $b$ 很大。

识别信号： 题面出现“幂”“取模”“指数很大”“$b\le 10^9$ 或更大”。

核心建模： 用二进制拆指数，每一位只处理一次。

二、数论公式中的幂

典型模式： 公式里包含 $a^k$，但最终只关心模意义下的结果。

识别信号： 出现“费马小定理”“逆元”“组合数取模”“矩阵快速幂前置知识”。

核心建模： 把公式中的幂计算交给快速幂。

三、重复操作的快速合成

典型模式： 一个操作需要重复执行 $b$ 次，且操作可以合并。

识别信号： 出现“重复执行很多次”“函数复合”“状态转移很多步”。

核心建模： 把乘法换成更一般的“合并操作”。如果操作满足结合律，就可以按二进制倍增。

经典例题

1. luogu-P1226

快速幂模板题。直接套用 quick_pow(base, exp, mod)。

2. luogu-P3811

线性逆元是更优解，但快速幂求单个逆元是必须掌握的基础方法。

3. luogu-P1962

斐波那契数列的矩阵快速幂做法。本质仍然是“指数二进制拆分”，只是乘法对象从整数变成矩阵。

参考

• 旧版文章：Rbook_ejs_old/book/math/quick_pow/index.md