BigInteger 的快速幂函数modpow（）和算法解决

解题思路:

注意事项:

参考代码:

BigInteger的快速幂函数：

import java.math.BigInteger;
import java.util.*;

public class Main{
   public static void main(String[] args) {
       Scanner sc=new Scanner(System.in);
       BigInteger A=sc.nextBigInteger(),B=sc.nextBigInteger(),P=sc.nextBigInteger();
       System.out.println(A.modPow(B, P));
   }
}

算法解决：

import java.util.*;

public class Main{
   public static void main(String[] args) {
       Scanner sc=new Scanner(System.in);
       long A=sc.nextLong(),B=sc.nextLong(),P=sc.nextLong();
       System.out.println(fast_power(A,B,P));
   }

   //a^10=(a^2)^5=(a^2)*((a^2)^2)^2,即2^10=(2^2)^5=4^5,4^5=4*(4^2)^2
   //(a*b)%c=(a%c)*(b%c)
   public static long fast_power(long a,long b,long c) {
       long ans=1;
       a%=c;
       while(b!=0)
       {
           if(b%2==1)//if(b&1)——偶数的二进制最后一位为0，奇数为0，偶数&1为0，奇数&1为1
               ans=(ans*a)%c;
           a=(a*a)%c;
           b/=2;//b>>=1——一个数均分，相当于将其二进制数向右移一位
       }
       return ans;
   }
}