超级次方
你的任务是计算 对 1337 取模，a 是一个正整数，b 是一个非常大的正整数且会以数组形式给出。
示例:
输入：a = 2147483647, b = [2,0,0]
输出：1198
思路
解法一：
解题关键：a⋅b mod n = [(a mod n) (b mod n) ] mod n
假设 b 所代表的数值为 K，则有：K可转化成计算⌊K/10⌋ +(K mod 10),
MOD = 1337
class Solution:
def superPow(self, a: int, b: List[int]) -> int:
return self.dfs(a, b, len(b) - 1)
def dfs(self, a: int, b: List[int], u: int) -> int:
if u == -1: return 1
return self.pow(self.dfs(a, b, u -1), 10) * self.pow(a, b[u]) % MOD
def pow(self, a: int, x: int) -> int:
ans = 1
a %= MOD
while x > 0:
ans = ans * a % MOD
x -= 1
return ans
解法二：
基于解法1的基础上，使用快速幂的方法
MOD = 1337
class Solution:
def superPow(self, a: int, b: List[int]) -> int:
return self.dfs(a, b, len(b) - 1)
def dfs(self, a: int, b: List[int], u: int) -> int:
if u == -1: return 1
return self.pow(self.dfs(a, b, u -1), 10) * self.pow(a, b[u]) % MOD
def pow(self, a: int, x: int) -> int:
ans = 1
a %= MOD
while x != 0:
if (x & 1) != 0: # x的当前末位为1
ans = ans * a % MOD
a = a * a % MOD # a自乘
x >>= 1 # x右移一位
return ans