0372：超级次方（★）

力扣第 372 题

题目

你的任务是计算 ab 对 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 <= 231 - 1
• 1 <= b.length <= 2000
• 0 <= b[i] <= 9
• b 不含前导 0

分析

根据 $\begin{aligned} a^{b*10+c}=(a^{b})^{10}*a^{c}\end{aligned}$，递推即可。

解答

1
2
3
4
5
6

class Solution:
    def superPow(self, a: int, b: List[int]) -> int:
        res = 1
        for x in b:
            res = pow(res,10,1337)*pow(a,x,1337)%1337
        return res

43 ms