LeetCode 372. 超级次方

约 5 分钟
文章信息 6 个分类 4 个标签
分类
LeetCode CodeTop 中等 未解决 1-2 百度
标签
数学 分治 欧拉函数 欧拉定理
目录

题目描述

✅ 372. 超级次方

题意分析

题目目标：给定正整数 a 和一个数组 b，b 按十进制逐位存放一个可能极大的指数，要求计算 a 的这个指数次方对 1337 取余的结果。
核心约束：指数不是一个整数而是一个数组，这是最重要的信号——它意味着指数大到任何整型都装不下，绝不可能先把 b 还原成一个数再算，只能顺着十进制这个结构逐位处理。第二个信号是模数 1337 很小且固定，说明中间结果始终能压在一个不大的范围内，用 64 位整数做乘法不会溢出。第三个信号是 b 的长度上界很小（不超过 2000 位），意味着与位数成正比的递归或迭代都能轻松通过。
边界处理：b 可能为空数组，此时指数为 0，任何底数的 0 次方在模 1337 意义下都是 1；a 可能大于等于 1337，必须先取余再参与运算；b 中的某一位可能是 0，快速幂要能正确处理 0 次方并返回 1；乘法过程中两个小于 1337 的数相乘最大约 1.8×10^6，虽然不会超 int，但一旦有人漏写取模就会连锁放大，用 long 承接乘积是更稳妥的写法。

解法：递归拆指数（模 1337）

核心思路

不能把指数数组还原为整数。设前 len-1 位表示的指数为 prefix，最后一位为 digit，则前 len 位表示 10*prefix+digit，并有：

\[a^{10\cdot prefix+digit}=(a^{prefix})^{10}\cdot a^{digit}\]

定义 dfs(len) 为 a 的“指数前 len 位”次方对 1337 的余数。递归先求 dfs(len-1)，再用快速幂求其 10 次方，并乘上 a 的当前数字次方。

不变量：dfs(len) 始终等于由前 len 个十进制数字构成的指数对应的模幂结果；所有乘法后立即取模，中间值始终与真实幂同余。

正确性：len=0 时指数为 0，返回 1。假设前缀结果正确，上述指数恒等式和模乘法性质保证合并后的结果正是前 len 位指数的答案，因此归纳到完整数组成立。

解题步骤

  1. 先将底数归约为 a % 1337。
  2. 用二进制快速幂实现 powMod(base,exp)，每次乘法后立即取模。
  3. dfs(0)=1；其余状态取当前末位，按恒等式合并前缀结果。
  4. 只传递前缀长度，不复制指数数组。

a=2,b=[1,3] 时，前一位得到 2^1；再计算 (2^1)^10 * 2^3，对 1337 取模得到 170。

数字位为 0 时仍要把前缀结果提升到 10 次方；例如 [1,0] 表示指数 10，而不是指数 1。空指数数组表示 0 次方，返回 1。

代码实现

class Solution {
    private static final int MOD = 1337;

    public int superPow(int a, int[] b) {
        return dfs(a % MOD, b, b.length);
    }

    private int dfs(int a, int[] b, int len) {
        if (len == 0) {
            return 1;
        }
        int last = b[len - 1];
        int part1 = powMod(dfs(a, b, len - 1), 10);
        int part2 = powMod(a, last);
        return (int) ((long) part1 * part2 % MOD);
    }

    private int powMod(int a, int exp) {
        long res = 1;
        long base = a;
        int e = exp;
        while (e > 0) {
            if ((e & 1) == 1) {
                res = res * base % MOD;
            }
            base = base * base % MOD;
            e >>= 1;
        }
        return (int) res;
    }
}

func superPow(a int, b []int) int {
	const mod = 1337

	powMod := func(x int, exp int) int {
		res := 1
		base := x % mod
		e := exp
		for e > 0 {
			if e&1 == 1 {
				res = res * base % mod
			}
			base = base * base % mod
			e >>= 1
		}
		return res
	}

	var dfs func(len int) int
	aa := a % mod
	dfs = func(len int) int {
		if len == 0 {
			return 1
		}
		last := b[len-1]
		part1 := powMod(dfs(len-1), 10)
		part2 := powMod(aa, last)
		return part1 * part2 % mod
	}

	return dfs(len(b))
}

复杂度分析

  • 时间复杂度：$O(n)$，每个指数数字只触发常数规模的模幂运算。
  • 空间复杂度：$O(n)$，来自递归栈；不复制指数数组。

关键点总结

  • 大指数按十进制位处理，不需要也不能还原为原生整数。
  • 每加入一位，旧指数乘 10，再加当前数字，对应“前缀结果的 10 次方乘当前小幂”。
  • 快速幂和外层乘法都应及时取模，保持递归返回值定义。
  • 空前缀是指数 0，模幂基例为 1。
  • 1337 是合数且底数未必与它互质，逐位恒等式不依赖欧拉降幂条件。

易错点总结

  • 先把指数拼成 long：指数位数很大时必然溢出。
  • 忽略前缀的 10 次方：[1,0] 会被当成指数 1，而不是 10。
  • 把“乘当前小幂”也包含进 10 次方：[1,3] 会把指数 13 错算成 40。
  • 快速幂只在最后取模：中间乘法会迅速溢出。
  • 缺少 len=0 基例：空指数数组会越界，而正确结果是 1。
  • 每层复制指数前缀：把线性处理退化为 $O(n^2)$。

相似题目

题目 难度 考察点
50. Pow(x, n) 中等 快速幂的原型，指数是普通整数但可能为负，重点在负指数取倒数与 MIN_VALUE 溢出
剑指 Offer 16. 数值的整数次方 中等 同为快速幂，可用来对比递归写法与迭代写法的取舍
29. 两数相除 中等 同样用倍增思想把线性过程压成对数，但方向是减法而非乘法
69. x 的平方根 简单 幂运算的逆问题，考察二分逼近与乘法溢出的规避
剑指 Offer 14- II. 剪绳子 II 中等 贪心结论加上大数取模，同样要求每一步乘法后立即归约