计算幂运算看似简单，pow(a, n)一行代码就能搞定，但一旦遇到取模、高精度或者指数特别大的场景，浮点版本的pow就会因为精度丢失而出错。手写循环连乘虽然精确，可当指数达到10的18次方量级时，循环次数会让程序直接超时。快速幂算法正是为了解决这个问题而生，它能把O(n)的计算量压缩到O(log n)，是算法竞赛和密码学领域的必备基础技能。
快速幂的核心原理：二进制拆分思想
快速幂的本质，是把指数n按二进制展开，从而将幂运算拆解成若干个“平方”操作的组合。任何一个正整数n都可以写成2的幂之和，例如13的二进制是1101，也就是8加4加1。那么a的13次方就可以写成a的8次方乘以a的4次方乘以a的1次方。
这个拆分带来了一个关键优势：a的2次方、a的4次方、a的8次方这些底数不需要分别从头计算，每一项都是前一项的平方。也就是说，我们只需从a开始不断自乘，就能依次得到a、a平方、a的四次方、a的八次方……这个序列最多只有log n项。对于指数为13的情况，直接连乘需要13次乘法，而拆分后只需要做几次平方加上两三次乘法。
用数学公式表达就是：假设n的二进制表示为b(k) b(k-1) … b(1) b(0)，那么a的n次方等于所有b(i)为1对应的a的2的i次方的乘积。每处理完一位，就把底数平方一次，指数右移一位，直到指数变成0为止。
递归实现与迭代实现对比
递归写法最贴近数学定义，容易理解。当指数为偶数时，a的n次方等于a的n/2次方的平方；当指数为奇数时，再多乘一个a。代码如下：
long long quickPow(long long a, long long n) {
if (n == 0) return 1;
long long half = quickPow(a, n / 2);
if (n % 2 == 0) {
return half * half;
} else {
return half * half * a;
}
}
递归版本逻辑清晰，但存在函数调用开销，且深度为log n的递归在极端情况下虽然不会栈溢出，性能上还是略逊一筹。工程实践中更推荐迭代写法，通过位运算直接扫描指数的每一个二进制位：
long long quickPow(long long a, long long n) {
long long result = 1;
while (n > 0) {
if (n & 1) { // 判断当前最低位是否为1
result = result * a;
}
a = a * a; // 底数不断平方
n >>= 1; // 指数右移一位
}
return result;
}
迭代版本只用了一个while循环，没有递归调用，空间复杂度为O(1)。其中n & 1用来判断n的二进制最低位是不是1，等价于n % 2 == 1；n >>= 1等价于n /= 2，但位运算的执行效率更高。两个小技巧在编译器开启优化时差别不大，不过养成使用位运算的习惯对理解算法本质很有帮助。
处理数据溢出：模运算必不可少
上面两个版本都有严重的隐患：即使指数只有60左右，long long也会溢出，因为2的63次方已经接近long long的极限，再乘几次就直接爆掉了。这就是为什么快速幂几乎总是和取模运算一起出现。实际题目中一般要求输出结果对某个数取模，常见的模数是10的9次方加7。
加上取模只需要修改两处乘法，每次乘完立刻取模，把中间结果控制在模数范围内：
const long long MOD = 1e9 + 7;
long long quickPow(long long a, long long n, long long mod) {
a %= mod; // 先把底数压到模数范围内
long long result = 1;
while (n > 0) {
if (n & 1) {
result = result * a % mod;
}
a = a * a % mod;
n >>= 1;
}
return result;
}
注意一个细节：如果mod接近long long的上限（比如10的18次方量级），两个long long相乘本身就可能溢出。这种情况下需要改用__int128类型做中间运算，或者使用龟速乘（也称快速乘）把乘法拆成加法来避免溢出。日常刷题中模数为10的9次方加7时，long long完全够用，两个不超过模数的数相乘最大约10的18次方，仍在long long的表示范围内。
典型应用场景与性能分析
快速幂最常见的应用是求模意义下的幂，这类问题在密码学、费马小定理求逆元、组合数学计算中大量出现。比如计算组合数C(n, m)对大质数取模时，除法不能直接取模，需要先把分母的阶乘通过费马小定理转换成逆元，而求逆元的过程本质上就是一次快速幂运算：a的逆元等于a的(mod-2)次方。
性能方面，快速幂的时间复杂度是严格的O(log n)。以指数为10的18次方为例，二进制展开也只有约60位，循环最多执行60次，每次做两三次乘法，总耗时纳秒级别。对比朴素算法需要10的18次方次乘法，即使每秒计算10亿次，也要跑三十年，差距一目了然。下表给出了直观对比：
| 指数规模 | 朴素算法乘法次数 | 快速幂乘法次数 |
|---|---|---|
| 1000 | 1000 | 约10次 |
| 10^9 | 10亿次 | 约30次 |
| 10^18 | 无法完成 | 约60次 |
除了基本的幂运算，快速幂思想还可以推广到矩阵快速幂，用于加速线性递推数列的计算，比如斐波那契数列的第n项可以在O(log n)时间内求出，把矩阵当作底数、套用同样的迭代框架即可。掌握快速幂不仅是学会一个模板函数，更是理解“降维拆解问题”这一通用算法思想的重要一步。
最后给出一个使用建议：写快速幂时优先选择迭代加位运算的版本，参数中带上模数，指数声明为long long或者unsigned long long以防边界问题。这个函数只有十来行，值得背下来，它会在你后续学习数论、动态优化和密码学时反复出现。
常见错误与调试要点
初学者实现快速幂时常犯几个错误。第一个是忘记在乘法之后立即取模，导致中间结果溢出后变成负数或者错误值，这种bug往往只在指数较大时才暴露，小规模测试完全发现不了。第二个是循环条件写成n > 0却对负指数做处理，快速幂本身只适用于非负整数指数，负指数需要转换成分数或者用模意义下的逆元来处理。
第三个常见错误是数据类型选择不当。如果底数和指数都声明为int，即使结果在long long范围内，中间的乘法也会先按int计算再截断，正确做法是至少把底数和累乘结果声明为long long，或者在乘法前做一次显式类型转换，例如(long long)a * a % mod。调试时可以先用小数据对比pow函数的浮点结果验证正确性，再放到大数据下测试性能。
此外还要注意模数为1的特殊情况，任何数对1取模结果都是0，某些题目的边界数据会专门卡这一点。把a %= mod放在函数开头，可以顺带处理底数本身大于模数的输入，让代码更加健壮。
如果需要处理超大模数下的乘法溢出，可以配合快速乘一起使用，思路与快速幂完全一致，把乘法拆成二进制加法：
// 龟速乘：计算 (a * b) % mod，避免乘法溢出
long long mulMod(long long a, long long b, long long mod) {
a %= mod;
b %= mod;
long long result = 0;
while (b > 0) {
if (b & 1) {
result = (result + a) % mod;
}
a = (a + a) % mod;
b >>= 1;
}
return result;
}
把快速幂中的乘法替换成这个mulMod，就能在模数接近long long上限时依然安全运行。掌握了这些细节，快速幂就算真正学到家了。