题目链接：超级次方
发现自己算法比较弱，打算恶补一下常用算法，故最近开始刷LeetCode题目，初步定为每天一道。中等和困难会写解析，简单的不写，可以关注一下。
你的任务是计算 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
解题思路
数学基础
乘积的余数=余数的乘积 (的余数)，(因为余数的乘积可能大于除数，因此还要求一次余。)
\[(\mathrm{a} \times \mathrm{b}) \% \mathrm{x}=((\mathrm{a} \% \mathrm{x}) \times(\mathrm{b} \% \mathrm{x})) \% \mathrm{x} \]递归快速幂算法
快速幂（Exponentiation by squaring，平方求幂）是一种简单而有效的小算法，它能以\(O(\log n)\)的时间复杂度计算乘方。快速幂不仅本身非常常见，而且后续很多算法也都会用到快速幂。
让我们先来思考一个问题：7的10次方，怎样算比较快？
方法1：最朴素的想法，7 * 7=49，49 * 7=343，... 一步一步算，共进行了9次乘法。
这样算无疑太慢了，尤其对计算机的CPU而言，每次运算只乘上一个个位数，无疑太屈才了。这时我们想到，也许可以拆分问题。
方法2：先算7的5次方，即7 * 7 * 7 * 7 * 7，再算它的平方，共进行了5次乘法。
但这并不是最优解，因为对于“7的5次方”，我们仍然可以拆分问题。
方法3：先算7 * 7得49，则7的5次方为49 * 49 * 7，再算它的平方，共进行了4次乘法。
模仿这样的过程，我们得到一个在时间内计算出幂的算法，也就是快速幂。
刚刚我们用到的，无非是一个二分的思路。我们很自然地可以得到一个递归方程：
\[a^n= \begin{cases}a^{n-1} \cdot a, & \text { if } n \text { is odd } \\ a^{\frac{n}{2}} \cdot a^{\frac{n}{2}}, & \text { if } n \text { is even but not } 0 \\ 1, & \text { if } n=0\end{cases} \]计算 \(a\) 的 次方，如果 \(n\) 是偶数（不为 0 )，那么就先计算 \(a\) 的 \(n / 2\) 次方，然后平方；如果 \(n\) 是奇数， 那么就先计算a的n-1次方，再乘上 \(a\) ；递归出口是 \(a\) 的 0 次方为 1 。
代码实现：
def qpow (a , b):
if a == 1 or b == 0:
return 1
if b % 2 == 1:
return a * qpow(a, b-1)
return qpow(a * a, n / 2)
上面的方法是针对一个数而言，对于一个数组 b 而言，也能使用递归进行计算.
这只是完成了b数组中的一个次幂，而对于数组b，我们也能用递归的思路去计算:
对于b=[1,2,3] :
在给定函数 superPow 中，我们从数组 b 的末尾项 3 开始，然后兵分两路，一路计算 \(\mathrm{a}^3\) ，也就是 qpow (a， 3)；然后将数组 b 中的最后 一项弹出，再递归调用函数 superPow 本身。这样，在第二层的函数 superPow 中，会计算 \(\mathrm{a}^2\) 并进入第三层计算 \(\mathrm{a}^1\) 。我们先关注第二层。
假设第三层已经全部算完了，返回第二层的的时候是返回了 \(\mathrm{a}^1\) 。这时它需要转换到 \(\mathrm{a}^{10}\) 再和 \(\mathrm{a}^2\) 相乘再取余。由于 \(\mathrm{a}^{10}\) 可能溢出，所以这个转 换我们也可以用 qpow 来完成。
这样一来，在第二层中一共要做以下的操作:
- 记录并弹出数组 \(b\) 的尾项，得到 \(k=2\) 。
- 计算 \(a^{10}\) :
left = qpow(superPow(a, b), 10) - 计算 \(a^2\) :
right = qpow(a, k) - 返回余数的乘积的余数 (
qpow返回的值已经求过余了) :return left * right % 1337
Python代码
class Solution(object):
def superPow(self, a, b):
res = 1
for x in b:
res = self.pow(res, 10) * self.pow(a, x) % 1337
return res
def pow(self, a, b):
if b == 0 or a == 1:
return 1
if b % 2 == 1:
return a * self.pow(a, b - 1) % 1337
return self.pow((a * a % 1337, b / 2)) % 1337