题目
你的任务是计算 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
解题
方法一：快速幂
qPow(a,b)是指数运算，a是一个正整数，b是0~9的整数
由于vector& b是一个数组，因此通过qPow(dfs(a,b,index-1),10)*qPow(a,b[index])%MOD;将它分解成很多个qPow
取余规则的推导
快速幂的核心
class Solution { public: const int MOD=1337; int superPow(int a, vector<int>& b) { return dfs(a%MOD,b,b.size()-1); } int dfs(int a,vector<int>& b,int index){ if(index==-1||a==1){ return 1; } return qPow(dfs(a,b,index-1),10)*qPow(a,b[index])%MOD; } int qPow(int a,int b){ int res=1; a%=MOD; while(b>0){ if((b&1)!=0){ res=res*a%MOD; } a=a*a%MOD; b>>=1; } return res; } };
