题目描述
这是 LeetCode 上的 372. 超级次方 ,难度为 中等。
Tag : 「数学」、「快速幂」
你的任务是计算 ab
对 13371337 取模,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} - 11<=a<=231−1
- 1 <= b.length <= 20001<=b.length<=2000
- 0 <= b[i] <= 90<=b[i]<=9
- b 不含前导 0
递归 + 快速幂(可选)
根据题意,要我们求得的是 a^b \bmod {1337}abmod1337 的值,其中 bb 是以数组形式给出。
刚一看是一道快速幂的题目(事实上也确实可以使用快速幂,但不是必须),由于 bb 是数组形式,因此我们还需要对其进行分解。
假设 bb 所代表的数值为 KK,则有:
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)}aK=a(⌊10K⌋∗10)+(Kmod10)=a(⌊10K⌋∗10)∗a(Kmod10)=(a⌊10K⌋)10∗a(Kmod10)
也就是说,我们每次只需要计算 bb 数组的最后一位作为次方的值即可将问题规模缩小。
上述公式可能不好直接理解,举个🌰,设我们的 aa 为 9999,要计算的 bb 数组所代表的数值为 K = 2345K=2345,那么其计算过程可以分解为:
- a^K = 99^{2345}aK=992345
- 99^{2345} = 99^{234 * 10 + 5}992345=99234∗10+5
- 99^{234 * 10 + 5} = 99^{234 * 10} * 99^{5}99234∗10+5=99234∗10∗995
- 99^{234 * 10} * 99^{5} = {(99^{234})}^{10} * 99^{5}99234∗10∗995=(99234)10∗995
...
可见,真正涉及计算次方的操作,所用到的次方都是一个 1010 以内的数字,因此并非一定要使用快速幂。
代码(P2P2 为不使用快速幂):
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; } } 复制代码
- 时间复杂度:假设 bb 数组所代表的数字为 KK,使用快速幂的复杂度为 O(\log{K})O(logK),或者说是 O(n * \log{10})O(n∗log10),其中 nn 为数组 bb 的长度,数字 1010 所代表的含义是计算一个次方为 1010 以内的值;而不使用快速幂的复杂度为 O(n * 10)O(n∗10)
- 空间复杂度:忽略递归带来的额外空间开销,复杂度为 O(1)O(1)
最后
这是我们「刷穿 LeetCode」系列文章的第 No.372
篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先把所有不带锁的题目刷完。
在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:github.com/SharingSour… 。
在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。