MOD = 1337
class Solution:
def superPow(self, a: int, b: List[int]) -> int:
def dfs(i):
if i == -1:
return 1
return quickPow(dfs(i - 1), 10) * quickPow(a, b[i]) % MOD
def quickPow(x, y):
ans = 1
x %= MOD
while y:
if y & 1:
ans = ans * x % MOD
x = x * x % MOD
y >>= 1
return ans
a %= MOD
return dfs(len(b) - 1)
Java实现
class Solution {
private static final int MOD = 1337;
public int superPow(int a, int[] b) {
return dfs(a % MOD, b, b.length - 1);
}
private int dfs(int a, int[] b, int idx) {
if(idx == -1 || a == 1)
return 1;
return qPow(dfs(a, b, idx - 1),10) * qPow(a, b[idx]) % MOD;
}
private 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;
}
}