xindoo is
always here

Leetcode 372. Super Pow

题目链接: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);
    }
}
打赏
未经允许不得转载:XINDOO » Leetcode 372. Super Pow
分享到: 更多 (0)

评论 抢沙发

xindoo

联系我联系我们

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏