快速幂原理：二进制分解
基于通用数论套路 · 核于 2026-07
速查
- 核心思想：把指数 n 按二进制分解为
n = b₀ + b₁·2 + b₂·2² + ... + bₖ·2^k（bᵢ ∈ {0,1}），则a^n = ∏(bᵢ=1) a^(2^i)；而a^(2^i)可由a^(2^(i-1))自平方得到。 - 两类积木：①底数积木
base = a, a², a⁴, a⁸, ...（每轮base *= base）；②结果累乘（仅当当前二进制位为 1 时res *= base）。 - 递归写法：
pow(a,n)：若n=0返回 1；否则half = pow(a, n/2)，sq = half²，n偶返回sq，n奇返回sq × a。 - 迭代写法：
while(n>0) { if(n&1) res*=base; base*=base; n>>=1; }——位运算扫二进制位，最常用。 - 复杂度：乘法次数 = n 的二进制位数 = ⌈log₂(n+1)⌉ ≈ O(log n)；空间迭代 O(1)、递归 O(log n)（栈）。
- 取模版：每步乘法后
%p，由(a×b) mod p = ((a mod p)×(b mod p)) mod p保证正确——把中间值压在[0,p)。 - 边界：
n=0时a^0 = 1（含0^0，按组合数学约定取 1）；n=1时返回a；a=0, n>0时返回 0。 - 为什么快：朴素 O(n) 的「连乘 n 次」改成「逐位累乘 + 自平方」，乘法次数从线性降到对数——算
2^10^9只需约 30 次而非 10 亿次。 - 易错：迭代版先判
n&1再base*=base（顺序反了会多乘一次）；n是 JS Number 时右移用n = Math.floor(n/2)（>>对 >2³² 的数会错）。 - 应用入口：取模版是费马小定理求逆元、组合数取模的基础；思想可推广到矩阵快速幂。
一、从朴素到快速幂：为什么要二进制分解
朴素幂 a^n 是连乘 n 次，O(n) 乘法。n 大了就跑不动。关键洞察是指数可以二进制分解，从而把「乘 n 次」变成「乘 log₂n 次」。
把指数 n 写成二进制：
n = b₀·2⁰ + b₁·2¹ + b₂·2² + ... + bₖ·2ᵏ （每个 bᵢ ∈ {0, 1}）由指数法则 a^(x+y) = a^x · a^y，有：
a^n = a^(b₀·1 + b₁·2 + b₂·4 + ...) = ∏(bᵢ=1) a^(2ⁱ)也就是说，n 的每个为 1 的二进制位 bᵢ 对应一项 a^(2ⁱ)，把这些项乘起来就是 a^n。而 a^(2ⁱ) 这一系列值（a^1, a^2, a^4, a^8, ...）每一项都是前一项的平方，可以边算边生成——这就是快速幂的全部精髓。
例子：a^13，13 = 8 + 4 + 1 = 1101₂
13 的二进制：1 1 0 1 （从高位到低位：8,4,2,1）
为 1 的位：第 0 位（1）、第 2 位（4）、第 3 位（8）
所以：a^13 = a^1 × a^4 × a^8积木链（每项自平方）：a → a² → a⁴ → a⁸，取第 0、2、3 项累乘。
二、递归写法：分治视角
从分治角度，按指数奇偶分类：
a^n = (a^(n/2))² 当 n 为偶数
a^n = (a^((n-1)/2))² × a 当 n 为奇数
a^0 = 1 边界每次把指数砍半，递归 O(log n) 层，每层 O(1) 次乘法。
// 递归快速幂（取模版）
function powMod(a, n, p) {
if (n === 0) return 1 % p; // a^0 = 1（p=1 时 1%1=0）
const half = powMod(a, Math.floor(n / 2), p);
let sq = (half * half) % p; // 平方后取模
return n % 2 === 0 ? sq : (sq * (a % p)) % p; // 奇数多乘 a（也取模）
}递归版贴近数学定义、易于证明正确性，适合教学。缺点是函数调用有开销，且对超大指数（如 n=10^18）递归栈约 60 层（尚可，但工程上迭代更稳）。
三、迭代写法：位运算（最常用）
迭代版直接扫描 n 的二进制位，用 n & 1 取最低位、n >>= 1（或 n = Math.floor(n/2)）右移：
// 迭代快速幂（取模版）
function powMod(a, n, p) {
let res = 1, base = a % p; // base 先取模
while (n > 0) {
if (n & 1) res = (res * base) % p; // 位为 1：累乘 + 取模
base = (base * base) % p; // 底数自平方 + 取模
n = Math.floor(n / 2); // 指数右移（安全版）
}
return res;
}关键顺序：先判位、再自平方
注意循环里先 if (n & 1) 累乘，再 base *= base 自平方。如果反过来，会多乘一次 base（因为自平方后的 base 还没轮到它的二进制位）。
- 正确：本轮累乘的是「当前位对应的
a^(2ⁱ)」，然后base升级为「下一位的a^(2^(i+1))」。 - 错误：先自平方会让本轮累乘到「下一位的积木」，结果整体错位。
走一遍：powMod(2, 13, 1000)（算 2^13 mod 1000 = 8192 mod 1000 = 192）
初始 res=1, base=2%1000=2, n=13
轮1: n&1=1 → res=(1×2)%1000=2; base=(2×2)%1000=4; n=6
轮2: n&1=0 → res=2; base=(4×4)%1000=16; n=3
轮3: n&1=1 → res=(2×16)%1000=32; base=(16×16)%1000=256;n=1
轮4: n&1=1 → res=(32×256)%1000=192;base=(256×256)%1000; n=0 退出
返回 192 ✅ （2^13 = 8192，8192 mod 1000 = 192）4 轮循环 = ⌈log₂(13)⌉ = 4，O(log n)。
四、复杂度分析：为什么是 O(log n)
每轮循环 n 右移一位（n /= 2），所以循环次数 = n 的二进制位数 = ⌈log₂(n+1)⌉。每轮内部是常数次乘法和取模（O(1)），故：
- 时间：O(log n) 次乘法。
- 空间：迭代版 O(1)；递归版 O(log n)（递归栈深度）。
对比朴素 O(n)：算 2^10^9，朴素要约 10⁹ 次乘法（超时），快速幂只要约 30 次（log₂(10⁹) ≈ 29.9）——加速 8 个数量级。这正是快速幂的价值所在。
五、取模版：正确性来自模运算可分配性
取模版快速幂每步乘法后 %p，为什么结果还是 a^n mod p？因为模运算对乘法可分配：
(a × b) mod p = ((a mod p) × (b mod p)) mod p归纳地看：快速幂每次累乘都是「当前结果 × 某个 a^(2ⁱ)」，对这两个因子分别取模再相乘再取模，等于不取模相乘最后取模。所以任何中间步骤取模都不改变最终 a^n mod p，只是把中间值始终压在 [0, p) 内——既保证正确，又防止大数溢出。
边界细节
n = 0：a^0 = 1，返回1 % p（当p = 1时应为 0）。a ≥ p：循环外先base = a % p，把底数压进[0, p)。p = 1：任何数 mod 1 都是 0，直接返回 0（或靠1 % p = 0自然处理）。
六、BigInt 版：应对超大 p
当 p 较大（如 p = 10^9+7）时，base × base 可达 (10^9)² = 10^18，超过 JS Number 安全整数 2^53 ≈ 9×10^15，会丢精度。此时用 BigInt：
// BigInt 取模版快速幂
function powModBig(a, n, p) {
a = BigInt(a); n = BigInt(n); p = BigInt(p);
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 慢——仅在 p × p 超 2^53 时才必须用。详见模运算性质与应用。
七、负指数与负底数（扩展）
标准快速幂处理 n ≥ 0。若要支持负指数 a^(-n) = 1/a^n，需引入浮点或有理数，超出整数模运算范畴（模意义下负指数等价于「乘法逆元的正指数幂」，见费马小定理）。负底数 a < 0 对整数幂无影响（(-a)² = a²），但在取模时要注意：JS % 对负数可能返回负值，统一用 ((x % p) + p) % p 修正到 [0, p)。
交互演示
- 快速幂可视化演示 —— 二进制分解逐位累乘的完整过程
下一步
掌握了快速幂的递归/迭代/取模三版代码后，下一步是模运算的完整性质表与两大应用：费马小定理求逆元、矩阵快速幂，见模运算性质与应用。