题解 | 【模板】快速幂Ⅰ ‖ 模小整数

这一题是快速幂的模板

大概思路就是，如果指数是奇数，那么res=(res*a)%p;

然后就a=(a*a)%p;

b=b/2;

一开始的res就要对p取模，这是为了防止p为1这种情况，当p为1时，任何数取模后都输出0；

要注意这几个地方都要取模，不然答案就可能出错

import java.util.Scanner;
public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		int t=sc.nextInt();
		while(t-->0) {
			long a=sc.nextLong();
			long b=sc.nextLong();
			long p=sc.nextLong();
			System.out.println(f(a,b,p));
			
		}
		
		
	}
	public static long f(long a,long b,long p) {
		long res=1%p;
		a=a%p;
		while(b>0) {
			if(b%2==1) {
				res=(res*a)%p;
				b--;
			}
			a=(a*a)%p;
			b/=2;
		}
		return res;
		
		
	}

}