AcWing 875. 快速幂
原题链接
简单
作者:
yxc我的神
,
2024-03-13 20:03:28
,
所有人可见
,
阅读 5
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~
1.首先题目给出的形式是a^b%p,举个例子:4^5%10
2.将5变成二进制形式:(0101)2,则4^5=4(2^0+2^2)
3.分析qmi代码,当取到b的该位,且该位为1的时候,我们进行进制累加操作,也即a*a
4.当执行到b的第一位1的时候,此时的a为4,然后res=4^0,b向右移一位到达0,a变成4^2
5.当执行到b的第二位0的时候,此时a=4^2,res不操作,b向右移动一位到达1,a变成4^4
6.b执行到最高位,res=4^0*4^4,b不再移位,a=4^8
7.不进行操作
总结:其实我们可以分析得出,其实在b进行移位的时候,a的二进制指数是以2^n提升的,这个难点理解了就没问题
import java.util.Scanner;
public class 快速幂模板 {
public static int qmi(int a,int b,int p)
{
int res = 1;
while(b>0)
{
if((b&1)==1)res = (int)((long)res*a%p);
b=b>>1;
a=(int)((long)a*a%p);
}
return res;
}
public static void main(String args[]) {
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
for(int i=0;i<n;i++)
{
int a = scan.nextInt();
int b = scan.nextInt();
int p = scan.nextInt();
System.out.println(qmi(a,b,p));
}
}
}