如何高效进行模幂运算

今天来聊一道与数学运算有关的题目，力扣第 372 题「超级次方」，让你进行巨大的幂运算，然后求余数。

int superPow(int a, int[] b);

int superPow(int a, vector<int>& b);

def superPow(a: int, b: List[int])

func superPow(a int, b []int) int

var superPow = function(a, b) {}

要求你的算法返回幂运算 a^b 的计算结果与 1337 取模（mod，也就是余数）后的结果。就是你先得计算幂 a^b，但是这个 b 会非常大，所以 b 是用数组的形式表示的。

这个算法其实就是广泛应用于离散数学的模幂算法，至于为什么要对 1337 求模我们不管，单就这道题可以有三个难点：

一是如何处理用数组表示的指数，现在 b 是一个数组，也就是说 b 可以非常大，没办法直接转成整型，否则可能溢出。你怎么把这个数组作为指数，进行运算呢？

二是如何得到求模之后的结果？按道理，起码应该先把幂运算结果算出来，然后做 % 1337 这个运算。但问题是，指数运算你懂得，真实结果肯定会大得吓人，也就是说，算出来真实结果也没办法表示，早都溢出报错了。

三是如何高效进行幂运算，进行幂运算也是有算法技巧的，如果你不了解这个算法，后文会讲解。

那么对于这几个问题，我们分开思考，逐个击破。