372. 超级次方

你的任务是计算a^b对1337取模，a是一个正整数，b是一个非常大的正整数且会以数组形式给出。

示例 1：

输入：a = 2, b = [3]
输出：8

示例 2：

输入：a = 2, b = [1,0]
输出：1024

示例 3：

输入：a = 1, b = [4,3,3,8,5,2]
输出：1

示例 4：

输入：a = 2147483647, b = [2,0,0]
输出：1198

提示：

• 1 <= a <= 2^31 - 1
• 1 <= b.length <= 2000
• 0 <= b[i] <= 9
• b不含前导 0

Python解答：
1.简单快速幂，超时

class Solution:
    def superPow(self, a: int, b: List[int]) -> int:
        lens = len(b)
        new_b = 0
        for i in range(lens):
            new_b += b[i] * pow(10, lens-i-1)
        def compute(a, b):
            if b == 0:
                return 1
            elif b % 2 == 0:
                return compute(a*a, b//2)
            else:
                return compute(a*a, (b-1)//2) * a

        return compute(a, new_b) % 1337

2.改进版

class Solution:
    def superPow(self, a: int, b: List[int]) -> int:
        lens = len(b)
        result = 1
        for i in range(lens):
            result = self.mypow(result, 10, 1337) * self.mypow(a, b[i], 1337)
        return result % 1337

    def mypow(self, a, n, m):
        result = 1
        while n > 0:
            if n & 1 == 1:
                result = result * a % m
            a = a * a % m 
            n >>= 1
        return result