超级次方
难度:
标签:
题目描述
你的任务是计算 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 <= 231 - 11 <= b.length <= 20000 <= b[i] <= 9b不含前导 0
代码结果
运行时间: 32 ms, 内存: 16.6 MB
// Java Stream solution
// 思路：使用类似的快速幂算法，不同的是使用Java Stream来处理数组。
// 我们可以将数组中的每个元素与其位置关联，然后使用reduce函数进行累积计算。
import java.util.stream.IntStream;
public class SolutionStream {
private static final int MOD = 1337;
public int superPow(int a, int[] b) {
a %= MOD;
return IntStream.range(0, b.length)
.mapToObj(i -> new int[]{b[i], i})
.reduce(1, (acc, val) -> (acc * powMod(a, val[0] * (int) Math.pow(10, val[1]))) % MOD, (x, y) -> x * y % MOD);
}
private int powMod(int a, int k) {
int result = 1;
while (k > 0) {
if (k % 2 == 1) {
result = (result * a) % MOD;
}
a = (a * a) % MOD;
k /= 2;
}
return result;
}
}解释
方法:
这个题解利用了模运算的性质来简化计算。具体来说，它从 b 数组的最低位开始，依次计算 a 的 b[i] 次方，然后再乘以之前的结果的 10 次方，最后对 1337 取模。这样可以避免直接计算 a 的巨大次方，而是将其拆解为多个较小的计算。
时间复杂度:
O(n)
空间复杂度:
O(1)
代码细节讲解
🦆
在解题算法中，为什么每一步都需要对 1337 取模？这对计算结果有什么影响？
▷🦆
算法中使用了 `pow(ans, 10, MOD) * pow(a, e, MOD) % MOD`，这里的 `pow` 函数是如何确保计算不会因为大数而溢出的？
▷🦆
考虑到 b 数组可能非常长（最长 2000），整体算法是否可能受到某些极端情况的影响，例如当 a 接近上限 2147483647 时？
▷🦆
在递归地计算 `pow(ans, 10, MOD)` 时，是否存在某种模式或周期性，使得结果可能提前预知而避免重复计算？
▷相关问题
Pow(x, n)
实现 pow(x, n) ，即计算 x 的整数 n 次幂函数（即，xn ）。
示例 1：
输入：x = 2.00000, n = 10 输出：1024.00000
示例 2：
输入：x = 2.10000, n = 3 输出：9.26100
示例 3：
输入：x = 2.00000, n = -2 输出：0.25000 解释：2-2 = 1/22 = 1/4 = 0.25
提示：
-100.0 < x < 100.0-231 <= n <= 231-1n是一个整数- 要么
x不为零，要么n > 0。 -104 <= xn <= 104