372 Super Pow
Problem:
Your task is to calculate ab mod 1337 where a is a positive integer and b is an extremely large positive integer given in the form of an array.
Example1:
a = 2
b = [3]
Result: 8
Example2:
a = 2
b = [1,0]
Result: 1024
Solutions:
public class Solution {
public int superPow(int a, int[] b) {
long res = 1;
a = a % 1337;
for (int i = 0; i < b.length; ++i) {
res = pow(res, 10) * pow(a, b[i]) % 1337;
}
return (int)res;
}
private long pow(long x, int n) {
if (n == 0) return 1;
long v = pow(x, n / 2);
if (n % 2 == 0) {
return v * v % 1337;
}
else {
return v * v * x % 1337;
}
}
}