题目描述
给定n组ai,bi,pi,对于每组数据,求出abii mod pi的值。
输入格式
第一行包含整数n接下来n行,每行包含三个整数ai,bi,pi
输出格式
对于每组数据,输出一个结果,表示abii mod pi的值。
每个结果占一行。
数据范围
1≤n≤100000,
1≤ai,bi,pi≤2∗109
输入样例:
2
3 2 5
4 3 9
输出样例:
4
1
算法1
Java 代码
import java.util.*;
public class Main{
/*这道题重点是要求a^b的值,但是a和b的值都可能会非常大,所以可能会存在指数爆炸的情况
所以才有了快速幂算法对其做优化*/
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
/* 先将 然后a^k=a^(k的二进制)
a^2^0 mod p =a^(2^x1+2^x2+....) x是二进制中为1的位置
a^2^1 mod p =a^2^x1*a^2^x2*..... 这里每一项的值前面都求出来了
...
a^2^logk mod p
都求出来
###########################################################
举个例子 a=4,k=5,p=10; 4^5 mod 10
4^2^0 4^5=4^(101)
4^2^1 =4^(2^0+2^2)
4^2^2 =4^2^0*4^2^2
*/
while(n-->0){
long a=sc.nextInt();
long k=sc.nextInt();
long p=sc.nextInt();
System.out.println(qmi(a,k,p));
}
}
public static long qmi(long a,long k,long p){
long res=1;
while(k!=0){
//当k的最后一位为1的时候,才进行计算
if(k%2==1) res=res*a%p;
//k右移1位
k=k>>1;
a=a*a%p;
}
return res;
}
}