Super Pow

1. Initialize result = 1.
2. Create a helper function power(base, exp, mod) for modular exponentiation using the binary exponentiation method.
3. Iterate through each digit d in the input array b from left to right.
4. In each iteration, update the result by applying the rule a^(10*x + d) = (a^x)^10 * a^d. The new result is calculated as result = (power(result, 10, 1337) * power(a, d, 1337)) % 1337.
5. After iterating through all digits, result will hold the final value of a^b % 1337.

This approach works by processing the digits of the large exponent b one by one from left to right. The core idea relies on the mathematical property x^(10y + z) = (x^y)^10 * x^z. Let's say we have processed a prefix of b and calculated res = a^(prefix) % 1337. When we consider the next digit d, the new exponent becomes prefix * 10 + d. The new result can be calculated as a^(prefix * 10 + d) % 1337, which is equivalent to (a^(prefix * 10) * a^d) % 1337. This further simplifies to ((a^prefix)^10 * a^d) % 1337. Since we already have res = a^(prefix) % 1337, the updated result is (power(res, 10, 1337) * power(a, d, 1337)) % 1337. We start with a result of 1 (for an empty prefix) and iterate through all digits of b, updating the result in each step. A helper function for modular exponentiation, power(base, exp), is used to efficiently compute powers under a modulus. This function uses the binary exponentiation (or exponentiation by squaring) algorithm.

1class Solution {2    private int MOD = 1337;3 4    public int superPow(int a, int[] b) {5        if (a % MOD == 0) return 0;6        a %= MOD;7        int result = 1;8        for (int digit : b) {9            result = (power(result, 10) * power(a, digit)) % MOD;10        }11        return result;12    }13 14    // Computes (base^exp) % MOD using binary exponentiation15    private int power(int base, int exp) {16        int res = 1;17        base %= MOD;18        while (exp > 0) {19            if (exp % 2 == 1) {20                res = (int)((long)res * base % MOD);21            }22            base = (int)((long)base * base % MOD);23            exp /= 2;24        }25        return res;26    }27}

1. Factor the modulus: 1337 = 7 * 191.
2. The problem x = a^b % 1337 is split into a system of congruences: x ≡ a^b (mod 7) and x ≡ a^b (mod 191).
3. To solve these, we use Fermat's Little Theorem, which reduces the exponent b modulo p-1. We need to compute b % 6 and b % 190.
4. The remainders b % m are calculated by iterating through the digits of b: rem = (rem * 10 + digit) % m.
5. Handle the edge case where b % (p-1) == 0. The effective exponent should be p-1, not 0.
6. Calculate res1 = a^b (mod 7) and res2 = a^b (mod 191) using the reduced exponents.
7. Combine res1 and res2 using the Chinese Remainder Theorem (CRT) to find the unique solution x modulo 1337.

This advanced approach uses number theory to find the solution more efficiently. The modulus 1337 is not a prime number; it can be factored into 7 * 191. This allows us to use the Chinese Remainder Theorem (CRT). The problem of finding x = a^b % 1337 is broken down into solving a system of two congruences:

1. x ≡ a^b (mod 7)
2. x ≡ a^b (mod 191)

To solve each congruence, we use Fermat's Little Theorem. This implies that the exponent b can be reduced modulo p-1. So, we need to compute b % (7-1) = b % 6 and b % (191-1) = b % 190. The value of b modulo some number m can be found by iterating through its digits. Once we have res1 = a^b % 7 and res2 = a^b % 191, we use the CRT to combine them. We look for a number x that satisfies both congruences. The solution will be unique modulo 7 * 191 = 1337. The implementation requires pre-calculating the modular multiplicative inverse of 7 modulo 191, which is 82.

1class Solution {2    private final int MOD = 1337;3 4    public int superPow(int a, int[] b) {5        if (a % MOD == 0) return 0;6 7        // Calculate b mod phi(7)=6 and b mod phi(191)=1908        int b_mod_6 = getBModM(b, 6);9        if (b_mod_6 == 0) b_mod_6 = 6; // For b>=1, a^b = a^(phi) if b%phi=010 11        int b_mod_190 = getBModM(b, 190);12        if (b_mod_190 == 0) b_mod_190 = 190;13 14        // Calculate res1 = a^b mod 715        int res1 = power(a, b_mod_6, 7);16        17        // Calculate res2 = a^b mod 19118        int res2 = power(a, b_mod_190, 191);19 20        // Use Chinese Remainder Theorem to find the unique solution21        // x ≡ res1 (mod 7)22        // x ≡ res2 (mod 191)23        // From x = 7k + res1, we get 7k + res1 ≡ res2 (mod 191)24        // k ≡ (res2 - res1) * modInverse(7, 191) (mod 191)25        // The modular inverse of 7 mod 191 is 82.26        int k = (res2 - res1 + 191) % 191; // Handle negative result27        k = (int)((long)k * 82 % 191);28        29        return res1 + 7 * k;30    }31 32    // Computes b % m33    private int getBModM(int[] b, int m) {34        int rem = 0;35        for (int digit : b) {36            rem = (rem * 10 + digit) % m;37        }38        return rem;39    }40 41    // Computes (base^exp) % mod42    private int power(int base, int exp, int mod) {43        int res = 1;44        base %= mod;45        while (exp > 0) {46            if (exp % 2 == 1) {47                res = (int)((long)res * base % mod);48            }49            base = (int)((long)base * base % mod);50            exp /= 2;51        }52        return res;53    }54}