AcWing 89. a^b - Java
原题链接
简单
作者:
熊本熊本熊
,
2019-05-16 10:58:28
,
所有人可见
,
阅读 1936
import java.util.Scanner;
public class Main{
public static void main(String[] args){
Main solution = new Main();
Scanner reader = new Scanner(System.in);
int a = reader.nextInt();
int b = reader.nextInt();
int p = reader.nextInt();
int ans = solution.a_power_b(a,b,p);
System.out.println(ans);
}
public int a_power_b(int a, int b, int p){
// 一种基本的方法就是简单的按照a^b的方法累乘,但是这样计算的时间复杂度是O(n)的,如果b很大的话,会超时
// 一种优化方法是,按照b的二进制来累乘,计算出b的二进制表达,然后将其分解为2的幂相加的形式,然后计算出a^(2^n),
// 这样可以将时间复杂度降低到log(N)
// 这里必须使用long类型,不然对于某些比较大的数会溢出
long ans = 1; long k = a;
while (b > 0){
if( (b&1) == 1){
ans *= k;
ans = ans%p;
}
k = k*k;
// 这里没事也来模一下,乘数模几次没问题,最后的结果还是对的,
// 我记得我在哪有一个证明来着,忘了,
k = k%p;
b = b>>1;
}
ans = ans%p;
return (int)ans;
}
}