The key idea is to use modular exponentiation and the property:
a^(b1b2...bn) = ((a^(b1b2...bn-1))^10) * (a^bn)
This allows us to break down the large exponent (given as an array) into smaller problems, recursively solving for each digit.
classSolution {
public:int mod =1337;
intpowmod(int a, int k) {
int ans =1;
a %= mod;
while (k) {
if (k %2) ans = ans * a % mod;
a = a * a % mod;
k /=2;
}
return ans;
}
intsuperPow(int a, vector<int>& b) {
if (b.empty()) return1;
int d = b.back(); b.pop_back();
int part1 = powmod(superPow(a, b), 10);
int part2 = powmod(a, d);
return part1 * part2 % mod;
}
};
classSolution {
int mod = 1337;
privateintpowmod(int a, int k) {
int ans = 1;
a %= mod;
while (k > 0) {
if (k % 2 == 1) ans = ans * a % mod;
a = a * a % mod;
k /= 2;
}
return ans;
}
publicintsuperPow(int a, List<Integer> b) {
if (b.isEmpty()) return 1;
int d = b.remove(b.size() - 1);
int part1 = powmod(superPow(a, b), 10);
int part2 = powmod(a, d);
return part1 * part2 % mod;
}
}
classSolution {
privateval mod = 1337privatefunpowmod(a: Int, k: Int): Int {
var ans = 1var base = a % mod
var exp = k
while (exp > 0) {
if (exp % 2==1) ans = ans * base % mod
base = base * base % mod
exp /=2 }
return ans
}
funsuperPow(a: Int, b: MutableList<Int>): Int {
if (b.isEmpty()) return1val d = b.removeAt(b.size - 1)
val part1 = powmod(superPow(a, b), 10)
val part2 = powmod(a, d)
return part1 * part2 % mod
}
}
classSolution:
mod: int =1337defpowmod(self, a: int, k: int) -> int:
ans =1 a %= self.mod
while k:
if k %2:
ans = ans * a % self.mod
a = a * a % self.mod
k //=2return ans
defsuperPow(self, a: int, b: list[int]) -> int:
ifnot b:
return1 d = b.pop()
part1 = self.powmod(self.superPow(a, b), 10)
part2 = self.powmod(a, d)
return part1 * part2 % self.mod
impl Solution {
pubfnsuper_pow(a: i32, b: Vec<i32>) -> i32 {
fnpowmod(mut a: i32, mut k: i32, m: i32) -> i32 {
letmut ans =1;
a %= m;
while k >0 {
if k %2==1 {
ans = ans * a % m;
}
a = a * a % m;
k /=2;
}
ans
}
fnhelper(a: i32, b: &[i32], m: i32) -> i32 {
if b.is_empty() {
return1;
}
let d = b[b.len() -1];
let part1 = powmod(helper(a, &b[..b.len() -1], m), 10, m);
let part2 = powmod(a, d, m);
part1 * part2 % m
}
helper(a, &b, 1337)
}
}