LeetCode Super Pow

372. Super Pow

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

方法

此题由于指数位是数组，所以即使使用二分法求解也会超出范围。换个思路，需要知道有关取余的公式，如a*b % k = (a%k)(b%k)%k ==> a^1234560*a^7 % k = (a^1234560 % k) * (a^7 % k) % k：

a^1234567 % k = (a^1234560 % k) * (a^7 % k) % k = (a^123456 % k)^10 % k * (a^7 % k) % k

假设f(a,b)计算a^b%k,得:

f(a,1234567) = f(a, 1234560) * f(a, 7) % k = f(f(a, 123456),10) * f(a,7)%k;

public class Solution {
    public int superPow(int a, int[] b) {
        if(b.length == 0){
            return 1;
        }
        int last = b[b.length-1];
        int[] newB = new int[b.length-1];
        for(int i = 0; i < b.length-1;i++){
            newB[i] = b[i];
        }
        return pow(superPow(a,newB),10)*pow(a,last) % 1337;
    }
    public int pow(int a, int p){
        a = a % 1337;
        int res = 1;
        for(int i = 0; i < p; i++){
            res = (a*res)%1337;
        }
        return res;
    }
}