题解 | #快速幂#

import java.io.*;

/**
 * @BelongsProject: homework
 * @Author: Ling xi_Li
 * @CreateTime: 2023-11-09 17-41
 * @Description: TODO
 */

public class Main {
    public static void main(String[] args) throws IOException {
        //根据公式 (a1*a2)^b %p = ((a1%p)^b * (a2%p)^b) %p可以进行快速幂计算
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(in.readLine());

        String[] lines = null;
        for (int i = 0; i < n; i++) {
            lines = in.readLine().split(" ");
            long a = Integer.parseInt(lines[0]);
            long b = Integer.parseInt(lines[1]);
            long p = Integer.parseInt(lines[2]);

            long res = 1;
		  //算法例子如：解pow(3, 10) = pow(9, 5) = res*pow(9, 4) = res*pow(81, 2) = res*pow(6561, 1)
		  // =res*a=res*6561
            while (b > 0) {
			  //指数为奇数时候，结果去乘以落单的a,指数-1为偶数
                if (b % 2 == 1) {
                    res *= a;
                    res %= p;
                    b--;
                }
			  //指数为偶数的时候，指数/2，底数平方
                b /= 2;
                a *=  a;
                a %= p;

            }
            out.write(res + "\n");
        }
        in.close();
        out.close();
    }
}