计算 3**15421过程如下:
3**15421=(3**1542)**10+3**1 // 3**1542=(3**154)**10+3**2 // 3**154= (3**15)**10+3*4 3**15=(3**1)**10+3**5
这样通过有限的操作次数就能完成计算 不需要计算一万多次
a*b%c 为 a%c * b%c
代码如下
int MOD=1337; public int superPow(int a, int[] b) { return dfs(a,b,b.length-1); } public int dfs(int a,int[] b,int index ){ if(index==-1){ return 1; } return pow(dfs(a, b, index - 1), 10) * pow(a, b[index]) % MOD; } //迭代版本的快速幂,快速幂件leetcode50 int pow(int a,int b){ int res = 1; a=a%MOD; while(b>0){ if((b&1)!=0){ res = res * a%MOD; } a=a*a%MOD; b>>=1; } return res; }