元宝 LeetCode 372. 超级次方 Java实现

LeetCode 372 超级次方（Java 可 AC 版）

核心公式（利用模运算性质）：

“a^b % 1337” 不能直接算 b 太大

• 把 b 当成十进制数组从高位到低位处理：
  “result = (result^10 * a^b[i]) % 1337”
• 或者从低位到高位：
  “ans = ans * a^b[i] % MOD; a = a^10 % MOD;”

标准解法：快速幂 + 从后往前算

class Solution {
private static final int MOD = 1337;

public int superPow(int a, int[] b) { int ans = 1; a %= MOD; for (int i = b.length - 1; i >= 0; i--) { // 当前位作为指数：a^b[i] ans = (int)((long) ans * qpow(a, b[i]) % MOD); // 下一位是十位，所以 a 升为 a^10 a = qpow(a, 10); } return ans; } // 快速幂：a^n % MOD private int qpow(int a, int n) { long res = 1; long base = a % MOD; while (n > 0) { if ((n & 1) == 1) { res = res * base % MOD; } base = base * base % MOD; n >>= 1; } return (int) res; }

}

核心思路

以
“b = [1,2,3]” 为例：

a^123 = a^120 * a^3
= (a¹²⁾10 * a^3
= ((a¹⁾10 * a²⁾10 * a^3

从数组尾部开始：

1. 先算
   “a^b[末位]” 乘进结果
2. 再把底数变成
   “a^10”，相当于进位到十位
3. 重复直到处理完整个数组

易错点

• 中间乘法溢出：
  “ans * qpow(…)” 可能超
  “int”，必须用
  “long” 强转再
  “% MOD”

“a” 可能很大，进来先
“a %= MOD”

• 别用
  “Math.pow”：返回 double 且不算模，精度会炸
• 别试图把数组拼成
  “long/BigInteger” 再算：题目允许长度 2000，超出数值类型范围，必须逐位处理
• 快速幂里
  “base” 也要先取模

复杂度

• 时间：O(n * log 10) ≈ O(n)，n 为 b 长度，每位最多快速幂 log₂(10) 次乘法
• 空间：O(1)

要不要我再给你一版「从前往后算（result = result^10 * a^b[i]）」的等价写法，或者补一下递归分治版对照看？