你的任务是计算 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
乘方快速幂。
class Solution:
def superPow(self, a: int, b: List[int]) -> int:
MOD = 1337
ans = 1
for e in b[::-1]:
ans = ans * pow(a, e, MOD) % MOD
a = pow(a, 10, MOD)
return ans
class Solution {
private static final int MOD = 1337;
public int superPow(int a, int[] b) {
int ans = 1;
for (int i = b.length - 1; i >= 0; --i) {
ans = (int) ((long) ans * quickPowAndMod(a, b[i]) % MOD);
a = quickPowAndMod(a, 10);
}
return ans;
}
private int quickPowAndMod(int a, int b) {
int ans = 1;
while (b > 0) {
if ((b & 1) == 1) {
ans = (ans * (a % MOD)) % MOD;
}
b >>= 1;
a = (a % MOD) * (a % MOD) % MOD;
}
return ans;
}
}
class Solution {
const int MOD = 1337;
public:
int superPow(int a, vector<int>& b) {
int ans = 1;
for (int i = b.size() - 1; i >= 0; --i) {
ans = (long)ans * quickPowAndMod(a, b[i]) % MOD;
a = quickPowAndMod(a, 10);
}
return ans;
}
int quickPowAndMod(int a, int b) {
int ans = 1;
while (b) {
if (b & 1) {
ans = (ans * (a % MOD)) % MOD;
}
b >>= 1;
a = ((a % MOD) * (a % MOD)) % MOD;
}
return ans;
}
};
const mod = 1337
func superPow(a int, b []int) int {
ans := 1
for i := len(b) - 1; i >= 0; i-- {
ans = ans * quickPowAndMod(a, b[i]) % mod
a = quickPowAndMod(a, 10)
}
return ans
}
func quickPowAndMod(a, b int) int {
ans := 1
for b > 0 {
if b&1 > 0 {
ans = ans * a % mod
}
b >>= 1
a = ((a % mod) * (a % mod)) % mod
}
return ans
}