入门：二进制幂、模运算性质与防溢出

基于通用数论概念 · 核于 2026-07

速查

• 定义：快速幂是在 O(log n) 时间内计算 a^n 的算法——把指数 n 按二进制分解，逐位累乘，把朴素 O(n) 的「连乘 n 次」优化到约 log₂n 次乘法。
• 朴素法的痛点：a^n 连乘 n 次，n 很大时（如 2^10^9）要算 10 亿次乘法，直接超时——必须降复杂度。
• 二进制分解思想：把指数写成二进制，如 13 = 8+4+1 = 1101₂，则 a^13 = a^8 × a^4 × a^1——每位二进制为 1 时累乘对应的 a^(2^k)，而 a^(2^k) 可由前一项自平方得到。
• 复杂度：快速幂 O(log n) 次乘法（n 的二进制位数）；空间 O(1)（迭代）或 O(log n)（递归栈）。
• 两种写法：①递归——f(n) = f(n/2)² × (n 奇 ? a : 1)；②迭代——底数自平方、指数右移、二进制位为 1 时累乘结果。
• 模运算可分配性（加/减/乘）：(a ± b) mod p = ((a mod p) ± (b mod p)) mod p；(a × b) mod p = ((a mod p) × (b mod p)) mod p——减法取模后可能为负，要 +p 再 %p 修正。
• 除法不分配：(a / b) mod p ≠ (a mod p) / (b mod p)——除法在模意义下要用乘法逆元转乘法。
• 边算边取模：计算 a^n mod p 时每一步乘法后立即 %p，中间值始终在 [0, p) 内，避免大数溢出——这是「取模版快速幂」的核心。
• 为什么边算边取模是对的：由模运算乘法可分配性，每步取模不改变最终 (a^n mod p) 的结果，只是把中间值压小。
• 大数取模的精度问题：JS 的 Number 是 64 位浮点，安全整数上限 2^53 - 1；p × p 超 2^53 就丢精度，必须用 BigInt（任意精度整数）+ n 后缀字面量。
• 应用：①费马小定理求逆元——a^(p-1) ≡ 1 (mod p)（p 质数），逆元 a^(-1) ≡ a^(p-2) (mod p)；②矩阵快速幂——把斐波那契 F(n)=F(n-1)+F(n-2) 的 O(n) 递推降到 O(log n)；③组合数取模 C(n,k) mod p。
• 易错点：减法取模忘 +p 得负数；JS Number 超精度未用 BigInt；取模版快速幂每步漏 %p 导致中间值溢出。
• 进阶顺序：快速幂原理 → 模运算性质与应用 → 参考。

一、为什么需要快速幂

朴素计算 a^n 的做法是连乘 n 次：

// 朴素幂：O(n) 乘法
function powNaive(a, n) {
  let r = 1;
  for (let i = 0; i < n; i++) r *= a;
  return r;
}

问题在于复杂度线性于指数 n。当 n 很大时，这个算法根本跑不动：

• 算 2^10^9 要做约 10 亿次乘法——单线程 CPU 每秒约 10^8~10^9 次基本运算，直接超时（竞赛时限通常 1s）。
• 密码学（RSA）里指数是 2048 位二进制数（约 10^617），朴素法从宇宙诞生算到现在都算不完。

我们需要一个乘法次数随指数「位数」而非「大小」增长的算法——这就是快速幂，把 O(n) 降到 O(log n)：算 2^10^9 只需约 30 次乘法（log₂(10^9) ≈ 30）。

二、二进制分解：快速幂的核心思想

关键观察：任何正整数都能写成二进制。比如 13 = 8 + 4 + 1 = 1101₂，于是：

a^13 = a^(8+4+1) = a^8 × a^4 × a^1

注意 a^1、a^2、a^4、a^8 之间存在自平方关系：a^2 = (a^1)²、a^4 = (a^2)²、a^8 = (a^4)²。所以只要从 a 开始不断自平方，就能依次得到 a^1、a^2、a^4、a^8、a^16……——这些是「现成的积木」。

指数 13 的二进制：1 1 0 1
对应权重：        a^8 a^4 · a^1
累乘结果：        a^8 × a^4 × a^1 = a^13
（中间位是 0 的 a^2 不累乘）

算法就是：逐位扫描 n 的二进制，底数每轮自平方（生成下一块积木），当当前二进制位是 1 时，把当前底数累乘进结果。这样乘法次数 = 二进制位数 = ⌈log₂n⌉，外加少量累乘——总共 O(log n)。

三、递归写法：分治思想

从分治角度，快速幂也有递归形式。把 a^n 按指数奇偶分情况：

• a^n = (a^(n/2))²（n 偶）——只需算一半的幂，再平方。
• a^n = (a^((n-1)/2))² × a（n 奇）——算一半再平方，多乘一个 a。

每次递归把问题规模砍半，递归深度 O(log n)，每层 O(1) 次乘法。

// 递归快速幂：a^n
function pow(a, n) {
  if (n === 0) return 1;           // a^0 = 1（边界）
  const half = pow(a, Math.floor(n / 2)); // 算一半
  const sq = half * half;          // 平方
  return n % 2 === 0 ? sq : sq * a; // 奇数多乘一个 a
}

递归版思路清晰、贴近数学定义，适合讲解；但指数极大（如 n = 10^18）时递归栈有约 60 层（可接受），工程上常用迭代版避免函数调用开销。详见快速幂原理。

四、迭代写法：位运算

迭代版直接扫描 n 的二进制位，用位运算实现：

// 迭代快速幂：a^n
function pow(a, n) {
  let res = 1, base = a;
  while (n > 0) {
    if (n & 1) res *= base;   // 当前二进制位为 1：累乘底数
    base *= base;             // 底数自平方（生成下一块积木）
    n = Math.floor(n / 2);    // 指数右移一位（等价 n >>>= 1）
  }
  return res;
}

走一遍 a^13（13 = 1101₂）：初始 res=1, base=a。

位 1（个位）：n&1=1 → res=a;        base=a²;  n=6
位 0（2 位）：n&1=0 → res=a;        base=a⁴;  n=3
位 1（4 位）：n&1=1 → res=a·a⁴=a⁵;  base=a⁸;  n=1
位 1（8 位）：n&1=1 → res=a⁵·a⁸=a¹³; base=a¹⁶; n=0
退出，返回 a^13 ✅

总共 4 次循环（= 13 的二进制位数），每次循环内常数次乘法——O(log n)。

五、模运算：为什么必须边算边取模

朴素快速幂算 a^n 时中间值会爆炸式增长：2^64 ≈ 1.8×10^19，2^1000 已经远超宇宙原子数。实际题目几乎总是问 a^n mod p（p 是给定质数，如 10^9+7），此时必须每步乘法后立即取模：

// 取模版快速幂：a^n mod p
function powMod(a, n, p) {
  let res = 1, base = a % p;      // base 先取模
  while (n > 0) {
    if (n & 1) res = (res * base) % p;  // 每次累乘后 %p
    base = (base * base) % p;           // 自平方后 %p
    n = Math.floor(n / 2);
  }
  return res;
}

为什么每步取模不改变结果？ 因为模运算对乘法可分配：

(a × b) mod p = ((a mod p) × (b mod p)) mod p

所以 a^n mod p 可以在任何中间步骤取模，最终结果不变——只是把中间值始终压在 [0, p) 内，避免溢出。这就是「取模版快速幂」正确性的根基。

六、模运算的六大性质

模运算（mod p，p 为正整数）满足：

运算	性质	修正
加	(a+b) mod p = ((a mod p)+(b mod p)) mod p	—
减	(a-b) mod p = ((a mod p)-(b mod p)) mod p	结果为负要 +p 再 %p
乘	(a×b) mod p = ((a mod p)×(b mod p)) mod p	—
幂	a^n mod p = (a mod p)^n mod p	快速幂取模版的依据
除	❌ 不分配	需乘法逆元
恒等	a mod p 结果在 [0, p)	负数取模语言相关，JS % 可能得负

记住一句话：「加、减、乘都能边算边取模；除法不行，要转逆元；减法取模后可能为负要 +p 修正。」

七、大数取模：JS 的精度陷阱

JS 的 Number 是 IEEE 754 双精度浮点，安全整数上限是 2^53 - 1（约 9×10^15）。计算 a^n mod p 时，中间乘法 (base × base) 可能超这个上限：

p = 10^9 + 7
base × base 最大 ≈ (10^9)² = 10^18 > 2^53 ≈ 9×10^15  ❌ 丢精度

此时 res * base 和 base * base 都会悄悄丢精度，结果是错的且不报错。解决办法是用 BigInt（任意精度整数，字面量带 n 后缀）：

// 取模版快速幂（BigInt 版）：a^n mod p，避免精度丢失
function powMod(a, n, p) {
  a = BigInt(a); n = BigInt(n); p = BigInt(p); // 转成 BigInt
  let res = 1n, base = a % p;
  while (n > 0n) {
    if (n & 1n) res = (res * base) % p;
    base = (base * base) % p;
    n >>= 1n;                       // BigInt 可用位运算右移
  }
  return res;                        // 返回 BigInt
}

注意 BigInt 不能与 Number 混算（1n + 1 报错），且除法是整除（无小数）。详见模运算性质与应用。

下一步

理解了二进制分解思想与取模防溢出后，下一步是快速幂的完整代码模板（递归/迭代/取模三版）与 O(log n) 复杂度的严格分析，见快速幂原理：二进制分解。