快速幂算法精讲：从二分分治到二进制迭代，攻克大数幂运算

1. 项目概述：从“暴力乘”到“分治幂”的思维跃迁

如果你还在用for循环傻傻地计算pow(x, n)，那这篇文章就是为你准备的。我们这次要啃下的硬骨头，是算法面试和竞赛中一个经典且高频的考点：快速幂算法。标题里提到的50. Pow(x, n)、372. 超级次方和1808. 好因子的最大数目，这三道力扣题目，恰好构成了一个从基础到进阶，再到综合应用的完美学习路径。它们共同的核心，就是如何高效、优雅地计算一个数的超大次方，而秘诀就在于“分而治之”的思想和“二进制”的视角。

简单来说，快速幂解决的是这样一个痛点：当n非常大时（比如n是 2^31 - 1 这样的整数），直接进行n次乘法，时间复杂度是 O(n)，这在算法世界里是不可接受的，会直接超时。快速幂算法能将这个复杂度降到 O(log n)，这是一个质的飞跃。网络上热议的pow(2, 3, 5)这种带模运算的求幂，更是快速幂的典型应用场景，它揭示了内置函数pow()在处理大数取模时的局限性，以及我们手动实现快速幂的必要性。

无论你是正在准备面试的求职者，还是希望提升算法内功的开发者，掌握快速幂及其变种，都能让你在面对指数运算相关问题时，从“暴力求解”的思维定式中跳脱出来，拥有一个清晰且高效的解题工具箱。接下来，我们就从最根本的原理开始，一步步拆解这个强大的算法。

2. 核心原理：二分与分治的威力

要理解快速幂，首先要抛弃“次方就是连乘”的线性思维。我们引入两个核心思想：二分和分治。

2.1 从二分递归理解分治

我们先看一个简单的例子：计算x^10。 最笨的方法是：x * x * x ...乘 9 次。 快速幂的思路是：x^10 = (x^5)^2。看，规模从 10 降到了 5。那么x^5怎么算？x^5 = x * x^4。而x^4 = (x^2)^2。

我们把这个过程写成递归形式：

• 要计算pow(x, n)：
  • 如果n == 0，返回 1。
  • 如果n是偶数，那么pow(x, n) = pow(x, n/2) * pow(x, n/2)。
  • 如果n是奇数，那么pow(x, n) = x * pow(x, n-1)，而n-1就变成了偶数，可以继续用偶数的方法。

这个过程就像一个完美的分治策略：每次都将问题规模（指数n）减半。计算x^n的时间复杂度就从 O(n) 降到了 O(log n)。这就是递归快速幂的核心。

注意：这里有一个关键的优化点。在偶数情况下，我们计算了一次pow(x, n/2)，然后将其结果自乘。在代码实现时，一定要将这个结果保存到一个变量里（比如half = pow(x, n/2)），然后返回half * half。千万不要写成return pow(x, n/2) * pow(x, n/2)，这会导致递归函数被调用两次，完全失去了分治减少计算量的意义，时间复杂度会退化成 O(n)。

2.2 迭代法与二进制的洞察

递归写法直观，但可能有栈溢出的风险（虽然对于 O(log n) 的深度这很少见）。更精妙、更高效的是迭代快速幂，它基于对指数n的二进制表示的深刻理解。

核心思想是：任何整数都可以用二进制表示，那么x^n也可以分解为若干个x^(2^k)的乘积。

让我们以x^13为例，13 的二进制是 1101。

13 = 1*2^3 + 1*2^2 + 0*2^1 + 1*2^0

因此：

x^13 = x^(8+4+0+1) = x^8 * x^4 * x^1

我们发现，乘入最终结果的项，恰好对应二进制位为 1 的位置。

迭代法的流程如下：

1. 初始化结果res = 1。
2. 当指数n > 0时循环：
   • 如果n的当前二进制最低位是 1（即n % 2 == 1或n & 1 == 1），则将当前的x乘入结果res。
   • 将x自乘（x = x * x），这相当于计算x^(2^1),x^(2^2),x^(2^3)...
   • 将n右移一位（n = n // 2或n >>= 1），相当于检查下一个二进制位。
3. 循环结束，返回res。

计算x^13的迭代过程表：

这个过程极其精炼，且天然支持模运算，是竞赛和工程中最常用的模板。

3. 模板解析：递归与迭代的实现

理解了原理，我们来看代码模板。这里会给出 Python 和 Java 两种常见语言的实现，并详细解释每一个细节。

3.1 递归快速幂模板

递归模板更贴近分治的数学定义，易于理解。

Python 模板：

def myPow(x: float, n: int) -> float: # 处理指数为负的情况： x^(-n) = 1 / x^n def quick_pow(x, n): if n == 0: return 1 # 关键：将子问题结果保存，避免重复计算 half = quick_pow(x, n // 2) if n % 2 == 0: # 偶数： half * half return half * half else: # 奇数： x * half * half return x * half * half N = n if N < 0: x = 1 / x N = -N return quick_pow(x, N)

Java 模板：

class Solution { public double myPow(double x, int n) { long N = n; // 防止 n=-2^31 取反时溢出 return N >= 0 ? quickPow(x, N) : 1.0 / quickPow(x, -N); } private double quickPow(double x, long n) { if (n == 0) { return 1.0; } double half = quickPow(x, n / 2); if (n % 2 == 0) { return half * half; } else { return x * half * half; } } }

关键点解析：

1. 负数处理：这是第一个坑。当指数n为负数时，x^n = 1 / x^(-n)。我们需要先将n转为正数处理。特别注意 Java 中int的取值范围，当n = -2147483648 (Integer.MIN_VALUE)时，直接取负数-n会导致溢出，所以必须先转换为long型。
2. 递归终止条件：n == 0时，返回 1，这是数学定义。
3. 分治计算：计算half = quick_pow(x, n // 2)。这是效率的关键，只计算一次子问题。
4. 合并结果：根据n的奇偶性，用half组合出最终结果。

3.2 迭代快速幂模板（推荐）

迭代模板效率更高，且是处理带模运算问题的标准形式。

Python 模板（通用，含取模）：

def quick_pow_iter(base: int, exp: int, mod: int = None) -> int: """ 迭代快速幂 :param base: 底数 :param exp: 指数 :param mod: 模数，如果为None则不取模 :return: base^exp [% mod] """ result = 1 while exp > 0: # 如果当前二进制位为1，则将当前的base乘入结果 if exp & 1: # 等价于 exp % 2 == 1 result *= base if mod is not None: result %= mod # 每一步都取模，防止溢出 # base自增，准备下一位 base *= base if mod is not None: base %= mod # 同样，base自乘后也取模 # 指数右移一位 exp >>= 1 # 等价于 exp //= 2 return result if mod is None else result % mod

Java 模板（通用，含取模）：

class Solution { // 计算 (base^exp) % mod private long quickPow(long base, long exp, long mod) { long res = 1 % mod; // 处理mod=1的情况 base %= mod; // 先取模，防止base过大 while (exp > 0) { if ((exp & 1) == 1) { res = (res * base) % mod; } base = (base * base) % mod; exp >>= 1; } return res; } // 计算浮点数的整数次方（力扣50题） public double myPow(double x, int n) { long N = n; if (N < 0) { x = 1 / x; N = -N; } double res = 1.0; double current_product = x; while (N > 0) { if ((N & 1) == 1) { res *= current_product; } current_product *= current_product; N >>= 1; } return res; } }

模板使用心法：

1. result初始为 1：这是乘法的单位元。
2. 循环条件exp > 0：将指数视为二进制数，直到它被右移为 0。
3. exp & 1判断最低位：这是位运算，比exp % 2更高效，是快速幂的标志性写法。
4. base *= base：这步非常关键，它让base不断变成自己的平方（x -> x^2 -> x^4 -> x^8...），对应二进制位的权重。
5. exp >>= 1：右移一位，相当于除以 2 并向下取整，准备处理下一个二进制位。
6. 取模运算的位置：在带模运算的场景下（如pow(a,b,c)），必须在每一次乘法之后立即取模，即(res * base) % mod和(base * base) % mod。这是为了防止中间结果溢出（即使使用long类型，对于极大的数也可能溢出）。这也是为什么 Python 内置的pow(a,b,c)在b很大时依然高效安全，而先算a**b再取模则会内存溢出的原因。

4. 实战应用：三题精讲

掌握了模板，我们来看它在具体问题中的灵活应用。这三道题目的难度和侧重点依次递进。

4.1 力扣 50. Pow(x, n) - 基础模板题

这是最直接的快速幂应用题。要求实现pow(x, n)，即计算x的n次幂。

解题思路：直接套用上述迭代快速幂模板即可。唯一需要注意的是，本题的x是浮点数，n是整数，可能为负数。

Python 解答：

class Solution: def myPow(self, x: float, n: int) -> float: # 处理指数为负的情况 if n < 0: x = 1 / x n = -n # 迭代快速幂 res = 1.0 while n: if n & 1: # n % 2 == 1 res *= x x *= x n >>= 1 # n //= 2 return res

避坑指南：

• 整数溢出：在 Java/C++ 中，需要特别注意n = -2147483648的情况。直接n = -n会导致溢出，因为2147483648超出了int的正数范围。安全的做法是像之前模板一样，先将n转为long类型再操作。
• 浮点数精度：虽然题目接受一定的精度误差，但我们的算法本身是精确的。浮点数乘法的固有精度限制是语言和硬件层面的问题，算法层面无需过度担心。

4.2 力扣 372. 超级次方 - 模运算与逐位处理

这道题难度提升。要求计算a^b mod 1337，其中a是一个正整数，b是一个非常大的正整数，以数组形式给出，例如b = [1,0,1]表示指数为 101。

解题思路：这道题完美结合了快速幂和数学知识。

1. 数学基础：模运算有重要的性质(a * b) % k = (a % k) * (b % k) % k。因此我们可以在快速幂的每一步都进行取模。
2. 处理数组指数：指数b是一个数组，代表一个十进制大数。我们可以利用以下公式进行分解：

   a^{[b0, b1, ..., bk]} % m = (a^{[b0, b1, ..., b(k-1)]})^{10} * a^{bk} % m

   也就是说，我们可以从数组的最高位（或最低位）开始，逐位处理。假设我们已经知道superPow(a, b[:-1])的结果为prev，那么当前结果就是(prev^10 % m) * (a^{b.last} % m) % m。

Python 解答：

class Solution: def superPow(self, a: int, b: List[int]) -> int: MOD = 1337 # 快速幂模板：计算 (base^exp) % MOD def pow_mod(base, exp): res = 1 base %= MOD # 先取模，防止base过大 while exp: if exp & 1: res = (res * base) % MOD base = (base * base) % MOD exp >>= 1 return res ans = 1 for digit in b: # 核心公式： ans = (ans^10 * a^digit) % MOD ans = (pow_mod(ans, 10) * pow_mod(a, digit)) % MOD return ans

逐位解析：假设a = 2,b = [1, 5, 3](即指数 153)。

• 初始化ans = 1。
• 处理digit=1(百位):ans = (1^10 * 2^1) % 1337 = 2
• 处理digit=5(十位):ans = (2^10 % 1337 * 2^5 % 1337) % 1337。先算2^10=1024,1024%1337=1024。再算2^5=32。(1024*32)%1337=32768%1337=...(计算过程略)。得到新的ans。
• 处理digit=3(个位):ans = (上一轮结果^10 % 1337 * 2^3 % 1337) % 1337。
• 最终ans即为2^153 % 1337的结果。

实操心得：这道题的关键在于理解指数数组的逐位处理公式。它把一个大指数的计算，分解成了多个小指数（0-9）和10次方的计算，而这两者都可以用我们熟悉的快速幂高效完成。这体现了“分治”思想的另一种形式：不是对指数进行二分，而是按十进制位进行分解。

4.3 力扣 1808. 好因子的最大数目 - 数论与快速幂的结合

这是一道 Hard 题目，将快速幂的应用提升到了数论和组合优化的层面。题目描述略复杂，简化其核心：给定一个正整数primeFactors，你需要构造一个正整数n，使得n的质因数个数恰好为primeFactors个，并且n的“好因子”数目最大化。最终返回最大化的“好因子”数目对10^9+7取模的结果。

（“好因子”定义为：n的一个因子，且该因子能被n的每一个质因数整除。可以证明，这等价于这个因子本身是n的一个质因数的幂的乘积。）

解题思路分析：这是一道数学题。经过推导（推导过程涉及数论，此处不展开），结论是：

• 问题转化为：将整数primeFactors拆分成若干个正整数之和，使得这些数的乘积最大。
• 根据整数拆分求最大乘积的经典结论，应尽可能多地拆分出 3。如果余数是 1，则拿出一个 3 和这个 1 组成两个 2（因为3*1 < 2*2）。
• 最终，最大化乘积 =3^a * 2^b，其中a和b由primeFactors除以 3 的商和余数决定。
• 那么，“好因子”的最大数目就是这个最大乘积。由于结果需要对10^9+7取模，且a可能很大，这里就必须使用带模的快速幂来计算3^a % MOD和2^b % MOD。

Python 解答：

class Solution: def maxNiceDivisors(self, primeFactors: int) -> int: MOD = 10**9 + 7 if primeFactors <= 3: return primeFactors # 对于小情况直接返回 # 计算能拆出多少个3 a, b = divmod(primeFactors, 3) # 根据余数调整 if b == 1: # 余1： 拆一个3出来，变成两个2 (3+1 -> 2+2) a -= 1 b = 2 elif b == 2: # 余2： 保留一个2 pass # b == 0 的情况不需要调整 # 使用快速幂计算 (3^a * 2^b) % MOD def pow_mod(base, exp): res = 1 while exp: if exp & 1: res = (res * base) % MOD base = (base * base) % MOD exp >>= 1 return res ans = (pow_mod(3, a) * pow_mod(2, b)) % MOD return ans

为什么是3？—— 核心数学推导简述这源于一个不等式：对于x >= 4，有2*(x-2) >= x。这意味着对于大于等于4的数，把它拆成2和x-2不会让乘积变小。不断应用这个原理，最终会发现最优的拆分因子是 2 和 3。再比较2*2*2=8和3*3=9，显然 3 更优。因此，要尽可能拆出 3。

本题与快速幂的关联：在得出最终答案是3^a * 2^b后，a的数量级可能与primeFactors同阶，题目约束primeFactors最大为10^9，因此直接计算幂绝对会溢出。此时，我们迭代快速幂模板中的取模功能就派上了用场。pow_mod(3, a)能在 O(log a) 的时间内安全地计算出3^a % MOD的结果。

5. 常见问题与深度思考

在实际编码和面试中，关于快速幂，总有几个问题会反复被问到。

5.1 为什么快速幂的时间复杂度是 O(log n)？

这是由“分治”或“二进制分解”的本质决定的。在递归版本中，每次都将问题规模n减半，递归树的高度就是log₂ n。在迭代版本中，循环的次数等于指数n的二进制位数，同样是log₂ n量级。每次循环内部的操作（乘法、取模、位运算）都是 O(1) 的，所以总时间复杂度是 O(log n)。

5.2 如何处理指数为负数或零的情况？

• 指数为 0：根据数学定义，任何非零数的 0 次方等于 1。这也是我们递归的基准条件。
• 指数为负数：x^(-n) = 1 / x^n。通用做法是，如果n < 0，先将x取倒数（x = 1/x），再将指数变为正数（n = -n）进行计算。切记注意整型溢出问题（如 Java 中Integer.MIN_VALUE取负会溢出）。

5.3 快速幂算法中，取模运算应该放在哪里？

这是一个至关重要的细节，尤其在使用 C++、Java 等语言时。必须在每一次乘法运算之后立即取模。

错误示范：

// 错误！可能中间结果溢出 long res = 1; while (exp > 0) { if ((exp & 1) == 1) { res = res * base; // 这里可能溢出！ } base = base * base; // 这里也可能溢出！ exp >>= 1; } return res % mod;

正确做法：

// 正确！步步为营，防止溢出 long res = 1 % mod; // 处理mod=1的边界情况 base %= mod; // 初始base也取模 while (exp > 0) { if ((exp & 1) == 1) { res = (res * base) % mod; // 乘完就取模 } base = (base * base) % mod; // 自乘完也取模 exp >>= 1; } return res;

Python 得益于大整数支持，中间结果溢出风险较低，但为了算法的一致性和处理超大数时的性能，也建议采用步步取模的方式。

5.4 快速幂的应用场景有哪些？

快速幂绝不仅仅是解算法题的工具，它在实际工程和密码学中广泛应用：

1. 密码学：RSA 等非对称加密算法中，需要进行(base^exp) % mod形式的大数模幂运算，快速幂是唯一可行的计算方法。
2. 计算几何：在需要计算旋转矩阵的多次幂时（例如动画插值）。
3. 动态规划优化：有些 DP 状态转移方程可以写成矩阵形式，求第 n 步的状态就是求转移矩阵的 n 次幂，可以用矩阵快速幂在 O(log n) 时间内解决，经典问题如“斐波那契数列第 n 项”。
4. 随机算法：例如在 Miller-Rabin 素数测试中。

5.5 矩阵快速幂是什么？

这是快速幂思想的自然延伸。当“底数”不是一个数字，而是一个矩阵时，我们同样可以应用快速幂算法来高效计算矩阵的 n 次幂。只需要将模板中的乘法*替换为矩阵乘法，将初始值1替换为单位矩阵即可。矩阵快速幂是解决线性递推问题（如斐波那契数列）的利器，能将 O(n) 的复杂度降至 O(log n)。

掌握了基础的快速幂后，去学习矩阵快速幂，你会对“分治”思想有更深刻的理解。从数的幂到矩阵的幂，算法框架几乎不变，变化的只是乘法的定义，这种抽象和泛化的能力，正是算法学习的精髓所在。