友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
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 <= 231 - 1 -
1 <= b.length <= 2000 -
0 <= b[i] <= 9 -
b不含前导 0
思路分析
数学运算+分治模式。
首先，可以推理出如下公式：
\((a⋅b) mod m=[(amodm)⋅(bmodm)]modm\)
那么，a..xyz 可以转换成 …((ax)10)10(ay)10(az)，然后，按照上述公式做计算，即可求出最后结果。
-
一刷
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2025-07-23 12:21:04
*/
static final int MOD = 1337;
public int superPow(int a, int[] b) {
int result = 1;
for (int i = b.length - 1; i >= 0; i--) {
result = ((result % MOD) * pow(a, b[i])) % MOD;
a = pow(a, 10);
}
return result;
}
private int pow(int a, int x) {
int result = 1;
while (x != 0) {
a %= MOD;
if (a == 1) {
return 1;
}
if (x % 2 != 0) {
result = (result * a) % MOD;
}
a = (a * a) % MOD;
x /= 2;
}
return result % MOD;
}