C语言数组去重：从超时到AC的完整通关攻略
2026/10/21 5:54:31
计算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秒读懂）
题目1：Pow(x, n)（LC.50）
实现
pow(x, n)，即计算x的整数n次幂。示例：
2^10 = 1024；2^-2 = 0.25
约束：-100 < x < 100，-2^31 ≤ n ≤ 2^31-1。
题目2：超级次方（LC.372，延伸）
计算
a^b mod 1337，其中b以数组形式给出（如[1,0]表示10）。示例：
a=2, b=[3]→8；a=2, b=[1,0]→1024；a=2147483647, 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 | 操作 | res | base（下一轮） |
|---|---|---|---|---|---|
| 初始 | 1101(13) | — | res=1, base=3 | 1 | 3 |
| 1 | 1101 | 1 | res ×= 3 | 3 | 9 |
| 2 | 110(6) | 0 | 不动 | 3 | 81 |
| 3 | 11(3) | 1 | res ×= 81 | 243 | 6561 |
| 4 | 1(1) | 1 | res ×= 6561 | 1594323 | — |
| 结束 | 0 | — | — | 1594323 | — |
验算：3^13 = 1594323✓
关键点在第2轮：n的该位是 0，res不动，但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 递推演示（a=2, b=[1,0]，即2^10 = 1024）
| 步骤 | 读入位 | 递推式 | 结果 |
|---|---|---|---|
| 初始 | — | res = 1 | 1 |
| 1 | 1 | (1)¹⁰ × 2¹ | 2 |
| 2 | 0 | (2)¹⁰ × 2⁰ | 1024 |
结果1024 ✓
💻 代码实现（Python + Java）
Python版
classSolution:# ---------- LC.50 Pow(x, n) ----------defmyPow(self,x:float,n:int)->float:ifn<0:x=1/x n=-n# Python 无溢出问题res,base=1.0,xwhilen>0:ifn&1:# 当前位为1，把base乘进结果res*=base base*=base# 底数平方（无论当前位是否为1）n>>=1returnres# ---------- LC.372 超级次方 ----------defsuperPow(self,a:int,b:list[int])->int:MOD=1337# 注意1337 = 7 × 191，不是质数！res=1fordinb:res=self._pow_mod(res,10,MOD)# 整体升10次方res=res*self._pow_mod(a%MOD,d,MOD)%MODreturnresdef_pow_mod(self,base:int,exp:int,mod:int)->int:res=1base%=modwhileexp>0:ifexp&1:res=res*base%mod base=base*base%mod exp>>=1returnresJava版
classSolution{// ---------- LC.50 ----------publicdoublemyPow(doublex,intn){longN=n;// 转long：n = Integer.MIN_VALUE时-n会溢出if(N<0){x=1/x;N=-N;}doubleres=1.0,base=x;while(N>0){if((N&1)==1)res*=base;base*=base;// 底数平方，必须写在if外N>>=1;}returnres;}// ---------- LC.372 ----------publicintsuperPow(inta,int[]b){finalintMOD=1337;// 非质数，费马小定理不适用intres=1;for(intd:b){res=powMod(res,10,MOD);res=(int)((long)res*powMod(a%MOD,d,MOD)%MOD);}returnres;}privateintpowMod(intbase,intexp,intmod){longres=1,b=base%mod;while(exp>0){if((exp&1)==1)res=res*b%mod;b=b*b%mod;exp>>=1;}return(int)res;}}⚠️防坑提醒（必看）：
base *= base必须在if之外——最经典的实现错误。- Java的
Integer.MIN_VALUE溢出：-n对它无效，必须先转long。- LC.372的模数1337不是质数——费马小定理不适用。
递归版：同一个二进制，两种读法
defmyPowRecursive(self,x:float,n:int)->float:ifn<0:return1/self.myPowRecursive(x,-n)ifn==0:return1.0half=self.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:ifn==0: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 = 1"whilee:ife&1:R=mul(R,A)A=mul(A,A)e>>=1returnRreturnmpow([[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.50 | Pow(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)，用快速幂直接算；
② 通用做法用扩展欧几里得。
Q4：LC.372能不能用费马小定理降指数？
不能。
费马小定理要求模数是质数，而1337 = 7 × 191。这是本题最大的陷阱——看到“大指数取模”就想降幂，会直接算错。
正确的降幂工具是欧拉定理或通用的扩展欧拉定理。
🧩 实战小技巧（刷题党必备）
- 口诀：指数二进制，底数每轮平方；当前位为 1 就乘进结果。
- 模板：
while n: if n&1: 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)的栈空间。
如果面试官要求“改成迭代”，你会怎么改？
提示：递归是自顶向下拆指数，迭代是自底向上拼二进制位——两者处理位的顺序恰好相反。