脚本宝典收集整理的这篇文章主要介绍了LeetCode 12.5每日一题,脚本宝典觉得挺不错的,现在分享给大家,也给大家做个参考。
372. 超级次方
你的任务是计算 ab
对 1337
取模,a
是一个正整数,b
是一个非常大的正整数且会以数组形式给出。
a^b=(a^(b/10))^10*a^(b%10)
每次算最后一位,前面的递归处理,从最后一位倒置处理
class Solution {
int MOD = 1337;
//计算的过程,b从尾到头计算幂,去掉最后一位,计算最后一位的幂,再考虑前面所有位的dfs值^10,*最后一位的幂%MOD
public int superPow(int a, int[] b) {
return dfs(a, b, b.length - 1);
}
int dfs(int a, int[] b, int u) {
if (u == -1) return 1;//u==0,自然返回1
return (pow(dfs(a, b, u - 1), 10)%MOD * pow(a, b[u]) % MOD)%MOD;
}
int pow(int a, int b) {
int ans = 1;
a %= MOD;
while (b-- > 0) ans = ans * a % MOD;
return ans;
}
}
以上是脚本宝典为你收集整理的LeetCode 12.5每日一题全部内容,希望文章能够帮你解决LeetCode 12.5每日一题所遇到的问题。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。