Leetcode 372. Super Pow
Leetcode 372. Super Pow
xindoo
发布于 2021-01-21 18:06:35
发布于 2021-01-21 18:06:35
题目链接：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. 简短的题目，让你求(a^b)%1337的值，但b是以数组的形式给出的，这就意味着b可能非常非常大。看到题目我立马想到了大数的快速幂取模，利用java自带的Biginteger应该可以很轻易做的，但仔细想想，其实java做做大数的运算非常慢的，虽然代码简单了，但实际上是让计算机去做大量的计算，所以我就放弃了这种想法，不知道直接大数快速幂取模能不能ac。
真正的解法其实思路很简单，我随便举个例子就很容易理解了，假设要求(123^4567)%1337,只需要把这个幂式子分解成几个层次，然后把球模加到每一层中间就很容易计算出来了。
123^4567 = ((((((123)^4)^10*(123)^5)^10)*123^6)^10)*123^7看起来括号有点多。。。。暂时没想到什么直观的方法表示出来。 这里为了公式简短，我没加mod。加mod其实就是在每个括号里加上取mod。代码也很简短。
public class Solution {
private int powmod(int a, int b, int mod) {
int ans = 1;
for (int i = 0; i < b; i++) {
ans = (ans*a)%mod;
}
return ans;
}
public int superPow(int a, int[] b) {
int ans = 1;
a %= 1337; //开始没加这行,被大数坑了一次
for (int i = 0; i < b.length; i++) {
ans = (powmod(ans,10,1337)*powmod(a, b[i], 1337)) % 1337;
}
return ans;
}
public static void main(String args[]) {
Solution s = new Solution();
int a = 121;
int[] b = {14,4,2,582,2,2,3,6};
int ans = s.superPow(a, b);
System.out.println(ans);
}
}本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2016-08-06，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读