Last update:
June 10, 2026

二进制快速幂

二进制快速幂也称平方求幂。对于非负整数 $n$ ，它只需 $O(\log n)$ 次乘法就能计算 $a^n$ ，而朴素方法需要 $O(n)$ 次乘法。

这种技巧也广泛应用于与普通算术无关的任务，因为它适用于任何满足结合律的运算：

(X \cdot Y) \cdot Z = X \cdot (Y \cdot Z)

最直接的例子是模乘和矩阵乘法，下面还会讨论其他应用。

算法

朴素地计算 $a$ 的 $n$ 次幂，就是将 $n$ 个 $a$ 相乘，执行 $n-1$ 次乘法： $a^n=a\cdot a\cdot\ldots\cdot a$ 。但当 $a$ 或 $n$ 很大时，这种方式不实用。

利用 $a^{b+c}=a^b\cdot a^c$ ，以及 $a^{2b}=a^b\cdot a^b=(a^b)^2$ 。

二进制快速幂的思路是：根据指数的二进制表示拆分计算。

把 $n$ 写成二进制，例如：

3^{13} = 3^{1101_2} = 3^8 \cdot 3^4 \cdot 3^1

正整数 $n$ 的二进制表示恰有 $\lfloor\log_2 n\rfloor+1$ 位。因此，如果已经知道 $a^1,a^2,a^4,a^8,\dots,a^{2^{\lfloor\log_2 n\rfloor}}$ ，只需执行 $O(\log n)$ 次乘法。

现在只需找到快速求出这些幂的方法。方法很简单：序列中的每一项都是前一项的平方。

\begin{align} 3^1 &= 3 \\ 3^2 &= \left(3^1\right)^2 = 3^2 = 9 \\ 3^4 &= \left(3^2\right)^2 = 9^2 = 81 \\ 3^8 &= \left(3^4\right)^2 = 81^2 = 6561 \end{align}

因此，计算 $3^{13}$ 时，只需将其中三项相乘； $n$ 中对应 $3^2$ 的位为 0，所以跳过它： $3^{13}=6561\cdot81\cdot3=1594323$ 。

总时间复杂度为 $O(\log n)$ ：计算这些 $a$ 的幂需要对数级次数的操作，再至多用对数级次数的乘法将它们组合为最终结果。

下面的递归形式表达了同一个思路：

a^n = \begin{cases} 1 &\text{if } n == 0 \\ \left(a^{\frac{n}{2}}\right)^2 &\text{if } n > 0 \text{ and } n \text{ even}\\ \left(a^{\frac{n – 1}{2}}\right)^2 \cdot a &\text{if } n > 0 \text{ and } n \text{ odd}\\ \end{cases}

实现

先看递归实现，它直接对应上面的递推公式：

long long binpow(long long a, long long b) {
    if (b == 0)
        return 1;
    long long res = binpow(a, b / 2);
    if (b % 2)
        return res * res * a;
    else
        return res * res;
}

第二种方法不使用递归。在循环中计算各个幂，只将 $n$ 的对应二进制位为 1 的项乘入结果。两种方法的复杂度相同，但迭代实现省去了递归调用开销，实际运行通常更快。

long long binpow(long long a, long long b) {
    long long res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a;
        a = a * a;
        b >>= 1;
    }
    return res;
}

应用

高效计算模意义下的大整数幂

问题：计算 $x^n\bmod m$ 。这是一种非常常见的运算，例如求模乘逆元时就会用到。

解法：取模与乘法相容： $a\cdot b\equiv(a\bmod m)\cdot(b\bmod m)\pmod m$ 。因此可以直接沿用上述代码，将每次乘法改为模乘：

long long binpow(long long a, long long b, long long m) {
    a %= m;
    long long res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a % m;
        a = a * a % m;
        b >>= 1;
    }
    return res;
}

注意：当指数 $b$ 远大于 $m$ 时，还能进一步加速。对于正整数 $m$ ，若 $\gcd(x,m)=1$ ，则当 $m$ 为素数时，有 $x^n\equiv x^{n\bmod(m-1)}\pmod m$ ；当 $m$ 为合数时，有 $x^n\equiv x^{n\bmod\phi(m)}\pmod m$ 。这些结论直接来自费马小定理和欧拉定理，详情参见“模逆元”文章。

高效计算斐波那契数

问题：计算第 $n$ 个斐波那契数 $F_n$ 。

解法：详细说明见“斐波那契数”文章，这里只概述算法。由于 $F_n=F_{n-1}+F_{n-2}$ ，计算下一个数只需前两个数。可以构造一个 $2\times2$ 矩阵，表示从 $F_i,F_{i+1}$ 到 $F_{i+1},F_{i+2}$ 的变换。例如，应用到 $F_0,F_1$ 后就得到 $F_1,F_2$ 。将这个变换矩阵提升到 $n$ 次幂，就能在 $O(\log n)$ 时间内得到 $F_n$ 。

将一个置换应用 $k$ 次

问题：给定长度为 $n$ 的序列，将一个给定置换应用 $k$ 次。

解法：用二进制快速幂计算置换的 $k$ 次幂，再将它应用到序列上。时间复杂度为 $O(n\log k)$ 。

vector<int> applyPermutation(vector<int> sequence, vector<int> permutation) {
    vector<int> newSequence(sequence.size());
    for(int i = 0; i < sequence.size(); i++) {
        newSequence[i] = sequence[permutation[i]];
    }
    return newSequence;
}

vector<int> permute(vector<int> sequence, vector<int> permutation, long long k) {
    while (k > 0) {
        if (k & 1) {
            sequence = applyPermutation(sequence, permutation);
        }
        permutation = applyPermutation(permutation, permutation);
        k >>= 1;
    }
    return sequence;
}

注意：这个问题还可以在线性时间内解决：构造置换图，分别处理其中每个环，将 $k$ 对环长取模，即可确定环内每个元素的最终位置。

快速将一组几何变换应用到一组点

问题：给定 $n$ 个点 $p_i$ ，对每个点执行 $m$ 个变换。每个变换可以是平移、缩放，或绕指定轴旋转指定角度。此外还有“循环”操作，将一组变换重复 $k$ 次，循环还可以嵌套。要求比 $O(n\cdot length)$ 更快地执行所有变换，其中 $length$ 是展开循环后的变换总数。

解法：先观察不同变换如何改变坐标：

平移：分别给各个坐标加上一个常数。
缩放：分别将各个坐标乘以一个常数。
旋转：变换较复杂，这里不展开推导，但每个新坐标仍能表示成原坐标的线性组合。

这些变换都可以通过坐标上的线性运算来表示。使用齐次坐标后，一个变换可以写成如下 $4\times4$ 矩阵：

\begin{pmatrix} a_{11} & a_ {12} & a_ {13} & a_ {14} \\ a_{21} & a_ {22} & a_ {23} & a_ {24} \\ a_{31} & a_ {32} & a_ {33} & a_ {34} \\ a_{41} & a_ {42} & a_ {43} & a_ {44} \end{pmatrix}

让原坐标与一个值为 1 的附加坐标组成向量，再与矩阵相乘，就得到新坐标及值为 1 的附加坐标：

\begin{pmatrix} x & y & z & 1 \end{pmatrix} \cdot \begin{pmatrix} a_{11} & a_ {12} & a_ {13} & a_ {14} \\ a_{21} & a_ {22} & a_ {23} & a_ {24} \\ a_{31} & a_ {32} & a_ {33} & a_ {34} \\ a_{41} & a_ {42} & a_ {43} & a_ {44} \end{pmatrix} = \begin{pmatrix} x’ & y’ & z’ & 1 \end{pmatrix}

为什么要引入第四个虚构坐标？这正是齐次坐标的妙处，它在计算机图形学中应用广泛。平移需要给坐标加常数；若不升维，就无法用一次矩阵乘法表达这样的仿射运算。升维后，仿射变换就成为线性变换。

下面给出几种变换的矩阵表示：

平移： $x$ 坐标增加 $5$ ， $y$ 坐标增加 $7$ ， $z$ 坐标增加 $9$ 。

\begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 5 & 7 & 9 & 1 \end{pmatrix}

缩放： $x$ 坐标乘以 $10$ ，另两个坐标各乘以 $5$ 。

\begin{pmatrix} 10 & 0 & 0 & 0 \\ 0 & 5 & 0 & 0 \\ 0 & 0 & 5 & 0 \\ 0 & 0 & 0 & 1 \end{pmatrix}

旋转：遵循右手定则，绕 $x$ 轴逆时针旋转 $\theta$ 度。

\begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & \cos \theta & -\sin \theta & 0 \\ 0 & \sin \theta & \cos \theta & 0 \\ 0 & 0 & 0 & 1 \end{pmatrix}

将每个变换写成矩阵后，变换序列就是这些矩阵的乘积；重复 $k$ 次的循环就是矩阵的 $k$ 次幂，可以在 $O(\log k)$ 次矩阵乘法内用快速幂求出。先在 $O(m\log k)$ 时间内计算代表所有变换的矩阵，再用 $O(n)$ 时间将其应用到所有点，总复杂度为 $O(n+m\log k)$ 。

图中长度为 $k$ 的路径数量

问题：给定一个有 $n$ 个顶点的有向无权图，求从任意顶点 $u$ 到任意顶点 $v$ 、长度为 $k$ 的路径数量。

解法：另有专文详细讨论此问题。算法是将邻接矩阵 $M$ 提升到 $k$ 次幂：若存在从 $i$ 到 $j$ 的边，则 $m_{ij}=1$ ，否则为 0。结果矩阵的 $m_{ij}$ 就是从 $i$ 到 $j$ 、长度为 $k$ 的路径数量。该解法的时间复杂度为 $O(n^3\log k)$ 。

注意：同一篇文章还讨论了带权变体：寻找恰好包含 $k$ 条边的最小权重路径。它同样可以通过邻接矩阵的幂求解。矩阵中保存从 $i$ 到 $j$ 的边权；没有边则为 $\infty$ 。矩阵乘法也需修改：将乘法换成加法，将求和换成取最小值，即 $result_{ij}=\min\limits_{1\leq k\leq n}(a_{ik}+b_{kj})$ 。