1. 项目概述为什么我们需要快速幂在算法竞赛或者高性能计算的后台开发中我们常常会遇到一个看似简单却暗藏玄机的问题计算一个数的大整数次幂比如计算a的n次方即a^n。新手程序员的第一反应往往是写一个循环连续乘n次。这种方法直观易懂在n很小的时候完全没问题。但一旦n的规模上升到10^9甚至更大这种线性时间复杂度O(n)的算法就会变得完全不可接受程序会陷入漫长的等待甚至因为超时或溢出而失败。这就是快速幂算法登场的时候。它能在O(log n)的时间复杂度内完成计算将指数级的计算量压缩到对数级。对于n10^9朴素算法需要10亿次乘法而快速幂只需要大约30次。这个差距是数量级的。快速幂不仅是解决大数幂运算的核心工具其背后“分而治之”和“二进制分解”的思想更是理解许多高级算法如矩阵快速幂、求解线性递推的基石。今天我们就来彻底拆解这个经典算法并用 C 实现它同时分享一些实战中容易踩的坑和优化技巧。2. 算法核心思想与数学原理拆解快速幂算法的精髓在于两个核心思想指数的二进制表示和幂的乘法结合律。它不像我们数数一样一个一个乘而是跳着乘每次让底数翻倍平方然后根据指数的二进制位决定是否将当前的累积结果乘到最终答案里。2.1 从朴素乘法到“跳着乘”我们先看一个具体的例子计算3^13。朴素方法3 * 3 * 3 * ... * 3 总共12次乘法。快速幂思路我们把指数13用二进制表示13 (1101)_2。这意味着13 2^3 2^2 0*2^1 2^0 8 4 0 1。那么3^13 3^(841) 3^8 * 3^4 * 3^1。注意3^2对应的二进制位是0所以不乘。关键来了3^1,3^2,3^4,3^8这些项之间有什么关系3^2 (3^1)^2,3^4 (3^2)^2,3^8 (3^4)^2。也就是说我们可以从3^1开始不断地将当前结果平方就能得到所有以2的幂次为指数的值。计算过程模拟初始化结果res 1 当前底数base 3 指数n 13。n的二进制最后一位是1 (13 1 1) 所以res * base-res 1 * 3 3。然后base平方base 3*3 9n右移一位变成6。n6最后一位是0所以结果不变。base平方base 9*9 81n右移一位变成3。n3最后一位是1res * base-res 3 * 81 243。base平方base 81*81 6561n右移一位变成1。n1最后一位是1res * base-res 243 * 6561 1594323。base平方这步已不影响结果n右移一位变成0循环结束。最终res 1594323 正是3^13。整个过程中我们只进行了几次乘法和平方操作次数取决于指数n的二进制位数即O(log n)。2.2 递归与迭代两种实现视角理解了这个原理我们可以从两个角度实现它递归实现思路最直接对应公式a^n a^(n/2) * a^(n/2)当n为偶数或者a^n a^(n/2) * a^(n/2) * a当n为奇数。不断将问题规模减半。迭代实现即上面模拟的过程通过循环和位运算实现。这是更常用、效率也稍高的方法因为避免了递归的函数调用开销。我们后续的代码实现和讨论将主要围绕迭代版本展开。注意这里隐含了一个非常重要的前提——模运算。在实际应用中a^n的结果通常会非常大远超long long的表示范围。因此快速幂几乎总是和取模运算结合使用即计算(a^n) % mod。幸运的是取模运算满足(a * b) % mod ((a % mod) * (b % mod)) % mod所以我们可以放心地在每一步乘法后都进行取模防止中间结果溢出。这是实战中的标配写法。3. C 迭代实现与逐行解析下面给出一个健壮、通用的迭代快速幂函数模板它包含了取模操作并附上详细的注释。#include iostream using namespace std; /** * 快速幂算法 (迭代版) * param a 底数 * param n 指数 (非负整数) * param mod 模数 (可选默认为1即不取模。通常应传入一个质数如1e97) * return 计算 (a^n) % mod 的结果 */ long long fastPow(long long a, long long n, long long mod 1) { // 处理边界情况任何数的0次方定义为1 if (n 0) return 1 % mod; // 如果模数为1任何数模1都是0直接返回0。这是一个特例处理。 if (mod 1) return 0; long long res 1 % mod; // 初始化结果为1并先取模确保初始值在模范围内 a % mod; // 先将底数取模防止后续乘法溢出 while (n 0) { // 1. 检查当前指数n的二进制最低位是否为1 if (n 1) { // 如果为1说明当前二进制位有效将当前的底数乘入结果 res (res * a) % mod; } // 2. 无论当前位是否有效底数都需要平方为下一位做准备 a (a * a) % mod; // 平方后同样要取模 // 3. 将指数n右移一位相当于除以2并向下取整检查下一个二进制位 n 1; } return res; } int main() { // 示例1计算 3^13不取模 cout 3^13 fastPow(3, 13) endl; // 输出 1594323 // 示例2计算 3^13 % 1000 (求最后三位) cout 3^13 mod 1000 fastPow(3, 13, 1000) endl; // 输出 323 // 示例3大数场景计算 2^100 % 1000000007 (常见于算法题) const int MOD 1000000007; cout 2^100 mod MOD fastPow(2, 100, MOD) endl; // 输出 976371285 return 0; }3.1 关键代码行深度解读long long类型选择底数、指数、结果和模数都使用long long。这是因为即使取了模中间计算a * a时a本身可能已经接近模数例如1e9量级相乘就会溢出int范围约2e9。使用long long是安全的底线。在极端情况下模数接近1e18则需要使用快速乘或__int128来防止long long乘法溢出这属于进阶话题。初始取模a % mod和res 1 % mod这是非常关键的一步被称为“预取模”。它保证了在进入循环前a和res的值都严格小于mod。这样在后续的res * a和a * a运算中虽然乘积可能超过mod但绝不会超过(mod-1)*(mod-1)这通常仍在long long的表示范围内对于mod 1e9是安全的从而有效避免了不可控的溢出。这是一个重要的防御性编程技巧。循环条件while (n 0)只要指数n还没被右移到0就继续。每次循环处理n的一个二进制位。位运算n 1和n 1n 1用于检查n的二进制最低位是否为1效率远高于n % 2。n 1等价于n / 2但位运算通常更快。这是快速幂迭代实现的核心操作。取模运算的位置在每一次乘法 (res * a) 和平方 (a * a) 之后立即取模。这是保证计算过程始终在可控范围内的铁律。绝对不能先算完整个幂再取模那样中间值早就溢出了。4. 递归实现、矩阵快速幂与常见变体虽然迭代版本是主流但了解递归版本有助于加深对分治思想的理解。4.1 递归实现long long fastPowRecur(long long a, long long n, long long mod 1) { if (mod 1) return 0; if (n 0) return 1 % mod; a % mod; long long half fastPowRecur(a, n / 2, mod); if (n % 2 0) { // n为偶数: a^n (a^(n/2))^2 return (half * half) % mod; } else { // n为奇数: a^n (a^(n/2))^2 * a return (((half * half) % mod) * a) % mod; } }递归的代码更简洁地反映了数学定义但存在递归栈开销且对于极深的递归虽然log(n)深度通常没问题可能不如迭代稳定。4.2 矩阵快速幂从数到矩阵的飞跃快速幂的思想不仅能用于数字更能用于任何满足结合律的运算比如矩阵乘法。这就是强大的矩阵快速幂。应用场景主要用于求解线性递推式例如斐波那契数列F(n) F(n-1) F(n-2)。我们可以将递推式转化为矩阵形式[ F(n) ] [1 1] ^ (n-1) * [F(1)] [ F(n-1) ] [1 0] [F(0)]计算一个矩阵的n次幂如果直接用朴素矩阵乘法复杂度是O(n * m^3)m为矩阵阶数。而使用矩阵快速幂复杂度降为O(m^3 * log n)。对于n高达1e18的情况这是唯一可行的解法。C 实现核心你需要先实现一个矩阵类及其乘法运算符重载然后将上面快速幂函数中的long long乘法替换为矩阵乘法res1替换为单位矩阵。// 以2x2矩阵为例 const int MOD 1e97; struct Matrix { long long m[2][2]; Matrix() { memset(m, 0, sizeof(m)); } Matrix operator*(const Matrix other) const { Matrix res; for (int i 0; i 2; i) for (int j 0; j 2; j) for (int k 0; k 2; k) res.m[i][j] (res.m[i][j] m[i][k] * other.m[k][j]) % MOD; return res; } }; Matrix matrixFastPow(Matrix a, long long n) { Matrix res; // 将res初始化为单位矩阵 res.m[0][0] res.m[1][1] 1; while (n) { if (n 1) res res * a; a a * a; n 1; } return res; } // 使用 matrixFastPow 可以快速计算斐波那契数列第n项4.3 支持负指数与浮点数的快速幂有时我们需要计算a^(-n)或浮点数的幂。思路是进行转化负指数a^(-n) 1 / (a^n)。在实现时先计算a^n然后求其乘法逆元在模意义下或直接做浮点数除法。浮点数底数算法逻辑完全不变只是数据类型换成double并且不再需要取模运算。但要注意浮点数的精度误差特别是当指数很大时。double fastPowDouble(double a, long long n) { double res 1.0; while (n) { if (n 1) res * a; a * a; n 1; } return res; } // 处理负指数 double myPow(double a, long long n) { if (n 0) return fastPowDouble(a, n); else return 1.0 / fastPowDouble(a, -n); }5. 实战应用场景与性能对比分析快速幂绝不仅仅是书本上的算法它在以下场景中不可或缺密码学RSA等加密算法中大量的大数模幂运算 (a^b mod m) 是核心操作完全依赖快速幂。算法竞赛计算组合数C(n, m) % p需要用到费马小定理求逆元其中就涉及快速幂。求解线性递推数列的第n项如斐波那契使用矩阵快速幂。任何需要计算大指数取模的题目。数学计算需要计算x^y且y很大时例如在物理模拟或金融模型中。性能对比实测 我写了一个简单的测试计算2^1000000000 % 100000000710亿次方。朴素循环理论上需要10亿次乘法和取模在普通电脑上几分钟都无法完成实际因超时无法测试。快速幂迭代时间复杂度O(log n)大约log2(1e9) ≈ 30次循环迭代。实测时间在0.0001秒级别几乎是瞬间完成。这个对比直观地展示了从O(n)到O(log n)的威力。在数据规模面前高效的算法就是魔法。6. 常见问题、调试技巧与避坑指南即使理解了原理实现时也可能遇到各种问题。下面是我在多年刷题和项目中总结的“坑点”。6.1 典型错误与修正错误1忽略取模导致溢出// 错误写法 long long fastPowWrong(long long a, long long n, long long mod) { long long res 1; while (n) { if (n 1) res res * a; // 这里可能溢出 a a * a; // 这里也可能溢出 n 1; } return res % mod; // 最后才取模为时已晚 }修正必须像标准实现那样在每一次乘法后立即取模。错误2指数为0或底数为0时的边界处理0^0在数学上是未定义的但在编程题中常规定义为1。我们的实现 (n0时返回1%mod) 符合这一惯例。计算0^n (n0)我们的实现 (a%mod后进入循环) 会得到正确结果0。如果模数mod1任何数取模1都是0。我们在函数开头做了特判直接返回0避免不必要的计算。错误3使用int类型导致溢出这是最隐蔽的错误。即使最终结果在int范围内中间计算a * a也可能溢出。始终坚持使用long long作为与乘幂相关的变量类型。6.2 调试技巧小数据验证用cout打印循环每一步的resan的值对照手动计算过程。例如计算3^5。对比验证写一个朴素的for循环函数计算小范围的a^n % mod与快速幂的结果对比。单元测试准备多组测试数据包括n0,n1,a0,mod1, 大指数等边界情况。6.3 进阶问题模数下的乘法溢出当模数mod很大比如1e18时即使a moda * a也可能超过long long的范围约9e18导致溢出。解决方法有使用__int128如果编译器支持如GCC可以用__int128存储中间乘积然后再取模。res (__int128(res) * a) % mod; a (__int128(a) * a) % mod;使用快速乘算法模仿快速幂将乘法转化为加法在加法的每一步进行取模确保不溢出。但这会增加一个log的常数。long long quickMul(long long a, long long b, long long mod) { long long res 0; while (b) { if (b 1) res (res a) % mod; a (a a) % mod; b 1; } return res; } // 然后在快速幂中用 quickMul 替换普通的乘法6.4 关于%运算符和负数的处理C 中的%运算符当被除数为负数时结果也为负满足(a/b)*b a%b a。在我们的场景中底数a和结果res始终是非负的因为我们对a取了模所以不会遇到此问题。但如果你的输入a可能为负安全的做法是a (a % mod mod) % mod;这能确保a被调整到[0, mod)的正数范围内。最后记住这个算法的模板。在竞赛中它应该像呼吸一样自然。当你看到“求a^b mod p”或者递推式求第n项时快速幂就是你工具箱里的第一把利器。理解其二进制分解的本质你就能轻松驾驭它甚至将其思想迁移到其他符合结合律的运算上去。
快速幂算法精讲：从O(n)到O(log n)的大数幂运算优化
1. 项目概述为什么我们需要快速幂在算法竞赛或者高性能计算的后台开发中我们常常会遇到一个看似简单却暗藏玄机的问题计算一个数的大整数次幂比如计算a的n次方即a^n。新手程序员的第一反应往往是写一个循环连续乘n次。这种方法直观易懂在n很小的时候完全没问题。但一旦n的规模上升到10^9甚至更大这种线性时间复杂度O(n)的算法就会变得完全不可接受程序会陷入漫长的等待甚至因为超时或溢出而失败。这就是快速幂算法登场的时候。它能在O(log n)的时间复杂度内完成计算将指数级的计算量压缩到对数级。对于n10^9朴素算法需要10亿次乘法而快速幂只需要大约30次。这个差距是数量级的。快速幂不仅是解决大数幂运算的核心工具其背后“分而治之”和“二进制分解”的思想更是理解许多高级算法如矩阵快速幂、求解线性递推的基石。今天我们就来彻底拆解这个经典算法并用 C 实现它同时分享一些实战中容易踩的坑和优化技巧。2. 算法核心思想与数学原理拆解快速幂算法的精髓在于两个核心思想指数的二进制表示和幂的乘法结合律。它不像我们数数一样一个一个乘而是跳着乘每次让底数翻倍平方然后根据指数的二进制位决定是否将当前的累积结果乘到最终答案里。2.1 从朴素乘法到“跳着乘”我们先看一个具体的例子计算3^13。朴素方法3 * 3 * 3 * ... * 3 总共12次乘法。快速幂思路我们把指数13用二进制表示13 (1101)_2。这意味着13 2^3 2^2 0*2^1 2^0 8 4 0 1。那么3^13 3^(841) 3^8 * 3^4 * 3^1。注意3^2对应的二进制位是0所以不乘。关键来了3^1,3^2,3^4,3^8这些项之间有什么关系3^2 (3^1)^2,3^4 (3^2)^2,3^8 (3^4)^2。也就是说我们可以从3^1开始不断地将当前结果平方就能得到所有以2的幂次为指数的值。计算过程模拟初始化结果res 1 当前底数base 3 指数n 13。n的二进制最后一位是1 (13 1 1) 所以res * base-res 1 * 3 3。然后base平方base 3*3 9n右移一位变成6。n6最后一位是0所以结果不变。base平方base 9*9 81n右移一位变成3。n3最后一位是1res * base-res 3 * 81 243。base平方base 81*81 6561n右移一位变成1。n1最后一位是1res * base-res 243 * 6561 1594323。base平方这步已不影响结果n右移一位变成0循环结束。最终res 1594323 正是3^13。整个过程中我们只进行了几次乘法和平方操作次数取决于指数n的二进制位数即O(log n)。2.2 递归与迭代两种实现视角理解了这个原理我们可以从两个角度实现它递归实现思路最直接对应公式a^n a^(n/2) * a^(n/2)当n为偶数或者a^n a^(n/2) * a^(n/2) * a当n为奇数。不断将问题规模减半。迭代实现即上面模拟的过程通过循环和位运算实现。这是更常用、效率也稍高的方法因为避免了递归的函数调用开销。我们后续的代码实现和讨论将主要围绕迭代版本展开。注意这里隐含了一个非常重要的前提——模运算。在实际应用中a^n的结果通常会非常大远超long long的表示范围。因此快速幂几乎总是和取模运算结合使用即计算(a^n) % mod。幸运的是取模运算满足(a * b) % mod ((a % mod) * (b % mod)) % mod所以我们可以放心地在每一步乘法后都进行取模防止中间结果溢出。这是实战中的标配写法。3. C 迭代实现与逐行解析下面给出一个健壮、通用的迭代快速幂函数模板它包含了取模操作并附上详细的注释。#include iostream using namespace std; /** * 快速幂算法 (迭代版) * param a 底数 * param n 指数 (非负整数) * param mod 模数 (可选默认为1即不取模。通常应传入一个质数如1e97) * return 计算 (a^n) % mod 的结果 */ long long fastPow(long long a, long long n, long long mod 1) { // 处理边界情况任何数的0次方定义为1 if (n 0) return 1 % mod; // 如果模数为1任何数模1都是0直接返回0。这是一个特例处理。 if (mod 1) return 0; long long res 1 % mod; // 初始化结果为1并先取模确保初始值在模范围内 a % mod; // 先将底数取模防止后续乘法溢出 while (n 0) { // 1. 检查当前指数n的二进制最低位是否为1 if (n 1) { // 如果为1说明当前二进制位有效将当前的底数乘入结果 res (res * a) % mod; } // 2. 无论当前位是否有效底数都需要平方为下一位做准备 a (a * a) % mod; // 平方后同样要取模 // 3. 将指数n右移一位相当于除以2并向下取整检查下一个二进制位 n 1; } return res; } int main() { // 示例1计算 3^13不取模 cout 3^13 fastPow(3, 13) endl; // 输出 1594323 // 示例2计算 3^13 % 1000 (求最后三位) cout 3^13 mod 1000 fastPow(3, 13, 1000) endl; // 输出 323 // 示例3大数场景计算 2^100 % 1000000007 (常见于算法题) const int MOD 1000000007; cout 2^100 mod MOD fastPow(2, 100, MOD) endl; // 输出 976371285 return 0; }3.1 关键代码行深度解读long long类型选择底数、指数、结果和模数都使用long long。这是因为即使取了模中间计算a * a时a本身可能已经接近模数例如1e9量级相乘就会溢出int范围约2e9。使用long long是安全的底线。在极端情况下模数接近1e18则需要使用快速乘或__int128来防止long long乘法溢出这属于进阶话题。初始取模a % mod和res 1 % mod这是非常关键的一步被称为“预取模”。它保证了在进入循环前a和res的值都严格小于mod。这样在后续的res * a和a * a运算中虽然乘积可能超过mod但绝不会超过(mod-1)*(mod-1)这通常仍在long long的表示范围内对于mod 1e9是安全的从而有效避免了不可控的溢出。这是一个重要的防御性编程技巧。循环条件while (n 0)只要指数n还没被右移到0就继续。每次循环处理n的一个二进制位。位运算n 1和n 1n 1用于检查n的二进制最低位是否为1效率远高于n % 2。n 1等价于n / 2但位运算通常更快。这是快速幂迭代实现的核心操作。取模运算的位置在每一次乘法 (res * a) 和平方 (a * a) 之后立即取模。这是保证计算过程始终在可控范围内的铁律。绝对不能先算完整个幂再取模那样中间值早就溢出了。4. 递归实现、矩阵快速幂与常见变体虽然迭代版本是主流但了解递归版本有助于加深对分治思想的理解。4.1 递归实现long long fastPowRecur(long long a, long long n, long long mod 1) { if (mod 1) return 0; if (n 0) return 1 % mod; a % mod; long long half fastPowRecur(a, n / 2, mod); if (n % 2 0) { // n为偶数: a^n (a^(n/2))^2 return (half * half) % mod; } else { // n为奇数: a^n (a^(n/2))^2 * a return (((half * half) % mod) * a) % mod; } }递归的代码更简洁地反映了数学定义但存在递归栈开销且对于极深的递归虽然log(n)深度通常没问题可能不如迭代稳定。4.2 矩阵快速幂从数到矩阵的飞跃快速幂的思想不仅能用于数字更能用于任何满足结合律的运算比如矩阵乘法。这就是强大的矩阵快速幂。应用场景主要用于求解线性递推式例如斐波那契数列F(n) F(n-1) F(n-2)。我们可以将递推式转化为矩阵形式[ F(n) ] [1 1] ^ (n-1) * [F(1)] [ F(n-1) ] [1 0] [F(0)]计算一个矩阵的n次幂如果直接用朴素矩阵乘法复杂度是O(n * m^3)m为矩阵阶数。而使用矩阵快速幂复杂度降为O(m^3 * log n)。对于n高达1e18的情况这是唯一可行的解法。C 实现核心你需要先实现一个矩阵类及其乘法运算符重载然后将上面快速幂函数中的long long乘法替换为矩阵乘法res1替换为单位矩阵。// 以2x2矩阵为例 const int MOD 1e97; struct Matrix { long long m[2][2]; Matrix() { memset(m, 0, sizeof(m)); } Matrix operator*(const Matrix other) const { Matrix res; for (int i 0; i 2; i) for (int j 0; j 2; j) for (int k 0; k 2; k) res.m[i][j] (res.m[i][j] m[i][k] * other.m[k][j]) % MOD; return res; } }; Matrix matrixFastPow(Matrix a, long long n) { Matrix res; // 将res初始化为单位矩阵 res.m[0][0] res.m[1][1] 1; while (n) { if (n 1) res res * a; a a * a; n 1; } return res; } // 使用 matrixFastPow 可以快速计算斐波那契数列第n项4.3 支持负指数与浮点数的快速幂有时我们需要计算a^(-n)或浮点数的幂。思路是进行转化负指数a^(-n) 1 / (a^n)。在实现时先计算a^n然后求其乘法逆元在模意义下或直接做浮点数除法。浮点数底数算法逻辑完全不变只是数据类型换成double并且不再需要取模运算。但要注意浮点数的精度误差特别是当指数很大时。double fastPowDouble(double a, long long n) { double res 1.0; while (n) { if (n 1) res * a; a * a; n 1; } return res; } // 处理负指数 double myPow(double a, long long n) { if (n 0) return fastPowDouble(a, n); else return 1.0 / fastPowDouble(a, -n); }5. 实战应用场景与性能对比分析快速幂绝不仅仅是书本上的算法它在以下场景中不可或缺密码学RSA等加密算法中大量的大数模幂运算 (a^b mod m) 是核心操作完全依赖快速幂。算法竞赛计算组合数C(n, m) % p需要用到费马小定理求逆元其中就涉及快速幂。求解线性递推数列的第n项如斐波那契使用矩阵快速幂。任何需要计算大指数取模的题目。数学计算需要计算x^y且y很大时例如在物理模拟或金融模型中。性能对比实测 我写了一个简单的测试计算2^1000000000 % 100000000710亿次方。朴素循环理论上需要10亿次乘法和取模在普通电脑上几分钟都无法完成实际因超时无法测试。快速幂迭代时间复杂度O(log n)大约log2(1e9) ≈ 30次循环迭代。实测时间在0.0001秒级别几乎是瞬间完成。这个对比直观地展示了从O(n)到O(log n)的威力。在数据规模面前高效的算法就是魔法。6. 常见问题、调试技巧与避坑指南即使理解了原理实现时也可能遇到各种问题。下面是我在多年刷题和项目中总结的“坑点”。6.1 典型错误与修正错误1忽略取模导致溢出// 错误写法 long long fastPowWrong(long long a, long long n, long long mod) { long long res 1; while (n) { if (n 1) res res * a; // 这里可能溢出 a a * a; // 这里也可能溢出 n 1; } return res % mod; // 最后才取模为时已晚 }修正必须像标准实现那样在每一次乘法后立即取模。错误2指数为0或底数为0时的边界处理0^0在数学上是未定义的但在编程题中常规定义为1。我们的实现 (n0时返回1%mod) 符合这一惯例。计算0^n (n0)我们的实现 (a%mod后进入循环) 会得到正确结果0。如果模数mod1任何数取模1都是0。我们在函数开头做了特判直接返回0避免不必要的计算。错误3使用int类型导致溢出这是最隐蔽的错误。即使最终结果在int范围内中间计算a * a也可能溢出。始终坚持使用long long作为与乘幂相关的变量类型。6.2 调试技巧小数据验证用cout打印循环每一步的resan的值对照手动计算过程。例如计算3^5。对比验证写一个朴素的for循环函数计算小范围的a^n % mod与快速幂的结果对比。单元测试准备多组测试数据包括n0,n1,a0,mod1, 大指数等边界情况。6.3 进阶问题模数下的乘法溢出当模数mod很大比如1e18时即使a moda * a也可能超过long long的范围约9e18导致溢出。解决方法有使用__int128如果编译器支持如GCC可以用__int128存储中间乘积然后再取模。res (__int128(res) * a) % mod; a (__int128(a) * a) % mod;使用快速乘算法模仿快速幂将乘法转化为加法在加法的每一步进行取模确保不溢出。但这会增加一个log的常数。long long quickMul(long long a, long long b, long long mod) { long long res 0; while (b) { if (b 1) res (res a) % mod; a (a a) % mod; b 1; } return res; } // 然后在快速幂中用 quickMul 替换普通的乘法6.4 关于%运算符和负数的处理C 中的%运算符当被除数为负数时结果也为负满足(a/b)*b a%b a。在我们的场景中底数a和结果res始终是非负的因为我们对a取了模所以不会遇到此问题。但如果你的输入a可能为负安全的做法是a (a % mod mod) % mod;这能确保a被调整到[0, mod)的正数范围内。最后记住这个算法的模板。在竞赛中它应该像呼吸一样自然。当你看到“求a^b mod p”或者递推式求第n项时快速幂就是你工具箱里的第一把利器。理解其二进制分解的本质你就能轻松驾驭它甚至将其思想迁移到其他符合结合律的运算上去。
