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.
Example 1:
Input: a = 2, b = [3]
Output: 8
Example 2:
Input: a = 2, b = [1,0]
Output: 1024
Example 3:
Input: a = 1, b = [4,3,3,8,5,2]
Output: 1
Constraints:
- 1 <= a <= 231 - 1
- 1 <= b.length <= 2000
- 0 <= b[i] <= 9
- b does not contain leading zeros.
class Solution {
int base = 1337;
public int superPow(int a, int[] b) {
if(b.length == 0){
return 1;
}
int part1 = myPow(a, b[b.length-1]);
int[] c = getNewArray(b);
int part2 = myPow(superPow(a, c), 10);
return (part1*part2)%base;
}
int[] getNewArray(int[] b){
if(b.length ==0){
return b;
}
int[] c = new int[b.length-1];
for(int i=0;i<b.length-1;i++){
c[i] = b[i];
}
return c;
}
// 计算a的k次方，然后对base求摸
int myPow(int a, int k){
// 先对因子取模
a %= base;
int res = 1;
for(int i=0;i<k;i++){
// 然后模模相乘
res *= a;
// 结果继续求模（防止溢出）
res %= base;
}
return res;
}
}The main idea is cashed on the repeated pattern of the remainder of a^b. As long as we know the length of the pattern m, we just have to find an index point of this pattern based on b mod m. In addition, if a > 1337, we can let a = a mod 1337. Because if we let a = (1337x + c) where c = a mod 1337, (1337x + c)(1337x + c)(1337x + c)...(1337x + c) mod 1337 == ccc...c mod 1337.