372. Super Pow

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

一刷
题解：用recursion来实现

class Solution {
    private final int base = 1337;
    public int superPow(int a, int[] b) {
        if(b.length == 0) return 1;
        int lastDigit = b[b.length-1];
        int[] copyArr = Arrays.copyOf(b, b.length-1);
        return powMod(superPow(a, copyArr), 10) * powMod(a, lastDigit)%base;
    }
    
    private int powMod(int a, int n){
        a %= base;
        int res = 1;
        for(int i=0; i<n; i++){
            res = (res*a)%base;
        }
        return res;
    }
}