372. Super Pow (Medium)

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

Solution:

class Solution {
    int pow(int x, int n) {
        if (n == 0) return 1;
        if (n == 1) return x%1337;
        return pow(x%1337, n/2)*pow(x%1337, n-n/2)%1337 ;
    }
public:
    int superPow(int a, vector<int>& b) {
        long num = 1;
        for (int i = 0; i < b.size(); ++i) {
            num = pow(a,b[i])*pow(num,10)%1337;
        }
        return num;
    }
};