超级次方

你的任务是计算 a^b 对 1337 取模，a 是一个正整数，b 是一个非常大的正整数且会以数组形式给出。

示例 1:

输入: a = 2, b = [3]

输出: 8

示例 2:

输入: a = 2, b = [1,0]

输出: 1024

解题思想

这道题需要计算 a^b % c 的值，其中b非常的大，大到只能使用数组来表示。这道题是ACM里面常见的快速幂的解题方式，这其中有一个数学的推论，可以看我代码里附带的那个解释。

总之，这个公式的意思就是，(a*b)%c=(a%c)*(b%c),因此我们可以在每一步计算结果之后都这么处理，防止溢出。

第二个算法部分其实很容易理解，就是可以做类似于二分的分割，比如当b是偶数的时候，我们可以转化为计算a^（b/2)后再平方，而对于基础，则再乘一个a就可以，总之你看代码就知道了

 public class Solution {

     // 判断是否大于0

     public static boolean morethanzero(int[] x){

         for(int i=x.length-1;i>=0;i--){

             if(x[i]>0)

                 return true;

         }

         return false;

     }

     //高精度除法

     public static void div(int[] x,int y){

         int tmp=0;

         for(int i=0;i<x.length;i++){

             x[i] += tmp*10;

             tmp = x[i] % y;

             x[i] = x[i] /y;

         }

     }

     public static int superPow(int a, int[] b) {

         if (morethanzero(b) == false)

             return 1;

         a=a%1337;

         boolean isEven = false;

         if(b[b.length-1] % 2 == 0)

             isEven = true;

         div(b,2);

         int result = superPow(a,b);

         result = result % 1337;

         result*=result;//result由于div分成了两部分，现在把两部分合在一起

         result = result % 1337;

         if(isEven==false){

             result*=a;//奇数的话，再乘以a

             result = result % 1337;

         }

         return result;

     }

 }

巴特西

Leetcode 372.超级次方

超级次方

最新文章

热门文章