总结:
快速幂需要解决两个难点:1.大数的幂运算计算量很大,会耗费很长时间。2.计算的中间过程数很大会超出计算机的运算范围。
难点1:可以通过将幂运算转换为乘法。如果指数是偶数,可以将底数变为aa,指数变为b/2,这样就降低了计算量但值不变。如果指数是奇数,底数底数变为aa,指数变为b/2,同时结果还要再乘以一个a。
难点2:

a*b%p = (a%p)*(b%p)%p

利用上面公式可以先将乘法的因子取模,相乘后再取模,结果不变。这样就可以解决计算过程中数值过大的问题。注意:模运算消耗时间是比较大的。
参考:https://blog.csdn.net/rytyy/article/details/80479050
https://wenku.baidu.com/view/519676395aeef8c75fbfc77da26925c52dc5914a.html

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.nextLine());
        for(int i=0;i<n;i++){
            String line = sc.nextLine();
            String[] str = line.split(" ");
            int a = Integer.parseInt(str[0]);
            int b = Integer.parseInt(str[1]);
            int p = Integer.parseInt(str[2]);
            System.out.println(call(a,b,p));
        }
    }
    public static long call(long a,long b,long p){
        long res = 1;
        while(b>0){
            if(b%2==1){
                res=res*a%p;
            }
            b = b>>1;
            a = a*a%p;        

        }
        return res;

    }
}