372 超级次方

本文最后更新于：2021年1月7日 下午

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

示例 1：

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

示例 2：

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

示例 3：

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

示例 4：

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

提示：

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

Solution

参考：《算法小抄》5.2

  • 模运算、幂运算
  • 快速求幂

幂运算递归式：
$$
a^b = \begin{cases} a*x^{b-1}, & \text {b 为奇数} \ (a^{b/2})^2, & \text {b 为偶数} \end{cases}
$$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# @lc code=start
class Solution:
    def __init__(self):
        self.base = 1337

    def mypow(self, a, k):
        if k == 0: return 1
        if k % 2 == 1:
            return (a * self.mypow(a, k - 1)) % self.base
        else:
            sub = self.mypow(a, k // 2)
            return (sub * sub) % self.base

    def superPow(self, a: int, b: List[int]) -> int:
        self.base = 1337
        if not b: return 1
        last = b.pop()
        part1 = self.mypow(a, last)
        part2 = self.mypow(self.superPow(a, b), 10)
        return (part1 * part2) % self.base

# @lc code=end
algo leetcode 算法

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！