LC 372. 超级次方

题目描述

这是 LeetCode 上的 372. 超级次方 ，难度为 中等。

你的任务是计算 ab 对 $1337$ 取模，a 是一个正整数，b 是一个非常大的正整数且会以数组形式给出。

示例 1：

输入：a = 2, b = [3]

输出：8

示例 2：

输入：a = 2, b = [1,0]

输出：1024

示例 3：

输入：a = 1, b = [4,3,3,8,5,2]

输出：1

示例 4：

输入：a = 2147483647, b = [2,0,0]

输出：1198

提示：

• $1 <= a <= 2^{31} - 1$
• $1 <= b.length <= 2000$
• $0 <= b[i] <= 9$
• b 不含前导 0

---

递归 + 快速幂（可选）

根据题意，要我们求得的是 $a^b \bmod {1337}$ 的值，其中 $b$ 是以数组形式给出。

刚一看是一道快速幂的题目（事实上也确实可以使用快速幂，但不是必须），由于 $b$ 是数组形式，因此我们还需要对其进行分解。

假设 $b$ 所代表的数值为 $K$，则有：

$$a^{K} = a^{(\left \lfloor \frac{K}{10} \right \rfloor * 10) + (K \bmod 10)} = a^{(\left \lfloor \frac{K}{10} \right \rfloor * 10)} * a^{(K \bmod 10)} = ({a^{\left \lfloor \frac{K}{10} \right \rfloor}) ^ {10}} * a^{(K \bmod 10)}$$

也就是说，我们每次只需要计算 $b$ 数组的最后一位作为次方的值即可将问题规模缩小。

上述公式可能不好直接理解，举个🌰，设我们的 $a$ 为 $99$，要计算的 $b$ 数组所代表的数值为 $K = 2345$，那么其计算过程可以分解为：

1. $a^K = 99^{2345}$
2. $99^{2345} = 99^{234 * 10 + 5}$
3. $99^{234 10 + 5} = 99^{234 10} * 99^{5}$
4. $99^{234 10} 99^{5} = {(99^{234})}^{10} * 99^{5}$
   …

可见，真正涉及计算次方的操作，所用到的次方都是一个 $10$ 以内的数字，因此并非一定要使用快速幂。

代码（$P2$ 为不使用快速幂）：

class Solution {
    int MOD = 1337;
    public int superPow(int a, int[] b) {
        return dfs(a, b, b.length - 1);
    }
    int dfs(int a, int[] b, int u) {
        if (u == -1) return 1;
        return qpow(dfs(a, b, u - 1), 10) * qpow(a, b[u]) % MOD;
    }
    int qpow(int a, int b) {
        int ans = 1;
        a %= MOD;
        while (b != 0) {
            if ((b & 1) != 0) ans = ans * a % MOD;
            a = a * a % MOD;
            b >>= 1;
        }
        return ans;
    }
}

class Solution {
    int MOD = 1337;
    public int superPow(int a, int[] b) {
        return dfs(a, b, b.length - 1);
    }
    int dfs(int a, int[] b, int u) {
        if (u == -1) return 1;
        return pow(dfs(a, b, u - 1), 10) * pow(a, b[u]) % MOD;
    }
    int pow(int a, int b) {
        int ans = 1;
        a %= MOD;
        while (b-- > 0) ans = ans * a % MOD;
        return ans;
    }
}

• 时间复杂度：假设 $b$ 数组所代表的数字为 $K$，使用快速幂的复杂度为 $O(\log{K})$，或者说是 $O(n \log{10})$，其中 $n$ 为数组 $b$ 的长度，数字 $10$ 所代表的含义是计算一个次方为 $10$ 以内的值；而不使用快速幂的复杂度为 $O(n 10)$
• 空间复杂度：忽略递归带来的额外空间开销，复杂度为 $O(1)$

---

最后

这是我们「刷穿 LeetCode」系列文章的第 No.372 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。