Super Pow--C++ Clean and Short Solution

关于Leetcode中的Super Pow 一题有几种不同的解法，在Leetcode的discuss板块中，我发现了一种很棒的解题思路，顺便翻译一下（加深记忆）。

作者：fentoyal
地址：C++ Clean and Short Solution

翻译如下：

同余模定理：$ab \% k = (a \% k) * (b \% k) \% k$

由于幂存放在数组中，我们最好将它一位一位的处理。

通过观察可知：(其实为了便于理解可以先将取模的过程去掉，这里保留原式子）
$a^{1234567} \% k = (a^{1234560} \%k) * (a^7 \% k) \% k = (a^{123456} \%k)^{10} \% k * (a^7 \% k) \% k$

看起来有点复杂？让我们采取另一种表达方式：
假设$f(a,b)$表示计算$a^b\%k$ 然后利用该函数表示上面的公式：
$f(a,1234567)=f(a,1234560) * f(a,7) \%k = f(f(a,123456), 10) * f(a,7) \%k$

代码实现如下：

class Solution {const int base = 1337;int powmod(int a, int k) //a^k mod 1337 where 0 <= k <= 10{a %= base;int result = 1;for (int i = 0; i < k; ++i)result = (result * a) % base;return result;}
public:int superPow(int a, vector<int>& b) {if (b.empty()) return 1;int last_digit = b.back();b.pop_back();return powmod(superPow(a, b), 10) * powmod(a, last_digit) % base;}
};

Note: 这种方法显然不是最快的，但是当我们在面试中被问到这个问题时可以很快的理解并写出。还有这个方法没有使用内建的pow函数，我想这也是面试官所期待的。
希望它对你有帮助！