Your task is to calculate a^b 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
利用mod的性质，a^123 % k = (a ^ 120) % k × (a ^ 3) % k = (((a ^ 12) % k) ^ 10 % k) × (a ^ 3) % k。这题可以递归着做。不看答案真没想法。
int base = 1337;
public int superPow(int a, int[] b) {
if (b == null || b.length == 0) {
return 1;
}
return superPowHelper(a, b, b.length - 1);// 注意下标
}
private int superPowHelper(int a, int[] b, int i) {
if (i < 0) {// 注意下标
return 1;
}
return modPow(superPowHelper(a, b, i - 1), 10) % base * modPow(a, Integer.valueOf(b[i])) % base;
}
private int modPow(int a, int k) {
a = a % base;
int result = 1;
while (k > 0) {
result = (result * a) % base;
k--;
}
return result;
}