LeetCode 372. 超级次方

约 5 分钟
文章信息 6 个分类 2 个标签
分类
LeetCode CodeTop 中等 未解决 1-2 百度
标签
数学 分治

题目描述

✅ 372. 超级次方

image-20260929094914714

image-20260929094914816

题意分析

指数不是一个普通整数，而是按从高位到低位保存的十进制数字数组 b，需要计算对应的 $a^B\bmod 1337$。指数可能长达 $2000$ 位，不能先拼接成机器整数，也不能把乘法重复执行 $B$ 次。

题目只需要余数，可以始终保存模 1337 后的结果。关键是根据十进制位逐步合并指数，而不实际构造完整的 $B$。

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

核心思路

[!blue]

设去掉最后一位后的指数为 $p$，最后一位是 $d$，那么完整指数为 $10p+d$。利用幂的运算规律，有：

\[a^{10p+d}=(a^p)^{10}\cdot a^d\]

因而只要知道前缀的模幂结果，就能把它升到十次方，再乘上当前数字位贡献的 $a^d$，最后取模。乘法和取模可以交换先后，所以前缀只保留余数就足够，这个恒等式不要求 a 与 1337 互质。

定义 dfs(a,b,len) 为数组前 len 位表示的指数所对应的模幂。先递归得到前 len-1 位的结果，再合并 b[len-1]。len 只表示前缀长度，没有复制或截取数组；len == 0 表示内部递归的空前缀，即指数零，返回乘法单位元 1。

合并时的两个指数只有 10 和 0..9，用快速幂即可。辅助函数维护当前结果 res、尚未使用的幂 base 和剩余指数 e：最低位为一就将 base 乘入结果，再将底数平方、指数右移，逐位消耗指数。指数为零时不进入循环，直接返回 1。

底数先取模，每次乘法后也立刻取模，使参与下一次运算的余数始终小于 1337。当前数字位为零时，只是 $a^d=1$，前缀结果的十次方仍然必须计算，否则就丢失了十进制位权。

解题步骤

  1. 将底数缩小为 a % 1337，从完整数组长度开始递归。
  2. 当前长度为零时返回 1；否则记下末位，并递归计算前一段指数的模幂。
  3. 用快速幂计算前缀结果的十次方，以及缩减后底数的末位次方。
  4. 将两项相乘取模并返回。递归返回时逐位恢复完整指数，最外层得到最终余数。

代码实现

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)$，其中 $n$ 是指数的十进制位数。每位对应一层递归，辅助快速幂的指数最多为 10，每次最多处理四个二进制位，属于常数工作。
  • 空间复杂度：$O(n)$，递归栈深度随指数位数增长；数组不复制，快速幂仅用常数额外空间。

关键点总结

[!green]

  • 加入数字位对应指数乘十再加当前位。
  • 空前缀的幂为一，是递归基例。
  • 逐位恒等式不要求底数与模数互质。

易错点总结

[!yellow]

  • 把指数拼成机器整数：长指数超出表示范围。
  • 忽略前缀结果的十次方：数字位权错误。
  • 数字位为零就跳过整层：漏掉前缀指数乘十。
  • 乘法只在最后取模：中间数值会迅速增长。

相似题目

题目 难度 关联与区别
50. Pow(x, n) 中等 本题指数以十进制数组给出，可按a^(10b+d)分解并调用快速幂，避免把指数整体转整数。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2022/70330440
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！