描述
请你计算 �� ��� �ab mod p 的值。
一共有 �q 次询问。
输入描述:
第一行输入一个正整数 �q ,代表询问次数。
接下来每行输入三个正整数 �,�,�a,b,p,代表一次询问。
数据范围:
1≤�≤1051≤q≤105
1≤�,�,�≤1071≤a,b,p≤107
输出描述:
对于每次询问,输出一个整数,代表 �� ��� �ab mod p 的值。
示例1
输入:
2
2 2 6
3 4 10
复制输出:
4
1
import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n=scanner.nextInt();
long a;
long b;
long p;
for(int i=0;i<n;i++)
{
a=scanner.nextInt();
b=scanner.nextInt();
p=scanner.nextInt();
System.out.println(cal(a,b,p));
}
}
public static long cal(long a,long b,long p){
long res=1;
while(b>0){
if(b%2==1){
b--;
res=res*a%p;
}
b/=2;
a=a*a%p;
}
return res;
}
}