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

Two points:

• x mod y = (mn) mod y = (m mod y) (n mod y)
• x^325 = x^300 x^20 x^5 = (x^(100))^3 (x^(10))^2 x^5. at each bit of 325, the base is actually x^10 of previous base.

public class Solution {
    int mod = 1337;
    public int superPow(int a, int[] b) {
        if(b == null || b.length == 0) return 1;
        int res = 1;
        for( int i = b.length-1; i >=0;i--){
            res = (res * quickPow(a, b[i])) % mod;
            a = quickPow(a, 10);
        }

        return res;
    }
    private int quickPow(int a, int b){
        int res = 1;
        a = a % mod;

        while(b > 0){
            if((b&1) != 0) res = (res * a) % mod;
            a = (a*a)%mod;
            b >>= 1;
        }
        return res;
    }
}