Question

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

What we know:

• \(a^{x + y} = a^x \times a^y\);
• \(a^{xy} = (a^x)^y\);
• \((ab) \% k = ((a \% k)(b \% k)) \% k\);

Thus, we have

\(a^{10x+y} \% k = (((a^x \% k)^{10} \% k)\times (a^y \% k)) \% k\).

If we have a function \(f(a, b) = a^b \% k\), then the above equation can be written as \(a^{10x+y} = (f(f(a, x), 10)\times f(a, y)) \% k\).

class Solution {
    private static final int MOD = 1337;
    public int superPow(int a, int[] b) {
        a = a % MOD;
        if (a == 0) return a;
        if (b.length == 0) return 1;
        int res = powMod(a, b[0]);
        for(int i = 1; i < b.length; i++)
            res = (powMod(res, 10) * powMod(a, b[i])) % MOD;
        return res;
    }

    private int powMod(int a, int b) {
        if(b == 0) return 1;
        a = a % MOD;
        int res = a;
        for(int i = 1; i < b; i++)
            res = res * a % MOD;
        return res;
    }
}