计算3^13。朴素做法是连乘13次O(n)。如果你注意到13 1101₂ 8 4 1就可以这样算3^13 3^8 × 3^4 × 3^1而3^1 3、3^2 9、3^4 81、3^8 6561——只需不断平方3次乘法就拿到了全部“二进制位对应的幂”。再按13的二进制位挑选相乘总共6次乘法而不是13次。n越大差距越夸张3^1000000000朴素要10亿次乘法快速幂只要30次平方。这就是快速幂。它和倍增减法、快排共享同一个内核不按1递减而按2的幂次砍。 题目速览30秒读懂题目1Pow(x, n)LC.50实现pow(x, n)即计算x的整数n次幂。示例2^10 10242^-2 0.25约束-100 x 100-2^31 ≤ n ≤ 2^31-1。题目2超级次方LC.372延伸计算a^b mod 1337其中b以数组形式给出如[1,0]表示10。示例a2, b[3]→8a2, b[1,0]→1024a2147483647, b[2,0,0]→1198 核心思路把指数写成二进制任何正整数n都可以唯一表示为二进制n Σ bᵢ·2ⁱ。于是x^n x^(Σ bᵢ·2ⁱ) Π (x^(2ⁱ))^(bᵢ)即把n的二进制里所有为1的位对应的x^(2ⁱ)相乘。而x^(2ⁱ)这个序列有个极好的性质——后一项是前一项的平方x^1, x^2, x^4, x^8, x^16, ... 每项 前项²所以只需维护一个“当前底数base”每轮平方一次同时维护结果res当n的当前二进制位为1时把base乘进res。迭代版骨架推荐res 1 while n 0: if n 1: # 当前最低位为1 res * base base * base # 底数平方准备下一位 n 1 # 指数右移处理下一位递归版分治x^n x^(n/2) × x^(n/2) n为偶数 x^n x^(n/2) × x^(n/2) × x n为奇数两者复杂度都是O(logn)迭代版更好写、无栈开销面试首选。为什么是O(logn)循环次数 n的二进制位数 ⌊log₂ n⌋ 1。每轮做1~2次乘法所以总乘法次数 ≤ 2·log₂n。解法乘法次数n 10⁹复杂度朴素连乘10⁹次O(n)快速幂≤ 60次O(logn)负指数与溢出n 0时先算x^(-n)再取倒数x^n 1 / x^(-n)。⚠️Java的经典坑n Integer.MIN_VALUE时-n会溢出——-(-2147483648)仍然是-2147483648。标准做法是先转成long。Python无此问题。LC.372数组指数 模运算b是数组直接转成整数会溢出。关键是这个递推a^[d₀, d₁, ..., dₖ] (a^[d₀, ..., dₖ₋₁])¹⁰ × a^(dₖ)即从高位往低位扫每读一位就把当前结果“整体升10次方”再乘上新位对应的幂。配合模运算性质(a × b) mod m ((a mod m) × (b mod m)) mod m每一步都取模全程不出现大数。⚠️高频翻车点模数1337 7 × 191不是质数。所以费马小定理不适用——不能通过“指数对1336取模”来降幂只能老实做快速幂取模。️ 图解算法手把手走一遍3^13的迭代推演13 1101₂轮次n二进制n 1操作resbase下一轮初始1101(13)—res1, base313111011res × 3392110(6)0不动381311(3)1res × 81243656141(1)1res × 65611594323—结束0——1594323—验算3^13 1594323✓关键点在第2轮n的该位是 0res不动但base照样要平方。因为底数序列必须持续推进无论当前位是否为1。这是最容易写错的一处——把base * base写进了if里面。分解对应关系13 1101₂ │││└─ 第 0 位 1 → 乘 3^1 3 ││└── 第 1 位 0 → 不乘 │└─── 第 2 位 1 → 乘 3^4 81 └──── 第 3 位 1 → 乘 3^8 6561 ──────────────────────────────────── 3 × 81 × 6561 1594323 ✓LC.372 递推演示a2, b[1,0]即2^10 1024步骤读入位递推式结果初始—res 1111(1)¹⁰ × 2¹220(2)¹⁰ × 2⁰1024结果1024 ✓ 代码实现Python JavaPython版classSolution:# ---------- LC.50 Pow(x, n) ----------defmyPow(self,x:float,n:int)-float:ifn0:x1/x n-n# Python 无溢出问题res,base1.0,xwhilen0:ifn1:# 当前位为1把base乘进结果res*base base*base# 底数平方无论当前位是否为1n1returnres# ---------- LC.372 超级次方 ----------defsuperPow(self,a:int,b:list[int])-int:MOD1337# 注意1337 7 × 191不是质数res1fordinb:resself._pow_mod(res,10,MOD)# 整体升10次方resres*self._pow_mod(a%MOD,d,MOD)%MODreturnresdef_pow_mod(self,base:int,exp:int,mod:int)-int:res1base%modwhileexp0:ifexp1:resres*base%mod basebase*base%mod exp1returnresJava版classSolution{// ---------- LC.50 ----------publicdoublemyPow(doublex,intn){longNn;// 转longn Integer.MIN_VALUE时-n会溢出if(N0){x1/x;N-N;}doubleres1.0,basex;while(N0){if((N1)1)res*base;base*base;// 底数平方必须写在if外N1;}returnres;}// ---------- LC.372 ----------publicintsuperPow(inta,int[]b){finalintMOD1337;// 非质数费马小定理不适用intres1;for(intd:b){respowMod(res,10,MOD);res(int)((long)res*powMod(a%MOD,d,MOD)%MOD);}returnres;}privateintpowMod(intbase,intexp,intmod){longres1,bbase%mod;while(exp0){if((exp1)1)resres*b%mod;bb*b%mod;exp1;}return(int)res;}}⚠️防坑提醒必看base * base必须在if之外——最经典的实现错误。Java的Integer.MIN_VALUE溢出-n对它无效必须先转long。LC.372的模数1337不是质数——费马小定理不适用。递归版同一个二进制两种读法defmyPowRecursive(self,x:float,n:int)-float:ifn0:return1/self.myPowRecursive(x,-n)ifn0:return1.0halfself.myPowRecursive(x,n//2)returnhalf*half*(xifn%2else1.0)两者处理位的顺序恰好相反处理顺序平方方向空间迭代版从最低位到最高位底数不断平方自底向上O(1)递归版从最高位到最低位递归返回时平方自顶向下O(log n) 栈面试首选迭代版。延伸矩阵快速幂斐波那契时提过“可以做到 O(logn)”落地方式就是矩阵快速幂[F(n), F(n-1)]ᵀ [[1,1],[1,0]]^(n-1) × [F(1), F(0)]ᵀdeffib(self,n:int)-int:ifn0:return0defmul(A,B):return[[A[0][0]*B[0][0]A[0][1]*B[1][0],A[0][0]*B[0][1]A[0][1]*B[1][1]],[A[1][0]*B[0][0]A[1][1]*B[1][0],A[1][0]*B[0][1]A[1][1]*B[1][1]]]defmpow(A,e):R[[1,0],[0,1]]# 单位矩阵相当于res 1whilee:ife1:Rmul(R,A)Amul(A,A)e1returnRreturnmpow([[1,1],[1,0]],n-1)[0][0]注意mpow与数的快速幂逐行同构——只是把×换成了矩阵乘法、把1换成了单位矩阵。这正是快速幂的普适性所在它只依赖运算满足结合律。矩阵乘法满足结合律但不满足交换律所以快速幂照样成立。⏱️ 复杂度分析面试必问题目解法时间空间LC.50朴素连乘O(n)O(1)LC.50快速幂迭代O(log n)O(1)LC.50快速幂递归O(logn)O(logn) 栈LC.372数组递推 快速幂O(len(b) × log 10)O(1)乘法次数对比n 10⁹解法乘法次数相对朴素连乘10⁹1快速幂≤ 60约1.7×10⁷倍快 举一反三6 道高频变体题题号题目与本题的关系LC.372超级次方数组指数 模运算模数非质数LC.509斐波那契数矩阵快速幂可做到 O(logn)LC.70爬楼梯同LC.509矩阵快速幂加速LC.1137第N个泰波那契数三阶递推的矩阵快速幂LC.29两数相除倍增减法同一“二进制展开”思想LC.50Pow(x, n)本题 面试追问模拟提前准备惊艳全场Q1快速幂的循环次数是多少⌊log₂ n⌋ 1次即n的二进制位数。每轮1~2次乘法所以总乘法次数上界是2·⌊log₂ n⌋ 2。Q2矩阵快速幂怎么用把线性递推写成矩阵形式用快速幂算矩阵的幂。斐波那契[F(n), F(n-1)]ᵀ [[1,1],[1,0]]^(n-1) × [F(1), F(0)]ᵀ。注意矩阵乘法满足结合律但不满足交换律——快速幂只依赖结合律所以仍成立。Q3模运算下怎么做除法乘逆元。若a × x ≡ 1 (mod p)则x是a的逆元。求法有二① 模p为质数时由费马小定理得a^(-1) ≡ a^(p-2)用快速幂直接算② 通用做法用扩展欧几里得。Q4LC.372能不能用费马小定理降指数不能。费马小定理要求模数是质数而1337 7 × 191。这是本题最大的陷阱——看到“大指数取模”就想降幂会直接算错。正确的降幂工具是欧拉定理或通用的扩展欧拉定理。 实战小技巧刷题党必备口诀指数二进制底数每轮平方当前位为 1 就乘进结果。模板while n: if n1: res * base; base * base; n 1。防坑base * base必须在if外Java防Integer.MIN_VALUE溢出LC.372模数非质数。 实际应用场景不止是刷题密码学RSA的核心运算就是模幂没有快速幂RSA不可用组合计数预处理C(n, m)中的阶乘与逆元配合快速幂O(logn)求逆递推加速任何线性递推斐波那契、路径计数都能用矩阵快速幂从O(n)降到O(logn)浮点幂函数pow()库函数内部就是二进制幂的变体 今日思考题快速幂的递归版和迭代版复杂度相同但递归版有O(logn)的栈空间。如果面试官要求“改成迭代”你会怎么改提示递归是自顶向下拆指数迭代是自底向上拼二进制位——两者处理位的顺序恰好相反。