快速幂
引入
快速幂 （fast exponentiation），也称 二进制取幂 （binary exponentiation）或 平方取幂法 （exponentiation by squaring），是一个在 Θ(log𝑛)Θ(logn)
的时间内计算 𝑎𝑛an 的小技巧，而暴力的计算需要 Θ(𝑛)Θ(n) 的时间．
这个技巧可以应用于任何 𝑎a 的乘法满足结合律的场景中，例如模意义下取幂、矩阵幂等，详见后文 应用 一节．
过程
计算 𝑎a 的 𝑛n 次方表示将 𝑛n 个 𝑎a 乘在一起：𝑎𝑛 =𝑎×𝑎⋯×𝑎⏟𝑛 个 aan=a×a⋯×a⏟n 个 a．然而当 𝑛n 太大或单次乘法开销太大的时侯，这种方法就不太适用了．二进制取幂的想法是，将取幂的任务按照指数的 二进制表示 来分割成更小的任务．
例子
假设要计算 313313．如果将它展开为连乘式，需要 13 −1 =1213−1=12 次乘法．但是，因为
313=3(1101)2=38×34×31,313=3(1101)2=38×34×31,
所以，只要能快速计算出 31,32,34,3831,32,34,38，就能通过 22 次乘法计算出 313313 的值．于是，只需要知道一个快速的方法来计算上述 33 的 2𝑘2k 次幂的序列．这是容易的，因为因为序列中（除第一个）任意一个元素都是其前一个元素的平方．
根据这些分析，可以得到 313313 的计算过程如下：
31=3,32=(31)2=32=9,34=(32)2=92=81,38=(34)2=812=6561,313=6561×81×3=1594323.31=3,32=(31)2=32=9,34=(32)2=92=81,38=(34)2=812=6561,313=6561×81×3=1594323.
过程中，只进行了 55 次乘法运算．
这就是快速幂的基本想法．至于具体实现，有两种常见的版本．
迭代版本
设 𝑛n 的二进制表示为 (𝑛𝑡𝑛𝑡−1⋯𝑛1𝑛0)2(ntnt−1⋯n1n0)2，也就是说，有
𝑛=𝑛𝑡2𝑡+𝑛𝑡−12𝑡−1+⋯+𝑛121+𝑛020,n=nt2t+nt−12t−1+⋯+n121+n020,
其中，𝑛𝑖 ∈{0,1}ni∈{0,1}．那么，就有
𝑎𝑛=𝑎𝑛𝑡2𝑡+𝑛𝑡−12𝑡−1+⋯+𝑛121+𝑛020=𝑎𝑛020×𝑎𝑛121×⋯×𝑎𝑛𝑡−12𝑡−1×𝑎𝑛𝑡2𝑡.an=ant2t+nt−12t−1+⋯+n121+n020=an020×an121×⋯×ant−12t−1×ant2t.
注意，只有 𝑛𝑖 =1ni=1 的项才会真正出现在乘积的计算中．
根据这一表达式，可以首先在 Θ(log𝑛)Θ(logn) 时间内计算出 𝑎a 的 Θ(log𝑛)Θ(logn) 个 2𝑘2k 次幂的取值，然后花费 Θ(log𝑛)Θ(logn) 的时间选择等于 11 的二进制位对应的幂次乘到最终结果中．这就是快速幂的迭代版本实现．
伪代码如下：
𝐀𝐥𝐠𝐨𝐫𝐢𝐭𝐡𝐦 FastPow(𝑎,𝑛):𝐈𝐧𝐩𝐮𝐭. Base 𝑎 and exponent 𝑛.𝐎𝐮𝐭𝐩𝐮𝐭. Power 𝑎𝑛.𝐌𝐞𝐭𝐡𝐨𝐝.1𝑟𝑒𝑠𝑢𝑙𝑡←Id2𝐰𝐡𝐢𝐥𝐞 𝑛>0 𝐝𝐨3𝐢𝐟 𝑛mod2=1 𝐭𝐡𝐞𝐧4𝑟𝑒𝑠𝑢𝑙𝑡←𝑟𝑒𝑠𝑢𝑙𝑡⋅𝑎5𝐞𝐧𝐝 𝐢𝐟6𝑎←𝑎⋅𝑎7𝑛←𝑛/28𝐞𝐧𝐝 𝐰𝐡𝐢𝐥𝐞9𝐫𝐞𝐭𝐮𝐫𝐧 𝑟𝑒𝑠𝑢𝑙𝑡Algorithm FastPow(a,n):Input. Base a and exponent n.Output. Power an.Method.1result←Id2while n>0 do3if nmod2=1 then4result←result⋅a5end if6a←a⋅a7n←n/28end while9return result
利用这一方法计算快速幂，需要进行 Θ(log𝑛)Θ(logn) 次乘法运算．
递归版本
这一过程同样可以通过递归形式实现．注意到，指数 𝑛n 的二进制展开可以递归地写作
(𝑛𝑡𝑛𝑡−1⋯𝑛1𝑛0)2=2×(𝑛𝑡𝑛𝑡−1⋯𝑛1)2+𝑛0.(ntnt−1⋯n1n0)2=2×(ntnt−1⋯n1)2+n0.
因此，幂次 𝑎𝑛an 可以递归地计算为
𝑎𝑛=⎧{ {⎨{ {⎩1,𝑛=0,(𝑎⌊𝑛/2⌋)2,𝑛>0 and 𝑛 is even,(𝑎⌊𝑛/2⌋)2⋅𝑎,𝑛>0 and 𝑛 is odd.an={1,n=0,(a⌊n/2⌋)2,n>0 and n is even,(a⌊n/2⌋)2⋅a,n>0 and n is odd.
这就是快速幂的递归版本实现．
伪代码如下：
𝐀𝐥𝐠𝐨𝐫𝐢𝐭𝐡𝐦 FastPow(𝑎,𝑛):𝐈𝐧𝐩𝐮𝐭. Base 𝑎 and exponent 𝑛.𝐎𝐮𝐭𝐩𝐮𝐭. Power 𝑎𝑛.𝐌𝐞𝐭𝐡𝐨𝐝.1𝐢𝐟 𝑛=0 𝐭𝐡𝐞𝐧2𝐫𝐞𝐭𝐮𝐫𝐧 Id3𝐞𝐧𝐝 𝐢𝐟4𝑟𝑒𝑠𝑢𝑙𝑡←FastPow(𝑎,𝑛/2)5𝐢𝐟 𝑛mod2=0 𝐭𝐡𝐞𝐧6𝐫𝐞𝐭𝐮𝐫𝐧 𝑟𝑒𝑠𝑢𝑙𝑡⋅𝑟𝑒𝑠𝑢𝑙𝑡7𝐞𝐥𝐬𝐞8𝐫𝐞𝐭𝐮𝐫𝐧 𝑟𝑒𝑠𝑢𝑙𝑡⋅𝑟𝑒𝑠𝑢𝑙𝑡⋅𝑎9𝐞𝐧𝐝 𝐢𝐟Algorithm FastPow(a,n):Input. Base a and exponent n.Output. Power an.Method.1if n=0 then2return Id3end if4result←FastPow(a,n/2)5if nmod2=0 then6return result⋅result7else8return result⋅result⋅a9end if
利用这一方法计算快速幂，需要递归 Θ(log𝑛)Θ(logn) 次，同样需要 Θ(log𝑛)Θ(logn) 次乘法运算．尽管复杂度相同，由于递归本身有一定开销，所以实践中迭代版本的速度更快．
应用
模意义下取幂
给定三个整数 𝑎,𝑏,𝑝a,b,p，求 𝑎𝑏mod𝑝abmodp．其中 𝑝 ≥2p≥2．
这是一个非常常见的应用，例如它可以用于计算模意义下的乘法逆元．既然我们知道取模的运算不会干涉乘法运算，因此我们只需要在计算的过程中取模即可．
首先我们可以直接按照上述递归方法实现：
参考实现
C++Python
---|---
---|---
第二种实现方法是非递归式的．它在循环的过程中将二进制位为 1 时对应的幂累乘到答案中．尽管两者的理论复杂度是相同的，但第二种在实践过程中的速度是比第一种更快的，因为递归会花费一定的开销．
参考实现
C++Python
---|---
---|---
注意
- 模数通常情况下大于 11．在十分特殊的情况下，模数 𝑝p 可能等于 11，此时需要特殊考虑 𝑏 =0b=0 的情况．
- 当指数很大时，需利用 扩展欧拉定理 降幂后计算．
计算斐波那契数
根据斐波那契数列的递推式 𝐹𝑛 =𝐹𝑛−1 +𝐹𝑛−2Fn=Fn−1+Fn−2，我们可以构建一个 2 ×22×2 的矩阵来表示从 𝐹𝑖,𝐹𝑖+1Fi,Fi+1 到 𝐹𝑖+1,𝐹𝑖+2Fi+1,Fi+2 的变换．于是在计算这个矩阵的 𝑛n 次幂的时侯，我们使用快速幂的思想，可以在 Θ(log𝑛)Θ(logn) 的时间内计算出结果．对于更多的细节参见 斐波那契数列，矩阵快速幂的实现参见 矩阵加速递推 中的实现．
多次置换
问题描述
给你一个长度为 𝑛n 的序列和一个置换，把这个序列置换 𝑘k 次．
简单地把这个置换取 𝑘k 次幂，然后把它应用到序列上即可．时间复杂度为 𝑂(𝑛log𝑘)O(nlogk)．对于更多的细节参见 置换的复合．
注意
对这个置换建图，然后在每一个环上分别做 𝑘k 次幂（事实上等价于 𝑘k 对环长取模），可以在 𝑂(𝑛)O(n) 的时间复杂度下解决此问题．
加速几何中对点集的操作
HDU 4087 A Letter to Programmers
给定三维空间中 𝑛n 个点 𝑝𝑖pi，要求将 𝑚m 个操作都应用于这些点．包含 3 种操作：
- 沿某个向量移动点的位置（Shift）．
- 按比例缩放这个点的坐标（Scale）．
- 绕某条直线旋转（Rotate）．
还有一个特殊的操作，就是将某个操作序列重复 𝑘k 次（Repeat），Repeat 操作可以嵌套．输出操作结束后每个点的坐标．
参考 向量与矩阵 中的内容，每一种操作都可以用一个变换矩阵表示，一系列连续的变换可以用矩阵的乘积来表示．一个 Repeat 操作就相当于取一个矩阵的 𝑘k 次幂．这样可以用 𝑂(𝑚log𝑘)O(mlogk) 的时间计算出整个变换序列最终形成的矩阵．最后将它应用到 𝑛n 个点上，总复杂度 𝑂(𝑛 +𝑚log𝑘)O(n+mlogk)．
定长路径计数
问题描述
给一个有向图（边权为 1），求任意两点 𝑢,𝑣u,v 间从 𝑢u 到 𝑣v，长度为 𝑘k 的路径的条数．
我们把该图的邻接矩阵 𝑀M 取 𝑘k 次幂，那么 𝑀𝑖,𝑗Mi,j 就表示从 𝑖i 到 𝑗j 长度为 𝑘k 的路径的数目．该算法的复杂度是 𝑂(𝑛3log𝑘)O(n3logk)．有关该算法的细节请参见 矩阵 页面．
模意义下的整数乘法
问题描述
给定非负整数 𝑎,𝑏a,b 和正整数 𝑚m，计算 𝑎 ×𝑏mod𝑚a×bmodm，其中 𝑎,𝑏 ≤𝑚 ≤1018a,b≤m≤1018．
与二进制取幂的思想一样，这次我们将其中的一个乘数表示为若干个 2 的整数次幂的和的形式．因为在对一个数做乘 2 并取模的运算的时侯，我们可以转化为加减操作防止整型溢出．这样可以在 𝑂(log𝑚)O(logm) 的时间复杂度下解决问题．递归方法如下：
𝑎⋅𝑏=⎧{ {⎨{ {⎩0if 𝑎=02⋅𝑎2⋅𝑏if 𝑎>0 and 𝑎 even2⋅𝑎−12⋅𝑏+𝑏if 𝑎>0 and 𝑎 odda⋅b={0if a=02⋅a2⋅bif a>0 and a even2⋅a−12⋅b+bif a>0 and a odd
但在实际使用中，此方法由于引入了更大的计算复杂度导致时间效率不优．实际编程中通常利用 快速乘 来进行模数范围在 long long 时的乘法操作．
高精度快速幂
前置技能：大整数乘法
[洛谷 P1045 [NOIP 2003 普及组] 麦森数](https://www.luogu.com.cn/problem/P1045)
给定整数 𝑃P（1000 <𝑃 <31000001000<P<3100000），计算 2𝑃 −12P−1 的位数与最后 500500 位数字（用十进制数表示），不足 500500 位时高位补 0．
代码实现
---|---
## 底数固定的预处理快速幂
当底数 𝑎a 固定时，可以利用 [分块思想](../../ds/decompose/)，用一定的时间预处理后用 𝑂(1)O(1) 的时间回答一次幂询问．这一算法也常称为光速幂．过程如下：
1. 选定一个数 𝑠s，预处理出 𝑎0,𝑎1,⋯,𝑎𝑠−1a0,a1,⋯,as−1 与 𝑎0,𝑎𝑠,⋯,𝑎⌊𝑝/𝑠⌋𝑠a0,as,⋯,a⌊p/s⌋s 的值并存在两个数组里；
2. 对于每一次询问 𝑎𝑏ab，将 𝑏b 拆分成 ⌊𝑏/𝑠⌋𝑠 +(𝑏mod𝑠)⌊b/s⌋s+(bmods)，则 𝑎𝑏 =𝑎⌊𝑏/𝑠⌋𝑠 ⋅𝑎𝑏mod𝑠ab=a⌊b/s⌋s⋅abmods，就可以 𝑂(1)O(1) 求出答案．
假设指数 𝑏b 的范围是 [0,𝑛][0,n]，那么块长 𝑠s 经常选择为 √𝑛n 或者与之相近的 22 的幂次．选择 √𝑛n 可以获得最优的预处理复杂度 𝑂(√𝑛)O(n)，而选择 22 的幂次可以使用位操作简化计算．
特别地，对于模意义下幂的计算，底数 𝑎a 相同隐含着模数 𝑚m 也要相同这一要求．由于 [扩展欧拉定理](../number-theory/fermat/#扩展欧拉定理)，对于任意模数 𝑚m，预处理的指数范围上界为 𝑛 =2𝜑(𝑚)n=2φ(m)；对于素模数 𝑝p，预处理的范围上界为 𝑛 =𝑝 −1n=p−1．这两种情形预处理的复杂度都是 𝑂(√𝑚)O(m)．
参考代码
---|---
习题
- 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 协议之条款下提供，附加条款亦可能应用