跳转至

# 快速幂

## 引入

快速幂（fast exponentiation），也称 二进制取幂（binary exponentiation）或 平方取幂法（exponentiation by squaring），是一个在 Θ(l o g⁡𝑛)Θ(log⁡n) 的时间内计算 𝑎 𝑛 a n 的小技巧，而暴力的计算需要 Θ(𝑛)Θ(n) 的时间．

这个技巧可以应用于任何 𝑎 a 的乘法满足结合律的场景中，例如模意义下取幂、矩阵幂等，详见后文 应用 一节．

## 过程

计算 𝑎 a 的 𝑛 n 次方表示将 𝑛 n 个 𝑎 a 乘在一起：𝑎 𝑛 =𝑎×𝑎⋯×𝑎⏟𝑛 个 a a n=a×a⋯×a⏟n 个 a．然而当 𝑛 n 太大或单次乘法开销太大的时侯，这种方法就不太适用了．二进制取幂的想法是，将取幂的任务按照指数的 二进制表示 来分割成更小的任务．

例子

假设要计算 3 1 3 3 13．如果将它展开为连乘式，需要 1 3 −1 =1 2 13−1=12 次乘法．但是，因为

3 1 3=3(1 1 0 1)2=3 8×3 4×3 1,3 13=3(1101)2=3 8×3 4×3 1,

所以，只要能快速计算出 3 1,3 2,3 4,3 8 3 1,3 2,3 4,3 8，就能通过 2 2 次乘法计算出 3 1 3 3 13 的值．于是，只需要知道一个快速的方法来计算上述 3 3 的 2 𝑘 2 k 次幂的序列．这是容易的，因为因为序列中（除第一个）任意一个元素都是其前一个元素的平方．

根据这些分析，可以得到 3 1 3 3 13 的计算过程如下：

3 1=3,3 2=(3 1)2=3 2=9,3 4=(3 2)2=9 2=8 1,3 8=(3 4)2=8 1 2=6 5 6 1,3 1 3=6 5 6 1×8 1×3=1 5 9 4 3 2 3.3 1=3,3 2=(3 1)2=3 2=9,3 4=(3 2)2=9 2=81,3 8=(3 4)2=81 2=6561,3 13=6561×81×3=1594323.

过程中，只进行了 5 5 次乘法运算．

这就是快速幂的基本想法．至于具体实现，有两种常见的版本．

### 迭代版本

设 𝑛 n 的二进制表示为 (𝑛 𝑡 𝑛 𝑡−1⋯𝑛 1 𝑛 0)2(n t n t−1⋯n 1 n 0)2，也就是说，有

𝑛=𝑛 𝑡 2 𝑡+𝑛 𝑡−1 2 𝑡−1+⋯+𝑛 1 2 1+𝑛 0 2 0,n=n t 2 t+n t−1 2 t−1+⋯+n 1 2 1+n 0 2 0,

其中，𝑛 𝑖 ∈{0,1}n i∈{0,1}．那么，就有

𝑎 𝑛=𝑎 𝑛 𝑡 2 𝑡+𝑛 𝑡−1 2 𝑡−1+⋯+𝑛 1 2 1+𝑛 0 2 0=𝑎 𝑛 0 2 0×𝑎 𝑛 1 2 1×⋯×𝑎 𝑛 𝑡−1 2 𝑡−1×𝑎 𝑛 𝑡 2 𝑡.a n=a n t 2 t+n t−1 2 t−1+⋯+n 1 2 1+n 0 2 0=a n 0 2 0×a n 1 2 1×⋯×a n t−1 2 t−1×a n t 2 t.

注意，只有 𝑛 𝑖 =1 n i=1 的项才会真正出现在乘积的计算中．

根据这一表达式，可以首先在 Θ(l o g⁡𝑛)Θ(log⁡n) 时间内计算出 𝑎 a 的 Θ(l o g⁡𝑛)Θ(log⁡n) 个 2 𝑘 2 k 次幂的取值，然后花费 Θ(l o g⁡𝑛)Θ(log⁡n) 的时间选择等于 1 1 的二进制位对应的幂次乘到最终结果中．这就是快速幂的迭代版本实现．

伪代码如下：

𝐀 𝐥 𝐠 𝐨 𝐫 𝐢 𝐭 𝐡 𝐦 F a s t P o w(𝑎,𝑛):𝐈 𝐧 𝐩 𝐮 𝐭. B a s e 𝑎 a n d e x p o n e n t 𝑛.𝐎 𝐮 𝐭 𝐩 𝐮 𝐭. P o w e r 𝑎 𝑛.𝐌 𝐞 𝐭 𝐡 𝐨 𝐝.1 𝑟 𝑒 𝑠 𝑢 𝑙 𝑡←I d 2 𝐰 𝐡 𝐢 𝐥 𝐞 𝑛>0 𝐝 𝐨 3 𝐢 𝐟 𝑛 m o d 2=1 𝐭 𝐡 𝐞 𝐧 4 𝑟 𝑒 𝑠 𝑢 𝑙 𝑡←𝑟 𝑒 𝑠 𝑢 𝑙 𝑡⋅𝑎 5 𝐞 𝐧 𝐝 𝐢 𝐟 6 𝑎←𝑎⋅𝑎 7 𝑛←𝑛/2 8 𝐞 𝐧 𝐝 𝐰 𝐡 𝐢 𝐥 𝐞 9 𝐫 𝐞 𝐭 𝐮 𝐫 𝐧 𝑟 𝑒 𝑠 𝑢 𝑙 𝑡 Algorithm FastPow(a,n):Input. Base a and exponent n.Output. Power a n.Method.1 result←Id 2 while n>0 do 3 if n mod 2=1 then 4 result←result⋅a 5 end if 6 a←a⋅a 7 n←n/2 8 end while 9 return result

利用这一方法计算快速幂，需要进行 Θ(l o g⁡𝑛)Θ(log⁡n) 次乘法运算．

### 递归版本

这一过程同样可以通过递归形式实现．注意到，指数 𝑛 n 的二进制展开可以递归地写作

(𝑛 𝑡 𝑛 𝑡−1⋯𝑛 1 𝑛 0)2=2×(𝑛 𝑡 𝑛 𝑡−1⋯𝑛 1)2+𝑛 0.(n t n t−1⋯n 1 n 0)2=2×(n t n t−1⋯n 1)2+n 0.

因此，幂次 𝑎 𝑛 a n 可以递归地计算为

𝑎 𝑛=⎧{ {⎨{ {⎩1,𝑛=0,(𝑎⌊𝑛/2⌋)2,𝑛>0 a n d 𝑛 i s e v e n,(𝑎⌊𝑛/2⌋)2⋅𝑎,𝑛>0 a n d 𝑛 i s o d d.a n={1,n=0,(a⌊n/2⌋)2,n>0 and n is even,(a⌊n/2⌋)2⋅a,n>0 and n is odd.

这就是快速幂的递归版本实现．

伪代码如下：

𝐀 𝐥 𝐠 𝐨 𝐫 𝐢 𝐭 𝐡 𝐦 F a s t P o w(𝑎,𝑛):𝐈 𝐧 𝐩 𝐮 𝐭. B a s e 𝑎 a n d e x p o n e n t 𝑛.𝐎 𝐮 𝐭 𝐩 𝐮 𝐭. P o w e r 𝑎 𝑛.𝐌 𝐞 𝐭 𝐡 𝐨 𝐝.1 𝐢 𝐟 𝑛=0 𝐭 𝐡 𝐞 𝐧 2 𝐫 𝐞 𝐭 𝐮 𝐫 𝐧 I d 3 𝐞 𝐧 𝐝 𝐢 𝐟 4 𝑟 𝑒 𝑠 𝑢 𝑙 𝑡←F a s t P o w(𝑎,𝑛/2)5 𝐢 𝐟 𝑛 m o d 2=0 𝐭 𝐡 𝐞 𝐧 6 𝐫 𝐞 𝐭 𝐮 𝐫 𝐧 𝑟 𝑒 𝑠 𝑢 𝑙 𝑡⋅𝑟 𝑒 𝑠 𝑢 𝑙 𝑡 7 𝐞 𝐥 𝐬 𝐞 8 𝐫 𝐞 𝐭 𝐮 𝐫 𝐧 𝑟 𝑒 𝑠 𝑢 𝑙 𝑡⋅𝑟 𝑒 𝑠 𝑢 𝑙 𝑡⋅𝑎 9 𝐞 𝐧 𝐝 𝐢 𝐟 Algorithm FastPow(a,n):Input. Base a and exponent n.Output. Power a n.Method.1 if n=0 then 2 return Id 3 end if 4 result←FastPow(a,n/2)5 if n mod 2=0 then 6 return result⋅result 7 else 8 return result⋅result⋅a 9 end if

利用这一方法计算快速幂，需要递归 Θ(l o g⁡𝑛)Θ(log⁡n) 次，同样需要 Θ(l o g⁡𝑛)Θ(log⁡n) 次乘法运算．尽管复杂度相同，由于递归本身有一定开销，所以实践中迭代版本的速度更快．

## 应用

### 模意义下取幂

洛谷 P1226【模板】快速幂

给定三个整数 𝑎,𝑏,𝑝 a,b,p，求 𝑎 𝑏 m o d 𝑝 a b mod p．其中 𝑝 ≥2 p≥2．

这是一个非常常见的应用，例如它可以用于计算模意义下的乘法逆元．既然我们知道取模的运算不会干涉乘法运算，因此我们只需要在计算的过程中取模即可．

首先我们可以直接按照上述递归方法实现：

参考实现
C++Python

    1
    2
    3
    4
    5
    6
    7
    8
    long long binpow(long long a, long long b, long long p) {
      if (b == 0) return 1;
      long long res = binpow(a, b / 2, p);
      if (b % 2)
        return res * res % p * a % p;
      else
        return res * res % p;
    }

    1
    2
    3
    4
    5
    6
    7
    8
    def binpow(a, b, p):
        if b == 0:
            return 1
        res = binpow(a, b // 2, p)
        if (b % 2) == 1:
            return res * res * a % p
        else:
            return res * res % p

第二种实现方法是非递归式的．它在循环的过程中将二进制位为 1 时对应的幂累乘到答案中．尽管两者的理论复杂度是相同的，但第二种在实践过程中的速度是比第一种更快的，因为递归会花费一定的开销．

参考实现
C++Python

    1
    2
    3
    4
    5
    6
    7
    8
    9
    long long binpow(long long a, long long b, long long p) {
      long long res = 1;
      while (b > 0) {
        if (b & 1) res = res * a % p;
        a = a * a % p;
        b >>= 1;
      }
      return res;
    }

    1
    2
    3
    4
    5
    6
    7
    8
    def binpow(a, b, p):
        res = 1
        while b > 0:
            if b & 1:
                res = res * a % p
            a = a * a % p
            b >>= 1
        return res

注意

- 模数通常情况下大于 1 1．在十分特殊的情况下，模数 𝑝 p 可能等于 1 1，此时需要特殊考虑 𝑏 =0 b=0 的情况．
- 当指数很大时，需利用 扩展欧拉定理 降幂后计算．

### 计算斐波那契数

根据斐波那契数列的递推式 𝐹 𝑛 =𝐹 𝑛−1 +𝐹 𝑛−2 F n=F n−1+F n−2，我们可以构建一个 2 ×2 2×2 的矩阵来表示从 𝐹 𝑖,𝐹 𝑖+1 F i,F i+1 到 𝐹 𝑖+1,𝐹 𝑖+2 F i+1,F i+2 的变换．于是在计算这个矩阵的 𝑛 n 次幂的时侯，我们使用快速幂的思想，可以在 Θ(l o g⁡𝑛)Θ(log⁡n) 的时间内计算出结果．对于更多的细节参见 斐波那契数列，矩阵快速幂的实现参见 矩阵加速递推 中的实现．

### 多次置换

问题描述

给你一个长度为 𝑛 n 的序列和一个置换，把这个序列置换 𝑘 k 次．

简单地把这个置换取 𝑘 k 次幂，然后把它应用到序列上即可．时间复杂度为 𝑂(𝑛 l o g⁡𝑘)O(n log⁡k)．对于更多的细节参见 置换的复合．

注意

对这个置换建图，然后在每一个环上分别做 𝑘 k 次幂（事实上等价于 𝑘 k 对环长取模），可以在 𝑂(𝑛)O(n) 的时间复杂度下解决此问题．

### 加速几何中对点集的操作

HDU 4087 A Letter to Programmers

给定三维空间中 𝑛 n 个点 𝑝 𝑖 p i，要求将 𝑚 m 个操作都应用于这些点．包含 3 种操作：

1. 沿某个向量移动点的位置（Shift）．
2. 按比例缩放这个点的坐标（Scale）．
3. 绕某条直线旋转（Rotate）．

还有一个特殊的操作，就是将某个操作序列重复 𝑘 k 次（Repeat），Repeat 操作可以嵌套．输出操作结束后每个点的坐标．

参考 向量与矩阵 中的内容，每一种操作都可以用一个变换矩阵表示，一系列连续的变换可以用矩阵的乘积来表示．一个 Repeat 操作就相当于取一个矩阵的 𝑘 k 次幂．这样可以用 𝑂(𝑚 l o g⁡𝑘)O(m log⁡k) 的时间计算出整个变换序列最终形成的矩阵．最后将它应用到 𝑛 n 个点上，总复杂度 𝑂(𝑛 +𝑚 l o g⁡𝑘)O(n+m log⁡k)．

### 定长路径计数

问题描述

给一个有向图（边权为 1），求任意两点 𝑢,𝑣 u,v 间从 𝑢 u 到 𝑣 v，长度为 𝑘 k 的路径的条数．

我们把该图的邻接矩阵 𝑀 M 取 𝑘 k 次幂，那么 𝑀 𝑖,𝑗 M i,j 就表示从 𝑖 i 到 𝑗 j 长度为 𝑘 k 的路径的数目．该算法的复杂度是 𝑂(𝑛 3 l o g⁡𝑘)O(n 3 log⁡k)．有关该算法的细节请参见 矩阵 页面．

### 模意义下的整数乘法

问题描述

给定非负整数 𝑎,𝑏 a,b 和正整数 𝑚 m，计算 𝑎 ×𝑏 m o d 𝑚 a×b mod m，其中 𝑎,𝑏 ≤𝑚 ≤1 0 1 8 a,b≤m≤10 18．

与二进制取幂的思想一样，这次我们将其中的一个乘数表示为若干个 2 的整数次幂的和的形式．因为在对一个数做乘 2 并取模的运算的时侯，我们可以转化为加减操作防止整型溢出．这样可以在 𝑂(l o g⁡𝑚)O(log⁡m) 的时间复杂度下解决问题．递归方法如下：

𝑎⋅𝑏=⎧{ {⎨{ {⎩0 i f 𝑎=0 2⋅𝑎 2⋅𝑏 i f 𝑎>0 a n d 𝑎 e v e n 2⋅𝑎−1 2⋅𝑏+𝑏 i f 𝑎>0 a n d 𝑎 o d d a⋅b={0 if a=0 2⋅a 2⋅b if a>0 and a even 2⋅a−1 2⋅b+b if a>0 and a odd

但在实际使用中，此方法由于引入了更大的计算复杂度导致时间效率不优．实际编程中通常利用 快速乘 来进行模数范围在 `long long` 时的乘法操作．

### 高精度快速幂

前置技能：大整数乘法

洛谷 P1045 [NOIP 2003 普及组] 麦森数

给定整数 𝑃 P（1 0 0 0 <𝑃 <3 1 0 0 0 0 0 1000<P<3100000），计算 2 𝑃 −1 2 P−1 的位数与最后 5 0 0 500 位数字（用十进制数表示），不足 5 0 0 500 位时高位补 0．

代码实现

     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
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    #include <cmath>
    #include <cstring>
    #include <iostream>
    using namespace std;

    const int M = 500;

    int a[505], b[505], t[505];

    // 大整数乘法
    void mult(int x[], int y[]) {
      memset(t, 0, sizeof(t));
      for (int i = 1; i <= x[0]; i++) {
        for (int j = 1; j <= y[0]; j++) {
          if (i + j - 1 > M) continue;
          t[i + j - 1] += x[i] * y[j];
          t[i + j] += t[i + j - 1] / 10;
          t[i + j - 1] %= 10;
          t[0] = i + j;
        }
      }
      memcpy(b, t, sizeof(b));
    }

    // 快速幂
    void binpow(int p) {
      if (p == 1) {
        memcpy(b, a, sizeof(b));
        return;
      }
      binpow(p / 2);  // (2^(p/2))^2=2^p
      mult(b, b);     // 对 b 平方
      if (p % 2 == 1) mult(b, a);
    }

    int main() {
      cin.tie(nullptr)->sync_with_stdio(false);
      int p;
      cin >> p;
      a[0] = 1;  // 记录 a 数组的位数
      a[1] = 2;  // 对 2 进行平方
      b[0] = 1;  // 记录 b 数组的位数
      b[1] = 1;  // 答案数组
      binpow(p);
      cout << (int)(log10(2) * p) + 1 << '\n';
      b[1] -= 1;  // 最后一位减 1
      for (int i = M; i >= 1; i--) {
        cout << b[i];
        if ((i - 1) % 50 == 0) {
          cout << '\n';
        }
      }
    }

## 底数固定的预处理快速幂

当底数 𝑎 a 固定时，可以利用 分块思想，用一定的时间预处理后用 𝑂(1)O(1) 的时间回答一次幂询问．这一算法也常称为光速幂．过程如下：

1. 选定一个数 𝑠 s，预处理出 𝑎 0,𝑎 1,⋯,𝑎 𝑠−1 a 0,a 1,⋯,a s−1 与 𝑎 0,𝑎 𝑠,⋯,𝑎⌊𝑝/𝑠⌋𝑠 a 0,a s,⋯,a⌊p/s⌋s 的值并存在两个数组里；
2. 对于每一次询问 𝑎 𝑏 a b，将 𝑏 b 拆分成 ⌊𝑏/𝑠⌋𝑠 +(𝑏 m o d 𝑠)⌊b/s⌋s+(b mod s)，则 𝑎 𝑏 =𝑎⌊𝑏/𝑠⌋𝑠 ⋅𝑎 𝑏 m o d 𝑠 a b=a⌊b/s⌋s⋅a b mod s，就可以 𝑂(1)O(1) 求出答案．

假设指数 𝑏 b 的范围是 [0,𝑛][0,n]，那么块长 𝑠 s 经常选择为 √𝑛 n 或者与之相近的 2 2 的幂次．选择 √𝑛 n 可以获得最优的预处理复杂度 𝑂(√𝑛)O(n)，而选择 2 2 的幂次可以使用位操作简化计算．

特别地，对于模意义下幂的计算，底数 𝑎 a 相同隐含着模数 𝑚 m 也要相同这一要求．由于 扩展欧拉定理，对于任意模数 𝑚 m，预处理的指数范围上界为 𝑛 =2 𝜑(𝑚)n=2 φ(m)；对于素模数 𝑝 p，预处理的范围上界为 𝑛 =𝑝 −1 n=p−1．这两种情形预处理的复杂度都是 𝑂(√𝑚)O(m)．

参考代码

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    int a, mod, pow1[65536], pow2[65536];

    void preproc() {
      pow1[0] = pow2[0] = 1;
      for (int i = 1; i < 65536; i++) pow1[i] = 1LL * pow1[i - 1] * a % mod;
      int pow65536 = 1LL * pow1[65535] * a % mod;
      for (int i = 1; i < 65536; i++) pow2[i] = 1LL * pow2[i - 1] * pow65536 % mod;
    }

    int query(int pows) {
      return 1LL * pow1[pows & 65535] * pow2[pows >> 16] % mod;
    }

## 习题

- UVa 1230 - MODEX
- UVa 374 - Big Mod
- UVa 11029 - Leading and Trailing
- Codeforces - Parking Lot
- SPOJ - The last digit
- SPOJ - Locker
- SPOJ - Just add it

本页面部分内容译自博文 Бинарное возведение в степень 与其英文翻译版 Binary Exponentiation．其中俄文版版权协议为 Public Domain + Leave a Link；英文版版权协议为 CC-BY-SA 4.0．

> 本页面最近更新：2026/1/27 12:26:08，更新历史
> 发现错误？想一起完善？ 在 GitHub 上编辑此页！
> 本页面贡献者：Ir1d, sshwy, Tiphereth-A, cbw2007, Enter-tainer, Xeonacid, HeRaNO, ksyx, ouuan, c-forrest, Henry-ZHR, iamtwz, luoguyuntianming, Marcythm, Peanut-Tang, Aquistcev, billchenchina, CCXXXI, chinggg, eyedeng, FFjet, Great-designer, H-J-Granger, hhc0001, hsfzLZH1, Hszzzx, JEB-Bem, Jude Gao, kenlig, kfy666, Konano, Menci, NachtgeistW, qwqAutomaton, shawlleyw, shenshuaijie, StudyingFather, TOMWT-qwq, TrisolarisHD, TRSWNCA, uqzjc, Zhoier
> 本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用