企业官网建设流程全解析

OI-wiki 快速幂（二进制取幂）完全指南：原理、迭代与递归实现及六大经典应用

【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. （某大型游戏线上攻略，内含炫酷算术魔法）项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki

导读

快速幂（fast exponentiation），也称二进制取幂（binary exponentiation）或平方取幂法（exponentiation by squaring），是 OI / ICPC 竞赛中计算 $a^n$ 的核心技巧：暴力连乘需要 $\Theta(n)$ 次乘法，而二进制取幂只需 $\Theta(\log n)$ 次。本指南以 OI-wiki 的 binary-exponentiation.md 为主体，结合仓库内 代码实现 与配套 测试样例，系统讲解其数学原理、迭代/递归两种写法，以及模幂、斐波那契数列、置换复合、几何变换、定长路径计数、高精度快速幂等六大应用场景。读完本文，你将能够独立写出正确且高效的快速幂代码，并理解其迁移到矩阵、置换等任意满足结合律运算上的通用方法。

引入：为什么需要快速幂

计算 $a$ 的 $n$ 次方，最朴素的定义是把 $n$ 个 $a$ 乘在一起：

$$ a^{n} = \underbrace{a \times a \cdots \times a}_{n\text{ 个 }a}. $$

然而当 $n$ 太大（如 $n\ge 10^9$），或单次乘法本身开销很大（如矩阵乘法、高精度乘法）时，这种逐项连乘的方式就不适用了。二进制取幂的核心思想是：将取幂任务按照指数的二进制表示分割成更小的任务，从而把乘法次数从 $\Theta(n)$ 降到 $\Theta(\log n)$。

以 $3^{13}$ 为例。若展开为连乘式需要 $13-1=12$ 次乘法，但注意到 $13=(1101)_2$，于是

$$ 3^{13} = 3^{(1101)_2} = 3^8 \times 3^4 \times 3^1. $$

只要能快速得到 $3^1,3^2,3^4,3^8$，就能通过 $2$ 次乘法得出结果。而 $3^{2^k}$ 这个序列的每一项恰好是前一项的平方，计算成本极低。完整过程如下：

$$ \begin{aligned} 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, \ 3^{13} &= 6561 \times 81 \times 3 = 1594323. \end{aligned} $$

全程只进行了 $5$ 次乘法。这背后唯一的数学前提是乘法满足结合律——因此该技巧不仅适用于普通整数，也适用于模意义下的乘法、矩阵乘法、置换复合等一切满足结合律的运算。

过程：两种经典实现

迭代版本

设 $n$ 的二进制表示为 $(n_tn_{t-1}\cdots n_1n_0)_2$，即

$$ n = n_t2^t + n_{t-1}2^{t-1} + \cdots + n_12^1 + n_02^0, $$

其中 $n_i\in{0,1}$，则

$$ a^n = a^{n_t2^t + n_{t-1}2^{t-1} + \cdots + n_12^1 + n_02^0} = a^{n_0 2^0} \times a^{n_1 2^1}\times \cdots \times a^{n_{t-1}2^{t-1}} \times a^{n_t2^t}. $$

注意，只有 $n_i=1$ 的项才会真正出现在乘积中。据此，先花 $\Theta(\log n)$ 时间依次算出 $a^{2^0},a^{2^1},\cdots$（每个都是前一个的平方），再花 $\Theta(\log n)$ 时间把二进制位为 $1$ 对应的幂次乘入结果即可。

迭代版本伪代码如下：

$$ \begin{array}{l} \textbf{Algorithm }\text{FastPow}(a, n): \ \textbf{Input. }\text{Base }a\text{ and exponent }n.\ \textbf{Output. }\text{Power }a^n.\ \textbf{Method.}\ \begin{array}{ll} 1 & \textit{result}\gets\mathrm{Id}\ 2 & \textbf{while }n > 0\textbf{ do}\ 3 & \qquad \textbf{if }n \bmod 2 = 1\textbf{ then}\ 4 & \qquad \qquad \textit{result} \gets \textit{result}\cdot a\ 5 & \qquad \textbf{end if}\ 6 & \qquad a \gets a \cdot a\ 7 & \qquad n \gets n / 2\ 8 & \textbf{end while}\ 9 & \textbf{return }\textit{result} \end{array} \end{array} $$

其中 $\mathrm{Id}$ 是乘法单位元（整数取幂时为 $1$）。该算法共进行 $\Theta(\log n)$ 次乘法。仓库中 luogu-P1226-2.cpp 的迭代实现如下：

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; // 当前二进制位为 1，乘入对应幂 a = a * a % p; // a 自乘得到下一个 2^k 次幂 b >>= 1; // 指数右移一位 } return res; }

对应 Python 版本见 luogu-P1226-2.py：

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

递归版本

递归版本利用指数的二进制展开可递归写作

$$ (n_tn_{t-1}\cdots n_1n_0)2 = 2 \times (n_tn{t-1}\cdots n_1)_2 + n_0, $$

于是幂次 $a^n$ 可递归计算：

$$ a^n = \begin{cases} 1, & n = 0,\ (a^{\lfloor n/2\rfloor})^2, & n > 0 \text{ and }n\text{ is even},\ (a^{\lfloor n/2\rfloor})^2\cdot a, & n > 0 \text{ and }n\text{ is odd}. \end{cases} $$

递归版本伪代码如下：

$$ \begin{array}{l} \textbf{Algorithm }\text{FastPow}(a, n): \ \textbf{Input. }\text{Base }a\text{ and exponent }n.\ \textbf{Output. }\text{Power }a^n.\ \textbf{Method.}\ \begin{array}{ll} 1 & \textbf{if }n = 0\textbf{ then}\ 2 & \qquad \textbf{return }\mathrm{Id}\ 3 & \textbf{end if}\ 4 & \textit{result} \gets \text{FastPow}(a, n / 2) \ 5 & \textbf{if }n\bmod 2 = 0\textbf{ then}\ 6 & \qquad \textbf{return }\textit{result}\cdot\textit{result}\ 7 & \textbf{else}\ 8 & \qquad \textbf{return }\textit{result}\cdot\textit{result}\cdot a\ 9 & \textbf{end if} \end{array} \end{array} $$

递归版本需要递归 $\Theta(\log n)$ 次、$\Theta(\log n)$ 次乘法，复杂度与迭代版相同，但由于递归调用本身有一定开销，实践中迭代版本速度更快。仓库中 luogu-P1226-1.cpp 的递归实现为：

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; }

Python 版本见 luogu-P1226-1.py，两版实现均有配套的.in/.ans测试数据（examples/binary-exponentiation 目录下luogu-P1226-1.in、luogu-P1226-2.in等）可对照验证。

应用一：模意义下取幂

给定三个整数 $a,b,p$，求 $a^b\bmod p$（$p\ge 2$），这是快速幂最常见的应用，例如可用来计算模意义下的乘法逆元。由于取模运算不会干涉乘法，只需在每一步乘法后取模即可。

需要注意两点（原文档的明确警告）：

• 模数通常情况下大于 $1$；在十分特殊的情况下模数 $p$ 可能等于 $1$，此时需特殊考虑 $b=0$ 的情况；
• 当指数很大时，需利用扩展欧拉定理先降幂再计算。

模板题可见洛谷 P1226【模板】快速幂，上文给出的递归与迭代两版代码即为该题的标准解法，输出格式为a^b mod p=结果。

应用二：计算斐波那契数

根据斐波那契数列的递推式 $F_n = F_{n-1} + F_{n-2}$，可以构造一个 $2\times 2$ 的矩阵来表示从 $(F_i,F_{i+1})$ 到 $(F_{i+1},F_{i+2})$ 的线性变换。于是计算该矩阵的 $n$ 次幂时使用快速幂思想，就可在 $\Theta(\log n)$ 时间内求出 $F_n$。

相关细节参见 斐波那契数列，矩阵快速幂的具体实现参见 矩阵加速递推。这正是"快速幂适用于任何满足结合律的运算"的直接体现：把底数从标量换成矩阵，代码结构完全不变。

应用三：多次置换

问题描述：给定一个长度为 $n$ 的序列和一个置换，把该序列置换 $k$ 次。

简单做法是把这个置换取 $k$ 次幂，然后应用到序列上，时间复杂度 $O(n\log k)$。因为置换的复合满足结合律，可以直接复用快速幂框架（将"乘法"替换为"置换复合"）。更多细节参见 置换的复合。

进一步的优化思路（原文档提示）：对这个置换建图，然后在每一个环上分别做 $k$ 次幂（事实上等价于 $k$ 对环长取模），可以做到 $O(n)$ 的时间复杂度。

应用四：加速几何中对点集的操作

以 HDU 4087 "A Letter to Programmers" 为例：给定三维空间中 $n$ 个点 $p_i$，需要依次应用 $m$ 个操作，操作类型包括：

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

此外还有一个特殊操作 Repeat：将某个操作序列重复 $k$ 次，且 Repeat 可以嵌套。要求输出全部操作结束后每个点的坐标。

依据 向量与矩阵 的知识，每种操作都可以用一个变换矩阵表示，一系列连续变换等价于矩阵乘积；一个 Repeat 操作就相当于取某个矩阵的 $k$ 次幂。于是可以用 $O(m\log k)$ 的时间算出整个变换序列最终形成的矩阵，再一次性应用到 $n$ 个点上，总复杂度 $O(n + m\log k)$。

应用五：定长路径计数

问题描述：给一个有向图（边权为 1），求任意两点 $u,v$ 之间长度为 $k$ 的路径条数。

解法非常优雅：把图的邻接矩阵 $M$ 取 $k$ 次幂，则 $M^k_{i,j}$ 就表示从 $i$ 到 $j$ 长度为 $k$ 的路径数目。由于矩阵乘法满足结合律，直接使用矩阵快速幂即可，复杂度为 $O(n^3\log k)$。算法细节参见 矩阵 页面。

应用六：模意义下的整数乘法与高精度快速幂

模意义下的整数乘法（快速乘）

问题描述：给定非负整数 $a,b$ 和正整数 $m$，计算 $a\times b\bmod m$，其中 $a,b\le m\le 10^{18}$。

与二进制取幂思想类似，把其中一个乘数表示为若干个 2 的整数次幂之和。由于对某数做"乘 2 并取模"可以转化为加减操作防止整型溢出，可在 $O(\log m)$ 时间内解决。递归形式为：

$$ a \cdot b = \begin{cases} 0 &\text{if }a = 0 \ 2 \cdot \frac{a}{2} \cdot b &\text{if }a > 0 \text{ and }a \text{ even} \ 2 \cdot \frac{a-1}{2} \cdot b + b &\text{if }a > 0 \text{ and }a \text{ odd} \end{cases} $$

不过原文档明确指出：此方法引入了更大的计算常数，实际时间效率并不优，编程中通常利用 快速乘 来处理模数范围在long long时的乘法。

高精度快速幂：麦森数

前置技能：大整数乘法。

以洛谷 P1045【NOIP 2003 普及组】麦森数为例：给定整数 $P$（$1000 < P < 3100000$），要求计算 $2^P-1$ 的位数与最后 $500$ 位数字（十进制，不足 500 位高位补 0）。

这里底数是 2，指数 $P$ 可达数百万，结果位数以万计，必须将快速幂与大整数乘法结合。仓库中完整实现见 luogu-P1045.cpp，核心思路：

• 用数组按十进制位存储大数，mult实现高精度乘法（仅保留末 500 位，i + j - 1 > M时直接跳过，其中M = 500）；
• binpow采用递归快速幂：binpow(p/2)后对结果平方，若p为奇数再乘一次底数 2；
• 位数利用 $\log_{10}(2)\times P$ 取整加 1 直接算出：cout << (int)(log10(2) * p) + 1；
• 最后将末位减 1 得到 $2^P-1$，并按每行 50 位输出后 500 位。

配套测试数据见 luogu-P1045.in 与 luogu-P1045.ans。

底数固定的预处理快速幂（光速幂）

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

1. 选定一个数 $s$，预处理 $a^0,a^1,\cdots,a^{s-1}$ 与 $a^0,a^s,\cdots,a^{\lfloor p/s\rfloor s}$，分别存入两个数组；
2. 对每次询问 $a^b$，将 $b$ 拆分为 $\lfloor b/s\rfloor s+(b\bmod s)$，则 $$ a^b=a^{\lfloor b/s\rfloor s}\cdot a^{b\bmod s}, $$ 两次数组查询一次乘法即可 $O(1)$ 求答。

假设指数 $b$ 的范围是 $[0,n]$，块长 $s$ 通常取 $\sqrt{n}$ 或与之相近的 2 的幂次：取 $\sqrt{n}$ 得到最优预处理复杂度 $O(\sqrt{n})$；取 2 的幂次则可使用位操作简化计算（如用&与>>代替除法与取模）。

对于模意义下的幂，底数 $a$ 相同还隐含着模数 $m$ 也要相同这一要求。由 扩展欧拉定理：对任意模数 $m$，预处理的指数范围上界为 $n = 2\varphi(m)$；对素模数 $p$，预处理范围上界为 $n = p - 1$，两种情形的预处理复杂度都是 $O(\sqrt{m})$。

仓库中 pre-exp.cpp 给出了以 $s=2^{16}=65536$ 为块长的参考实现，并通过main中对{0, 1, 2, 15, 65535, 65536, 65537, 100000, 123456789, (1LL<<31)-1}等边界与随机指数逐一比对"光速幂"与朴素快速幂结果的方式做正确性自检，输出OK/Error。其核心逻辑如下：

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; }

这里pow1[i]存 $a^i$（$0\le i<65536$），pow2[i]存 $a^{65536\cdot i}$，查询时低 16 位用pows & 65535、高 16 位用pows >> 16直接索引，正是"选 2 的幂次块长 + 位操作"思想的落地实现。配套测试数据见 pre-exp.in 与 pre-exp.ans。

进阶练习

原文档附带了以下练习题目，覆盖模幂、末位/前导数字、计数等快速幂的典型考法：

• UVa 1230 - MODEX（模意义取幂模板）
• UVa 374 - Big Mod（大指数模幂）
• UVa 11029 - Leading and Trailing（同时求前导与末尾数字）
• Codeforces 630I - Parking Lot（计数问题）
• SPOJ LASTDIG - The last digit（末位数字）
• SPOJ LOCKER（乘积最大化类问题）
• SPOJ ZSUM - Just add it（多组幂求和）

小结

快速幂的复杂度从 $\Theta(n)$ 降到 $\Theta(\log n)$，其本质是把指数按二进制拆解并复用平方结果。只要运算满足结合律（整数乘法、模乘法、矩阵乘法、置换复合……），同一套框架即可迁移使用。结合本文给出的 C++ / Python 参考实现 与仓库中配套的.in/.ans测试数据，读者可以自行验证实现正确性，并在模幂、矩阵加速递推、光速幂等场景中直接套用。

（说明：本页内容部分译自 e-maxx 的《Бинарное возведение в степень》及其英文翻译版 Binary Exponentiation，其中俄文版版权协议为 Public Domain + Leave a Link，英文版版权协议为 CC-BY-SA 4.0。）

【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. （某大型游戏线上攻略，内含炫酷算术魔法）项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki