模幂运算为什么用分治快速幂？如何避免中间结果溢出？

简化版

模幂 a^b mod m 可以用快速幂，把指数每次减半。

如果 b 是偶数，a^b = (a^(b/2))^2；如果 b 是奇数，额外乘一个 a。

每次乘法后都取模，能控制数值大小，避免中间结果过大。

详细版

快速幂本质是分治：把指数 b 的问题拆成指数 b/2 的问题。

迭代写法更常见：

当 b 的当前二进制位为 1，把当前 base 乘进答案
每轮 base = base * base mod m
b 右移一位

复杂度从普通连乘的 O(b) 降到 O(log b)。

在 JavaScript 中，如果数值很大，需要用 BigInt 或专门的乘法取模技巧，否则 Number 精度可能不够。

完整版教学

一、为什么普通连乘太慢

计算 a^b mod m 如果直接乘 b 次，指数很大时不可接受。例如 b = 1,000,000,000，逐次乘法要 10 亿轮。快速幂利用指数的二进制结构，把乘法次数降到 log b 级别，大约只需要 30 轮。

记忆钩子：快速幂不是少乘一点，而是把指数按二进制折半处理。

二、分治公式怎么来

当 b 是偶数：

a^b = a^(b/2) * a^(b/2)

当 b 是奇数：

a^b = a * a^(b-1)

所以递归可以先求一半，再平方；迭代可以按二进制位累积答案。这就是分治在指数问题上的体现。

三、为什么每步都能取模

模运算满足乘法兼容性：

(x * y) mod m = ((x mod m) * (y mod m)) mod m

因此每次乘完立即取模不会改变最终答案，却能让中间值保持在较小范围。这个性质是模幂能够高效计算的数学基础。

操作	是否影响最终模值	好处
最后统一取模	不影响数学结果	中间数可能巨大
每步乘后取模	不影响数学结果	控制数值大小

实际编程通常选择每步取模。

四、迭代代码模板

普通整数范围内可以这样写：

function modPow(a, b, mod) {
  let ans = 1 % mod
  let base = a % mod
  while (b > 0) {
    if (b % 2 === 1) ans = (ans * base) % mod
    base = (base * base) % mod
    b = Math.floor(b / 2)
  }
  return ans
}

如果输入可能超过安全整数范围，JavaScript 需要使用 BigInt：

ans = (ans * base) % mod

其中 ans/base/mod 都应是 BigInt 类型。

五、带数字推演

计算 3^13 mod 7。13 的二进制是 1101。

ans=1, base=3, b=13 -> 位为1，ans=3
base=2, b=6
base=4, b=3 -> 位为1，ans=5
base=2, b=1 -> 位为1，ans=3

最终答案是 3。只用了少量平方和乘法。

六、常见误区与追问

误区：先算 a^b 再取模。 中间结果可能极大，甚至溢出或失去精度。
误区：奇数指数处理后忘记继续平方 base。 迭代每轮都要推进 base 和指数。
误区：JavaScript Number 随便乘大整数。 超过安全整数会有精度问题，应考虑 BigInt。
追问：复杂度为什么是 O(log b)？ 指数每轮除以 2，相当于处理二进制位数。
追问：mod 为 1 怎么办？ 所有数对 1 取模都是 0，初始化 1 % mod 能覆盖。

这些问题考的是数学性质和实现细节。

七、加强记忆

模幂记成“指数折半，乘完取模”。偶数指数平方半幂，奇数指数多乘一个底数；迭代时看二进制位，位为 1 就把当前 base 乘进答案。每一步都取模，既保证数学等价，又避免中间结果膨胀。大整数场景要额外注意语言精度。

简化版

详细版