LeetCode Super Pow Your task is to calculate ab mod 1337 where a is a positive integer and b is an extremely large positive integer given in the form of an array. Example1:
a = 2 b = [3] Result: 8Example2:
a = 2 b = [1,0] Result: 1024
快速幂的进阶版，超级幂。要求$$a^B=a^{[b_0,b_1,b_2,…b_{n-1}]}$$，其中的B用一个数组来表示，数组中的元素都是个位数，分别从高位到低位。比如第二个样例表示的是$$2^10$$。 我一开始把$$a^B=a^{[b_0,b_1,b_2,…b_{n-1}]}$$展开成$$a^B=a^{b_0*10^{n-1}+b_1*10^{n-2}+…}$$，对于每一项都用快速幂算出$$10^{n-i-1}$$，然后用快速幂算出$$a^{b_i*10^{n-i-1}}$$，最后累乘起来。但是很不幸WA或者TLE。 后来看了网上的题解，发现真是巧妙，这不就类似于多项式计算时层层嵌套的方法吗，一时想不起来那个叫什么名字了。比如我们要算$$a^{[b_0,b_1,b_2]}$$，本来是$$a^{b_0*10^2+b_1*10+b_2}$$。但是我们计算是可以这样算，先算$$C_0=a^{b_0}$$；递归到$$b_1$$时，在算到$$b_0$$的基础上，有$$C_1=(a^{b_0})^{10}*a^{b_1}=C_0^{10}*a^{b_1}$$；递归到$$b_2$$时，有$$C_2=((a^{b_0})^{10}*a^{b_1})^{10}*a^{b_2}=C_1^{10}*a^{b_2}$$。把$$C_2$$展开其实就是$$a^{b_0*10^2+b_1*10+b_2}$$。 完整代码如下： [cpp] typedef unsigned long long ull; class Solution { private: const static int MOD = 1337; ull fastPow(ull x, ull y) { ull ans = 1; while (y) { if (y & 1)ans = (ans*x) % MOD; y >>= 1; x = (x*x) % MOD; } return ans; } public: int superPow(int a, vector<int>& b) { ull ans = 1; for (int i = 0; i < b.size(); ++i) { ans = fastPow(ans, 10)*fastPow(a, b[i]) % MOD; } return ans; } }; [/cpp] 本代码提交AC，用时9MS。]]>