1. 项目概述为什么“快速幂”是算法竞赛的必刷题如果你参加过任何算法竞赛或者刷过LeetCode、牛客网这类题库一定对“快速幂”这个名字不陌生。它几乎是所有涉及大数取模、指数运算题目的核心解法从简单的“计算a的b次方”到复杂的“矩阵快速幂求解递推数列”其身影无处不在。然而很多初学者第一次接触时往往会被其“递归”、“位运算”这些字眼吓到觉得这又是一个深奥难懂的“黑魔法”。今天我们就来彻底拆解这个“小肥杨训练营”里的经典模板——快速幂我会用最直白的方式让你不仅记住模板更理解其背后的每一个“为什么”做到举一反三真正内化成自己的解题武器。简单来说快速幂要解决的核心问题是如何用远小于O(n)的时间复杂度计算出一个数a的n次方a^n。最朴素的想法是循环n次每次乘以a时间复杂度是O(n)。当n是一个巨大的数比如10^9时这个方法是完全不可行的。快速幂通过将指数n进行二进制拆解能将时间复杂度优化到O(log n)这是一个质的飞跃。这个技巧本身并不复杂但它蕴含的“分治”和“二进制思想”是理解许多更高级算法如矩阵快速幂、快速傅里叶变换的基石。接下来我将从原理、模板、变形到实战带你完整走一遍。2. 核心原理拆解从“慢速幂”到“快速幂”的思维跃迁要理解快速幂我们必须先抛弃那个直观的“连乘”想法。它的核心洞察在于任何指数都可以用二进制来表示而乘方运算具有结合律。2.1 二进制视角下的指数分解我们以计算 3^13 为例。13的二进制是 1101这意味着 13 1 * 2^3 1 * 2^2 0 * 2^1 1 * 2^0 8 4 0 1那么3^13 就可以表示为 3^13 3^(8401) 3^8 * 3^4 * 3^0 * 3^1注意这里3^0就是1可以忽略。所以我们实际上只需要计算 3^1, 3^2, 3^4, 3^8 这些值然后根据二进制位是否为1决定是否乘到结果里。这里的精妙之处在于3^2 可以通过 3^1 * 3^1 得到3^4 可以通过 3^2 * 3^2 得到3^8 可以通过 3^4 * 3^4 得到。也就是说每一个更高位的幂值都可以由低一位的幂值平方得来。我们不需要重复计算只需要不断地“翻倍”即可。2.2 迭代过程模拟让我们手动模拟一下计算 3^13 的快速幂过程设定结果res 1底数a 3指数n 13。第一轮n 13二进制1101最低位是1奇数说明当前位有效。将当前的底数a乘入结果res 1 * 3 3。然后底数自我平方以准备下一位a 3 * 3 9。指数右移一位相当于除以2向下取整n 6。第二轮n 6二进制110最低位是0偶数说明当前位无效结果res不变res 3。底数继续自我平方a 9 * 9 81。指数右移n 3。第三轮n 3二进制11最低位是1有效。将当前底数乘入结果res 3 * 81 243。底数平方a 81 * 81 6561。指数右移n 1。第四轮n 1二进制1最低位是1有效。将当前底数乘入结果res 243 * 6561 1594323。底数平方a 6561 * 6561但此时指数已为0无需计算。指数右移n 0。循环结束得到最终结果res 1594323正是 3^13。这个过程只进行了大约 log2(13) ≈ 4 轮循环而不是13次乘法。这就是效率提升的关键我们通过“平方”操作快速生成对应二进制位的权重通过“判断奇偶”来决定是否收集该权重。注意在实际编程中我们通常使用while(n 0)作为循环条件并在循环内通过n 1来判断奇偶二进制最低位是否为1通过n 1来右移指数。这是位运算的经典应用效率远高于n % 2和n / 2。3. 标准模板实现与逐行解析理解了原理我们来看最核心的代码模板。这里给出递归和迭代两种写法但竞赛和工程中迭代法是绝对主流因为它没有递归的函数调用开销且代码更简洁。3.1 迭代法模板推荐这是你必须刻在脑子里的“小肥杨训练营”标准模板。我们假设题目要求计算a^n % mod这是最常见的情形。// 计算 a^n % mod long long fastPow(long long a, long long n, long long mod) { long long res 1 % mod; // 初始化结果注意这里直接对mod取余处理了n0的情况 a % mod; // 先取模防止a过大导致后续乘法溢出 while (n 0) { // 如果当前二进制位为1则将当前的a乘入结果 if (n 1) { res (res * a) % mod; } // 将底数平方为下一个二进制位做准备 a (a * a) % mod; // 指数右移一位相当于除以2 n 1; } return res; }逐行解析与避坑指南long long res 1 % mod;为什么是1 % mod而不是1这是处理n0和mod1的特殊情况。任何数的0次方定义为1。如果mod1那么结果应为1 % 1 0。如果直接写res 1当mod1时函数会错误地返回1。这是一个非常隐蔽的边界条件坑点。a % mod;为什么先取模输入参数a可能非常大比如10^18如果不先取模在后续的a a * a运算中极有可能在取模前就发生溢出即使使用long long。先取模可以保证中间运算值始终控制在mod的范围内是防止整数溢出的关键步骤。while (n 0)循环条件。当n的二进制位被右移耗尽后变为0循环结束。if (n 1)n 1是位运算效果等同于n % 2 1但效率更高。它用于检查n当前二进制表示的最低位是否为1。res (res * a) % mod;如果当前位为1说明这个“权重”当前的a值需要贡献到最终结果里。乘法和取模必须同步进行防止溢出。a (a * a) % mod;这是快速幂的灵魂。无论当前位是否有效底数a都要自我平方以生成下一个二进制位对应的权重即a^1, a^2, a^4, a^8...。n 1;将n右移一位等价于n / 2但同样效率更高。它让我们能依次检查n的每一个二进制位。实操心得在竞赛中我习惯将res、a都定义为long long类型并且在每一次乘法后立即取模。即使题目可能不要求取模养成这个习惯也能让你在需要时无缝切换。另外对于mod为质数的情况结合费马小定理求逆元是更高级的用法但快速幂模板是这一切的基础。3.2 递归法模板递归写法更直观地体现了“分治”思想a^n a^(n/2) * a^(n/2) * a?如果n是奇数多乘一个a。long long fastPowRecur(long long a, long long n, long long mod) { if (n 0) return 1 % mod; long long half fastPowRecur(a, n / 2, mod); long long result (half * half) % mod; if (n % 2 1) { // 或者 n 1 result (result * a) % mod; } return result; }虽然递归写法清晰但其递归深度为 O(log n)有栈溢出风险尽管对于指数n来说通常安全且函数调用开销稍大。在绝大多数场景下迭代法是更优选择。4. 核心变形当快速幂遇上矩阵与乘法快速幂的强大之处在于它不仅仅适用于整数乘法。任何满足结合律的运算都可以套用这个“反复平方”的思想。最常见的两种变形是矩阵快速幂和快速乘。4.1 矩阵快速幂解决线性递推的利器这是快速幂最经典的应用拓展。例如斐波那契数列 F(n) F(n-1) F(n-2)我们希望能用 O(log n) 的时间计算第n项。核心思路将递推关系转化为矩阵乘法。 对于斐波那契数列存在以下关系[ F(n) ] [1 1] * [F(n-1)] [ F(n-1) ] [1 0] [F(n-2)]更一般地可以写成[F(n), F(n-1)]^T M * [F(n-1), F(n-2)]^T其中 M 是系数矩阵[[1,1],[1,0]]。 那么[F(n), F(n-1)]^T M^(n-1) * [F(1), F(0)]^T。问题就转化成了计算矩阵 M 的 (n-1) 次幂。这时我们只需要把快速幂模板中的“数字乘法”和“取模”换成“矩阵乘法”和“矩阵每个元素取模”即可。矩阵快速幂模板示例#include vector using namespace std; typedef vectorvectorlong long Matrix; // 矩阵乘法结果对mod取模 Matrix matrixMultiply(const Matrix A, const Matrix B, long long mod) { int n A.size(); Matrix C(n, vectorlong long(n, 0)); for (int i 0; i n; i) { for (int j 0; j n; j) { for (int k 0; k n; k) { C[i][j] (C[i][j] A[i][k] * B[k][j]) % mod; } } } return C; } // 矩阵快速幂 Matrix matrixFastPow(Matrix base, long long power, long long mod) { int n base.size(); // 初始化单位矩阵 Matrix res(n, vectorlong long(n, 0)); for (int i 0; i n; i) res[i][i] 1 % mod; while (power 0) { if (power 1) { res matrixMultiply(res, base, mod); } base matrixMultiply(base, base, mod); power 1; } return res; }注意事项单位矩阵相当于数字快速幂里的res 1。对于n阶方阵单位矩阵是对角线为1其余为0的矩阵。复杂度矩阵乘法复杂度是 O(k^3)其中k是矩阵阶数。因此矩阵快速幂的总复杂度是 O(k^3 log n)。对于斐波那契数列k2这非常高效。应用场景所有线性齐次递推关系如斐波那契、Tribonacci数列都可以通过构造转移矩阵用矩阵快速幂在 O(k^3 log n) 时间内求解第n项。4.2 快速乘解决模数下的乘法溢出在标准快速幂模板中我们假设(a * a) % mod不会溢出。但如果模数mod很大比如接近long long上限两个mod级别的数相乘即使在取模前也会溢出long long在C中大约是9e18。这时就需要“快速乘”。它的思想和快速幂一模一样只是把“幂运算”降级为“乘法运算”用于计算(a * b) % mod而不溢出。原理将乘法转化为加法。a * b可以看作是 b 个 a 相加。利用二进制思想我们可以用 O(log b) 的时间完成。// 快速乘计算 (a * b) % mod防止溢出 long long fastMul(long long a, long long b, long long mod) { long long res 0; a % mod; while (b 0) { if (b 1) { res (res a) % mod; // 这里做加法 } a (a a) % mod; // a a * 2 b 1; } return res; } // 使用快速乘的快速幂 long long fastPowWithMul(long long a, long long n, long long mod) { long long res 1 % mod; a % mod; while (n 0) { if (n 1) { res fastMul(res, a, mod); // 乘法改用快速乘 } a fastMul(a, a, mod); // 平方也用快速乘 n 1; } return res; }重要提示快速乘虽然解决了溢出问题但将乘法的 O(1) 时间变成了 O(log b)会带来常数级别的性能损耗。只有在模数极大确实会发生溢出的情况下才需要使用。对于一般的题目mod通常在1e97左右直接使用(a * b) % mod是安全的因为两个1e97级别的数相乘不会超过 1e18仍在long long范围内。5. 实战应用与场景剖析掌握了模板和变形我们来看看快速幂在具体问题中是如何大显身手的。5.1 场景一大数取模求幂最直接的应用例题计算a^b % p。(1 a, b, p 10^18)。 这就是模板题。直接套用迭代法快速幂即可。如果p也很大需要使用带快速乘的版本。5.2 场景二求乘法逆元费马小定理在组合数学取模运算中我们经常需要计算(a / b) % mod。除法取模不能直接进行需要转化为乘以其“逆元”。当mod是质数时根据费马小定理b的逆元就是b^(mod-2) % mod。计算过程检查mod是否为质数且b % mod ! 0。使用快速幂计算inv_b fastPow(b, mod-2, mod)。则(a / b) % mod (a * inv_b) % mod。这是快速幂在数论中的一个关键应用在计算组合数 C(n, m) % p 时必不可少。5.3 场景三矩阵快速幂求解线性递推例题斐波那契数列第n项n可以大到10^18。 如前所述构造矩阵M [[1,1],[1,0]]计算M^(n-1)再乘以初始向量[F1, F0]^T [1, 0]^T结果矩阵的第一行第一列元素就是 F(n)。更复杂的递推例如f(n) 2*f(n-1) 3*f(n-2) 5*f(n-3)。我们可以构造一个3x3的转移矩阵M [[2, 3, 5], [1, 0, 0], [0, 1, 0]]初始向量为[f(2), f(1), f(0)]。则[f(n), f(n-1), f(n-2)]^T M^(n-2) * [f(2), f(1), f(0)]^T。5.4 场景四指数非常巨大的情况欧拉降幂有时我们会遇到a^b % m中b本身就是一个巨大数字比如一个长字符串表示的数字。直接快速幂无法处理因为指数b无法存入整数变量。这时需要用到欧拉降幂公式a^b % m a^(b % φ(m) φ(m)) % m当b φ(m)时成立。其中φ(m)是欧拉函数。 这样我们可以先用高精度或逐位读取的方式计算出b_mod b % φ(m)然后对a^(b_mod φ(m))使用快速幂。这属于快速幂的进阶应用需要数论知识作为支撑。6. 常见问题与调试技巧实录在实际编码和解题中以下几个坑我几乎每次都提醒自己和学员要注意。6.1 溢出问题何时用快速乘这是一个高频错误。判断逻辑如下如果模数mod 1e9那么(a * a) % mod中的a*a最大约为1e18在Clong long(约9e18) 范围内安全。如果模数mod在1e10到1e18之间a*a就可能超过long long范围必须使用快速乘。一个简单的记忆法如果题目给出的mod是1e97这种经典质数直接用普通乘法取模如果模数是一个接近1e18的大数就要警惕。调试技巧在本地测试时可以故意用极大值如a1e18, n1e18, mod1e18测试你的快速幂函数。如果结果错误或程序异常很可能就是乘法溢出了。6.2 边界条件n0, mod1这是模板代码第一行long long res 1 % mod;要解决的问题。n0数学上定义为1。我们的循环while(n0)不会执行直接返回初始值1%mod。mod1任何数对1取模都为0。所以1%10是正确的。如果写res1就会错误地返回1。6.3 负数指数的处理标准的快速幂通常要求指数n为非负整数。如果题目涉及负数指数如计算a^(-n) % mod这通常意味着求a在模mod下的逆元的n次方。即a^(-n) % mod (a^(-1))^n % mod inv(a)^n % mod。 你需要先判断a与mod是否互质通常mod为质数用费马小定理求出inv(a)再对inv(a)做n次方的快速幂。6.4 矩阵快速幂的初始化与维度单位矩阵初始化务必确保res初始化为正确的单位矩阵而不是全1矩阵或零矩阵。单位矩阵是矩阵乘法中的“1”。矩阵维度转移矩阵base的维度由递推式的阶数决定。例如f(n)依赖于前k项则通常构造k x k的方阵。务必检查矩阵乘法的维度匹配(m x n) * (n x p)。效率矩阵快速幂的瓶颈在于矩阵乘法 O(k^3)。如果k较大比如10log n即使很小整体计算量也可能很大。有时需要优化矩阵乘法如Strassen算法但在竞赛中k通常很小2, 3, 5。6.5 一个综合排查表问题现象可能原因排查方法结果错误小数据对大数据错乘法溢出检查模数大小考虑使用快速乘结果始终为0或1边界条件处理错误n0或 mod1检查res初始化是否为1 % mod递归版本栈溢出指数n过大递归深度过深改用迭代法矩阵快速幂结果全0res未初始化为单位矩阵检查初始化代码矩阵快速幂运行时错误矩阵维度不匹配检查matrixMultiply函数中的循环边界取模结果出现负数C中%对负数取模结果为负使用(x % mod mod) % mod修正最后我的个人体会是快速幂模板本身几分钟就能记住但真正理解其二进制分解和结合律的思想才能让你在遇到“快速幂的变体”时游刃有余。比如你可以思考如果运算不是乘法而是加法并且定义“结合”为取最大值能否设计一个“快速幂”来求某个操作重复n次后的结果这种思维训练比死记硬背十个模板更有价值。下次当你看到某个运算需要重复巨量次数时不妨先想想这个运算满足结合律吗我能用它来“平方”吗如果能那么快速幂就是你的最佳选择。