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

  

 

  
1
 

　　看起来括号有点多。。。。暂时没想到什么直观的方法表示出来。 这里为了公式简短，我没加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);
    }
}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
 

文章来源: xindoo.blog.csdn.net，作者：xindoo，版权归原作者所有，如需转载，请联系作者。

原文链接：xindoo.blog.csdn.net/article/details/52136859