元宝 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 (a12)10 * a^3 ((a1)10 * a2)10 * a^3从数组尾部开始先算“a^b[末位]” 乘进结果再把底数变成“a^10”相当于进位到十位重复直到处理完整个数组易错点中间乘法溢出“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]」的等价写法或者补一下递归分治版对照看