Super Pow

The problem is asking for (a^b \mod 1337), where (a) is an integer and (b) is a very large integer given in the form of an array.

A brute force approach is infeasible due to the constraint on the size of (b). To solve this problem, we can use the properties of modular arithmetic and break down the computation of the power.

First, let’s recall that ((a \cdot b) \mod m = (a \mod m) \cdot (b \mod m) \mod m). We can use this property to break down the computation of (a^b \mod 1337).

Consider the number (b = b_0b_1b_2 \ldots b_n), where each (b_i) is a digit of (b). We can represent (b) as (b_0 \cdot 10^n + b_1 \cdot 10^{n-1} + \ldots + b_n).

Using the properties of exponents and modular arithmetic, we can compute (a^b \mod 1337) as follows:

[ a^b \mod 1337 = \left(a^{b_0 \cdot 10^n} \cdot a^{b_1 \cdot 10^{n-1}} \cdot \ldots \cdot a^{b_n} \right) \mod 1337 ]

Now we can break down each part of the expression and compute it modulo 1337.

Here’s the code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

from typing import List

class Solution:
    def superPow(self, a: int, b: List[int]) -> int:
        MOD = 1337

        def modPow(x: int, y: int) -> int:
            result = 1
            x %= MOD
            while y > 0:
                if y % 2:
                    result = (result * x) % MOD
                x = (x * x) % MOD
                y //= 2
            return result

        result = 1
        for digit in b:
            result = modPow(result, 10) * modPow(a, digit) % MOD
        return result

This code computes the result by breaking down the computation of the power into parts and applying the properties of modular arithmetic. It uses a helper function modPow to compute the modular exponentiation efficiently.