力扣372题（超级次方）

372、超级次方

基本思想：

公式1: 两数乘积之模的拆分
(a * b) % k = (a % k)(b % k) % k

公式2: 某数的n次幂取模的拆分
a^n % k = (a % k)^n % k

递归

具体实现：

公式1: 两数乘积之模的拆分
(a * b) % k = (a % k)(b % k) % k

公式2: 某数的n次幂取模的拆分
a^n % k = (a % k)^n % k

比如假设a=2 b=[1, 2, 3]
其实就是求a ** 123 % 1337

根据幂运算的规律，可以把幂运算拆成两数相乘的形式：

a ** 123 = (a ** 3) * (a**120)
= (a ** 3) * ((a**12) ** 10)
利用公式1把上面那个式子拆成两部分：
part1 = a ** 3 % 1337
part2 = (a ** 12) ** 10 % 1337

利用公式2，继续拆分part2
part2 = (a ** 12 % 1337) ** 10 % 1337

那最终的结果就变成：
(part1 * part2) % base

可以看到，在利用公式2拆分的时候，有一步是：
(a ** 12 % 1337)

这其实就是(a ** 123 % 1337)的简化版本，所以这里用递归来解决问题

代码：

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

        if not b:
            return 1
        last = b.pop()

        part1 = (a ** last) % base
        part2 = (self.superPow(a, b) ** 10) % base

        return (part1 * part2) % base