题解 | #快速幂#

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StreamTokenizer st = new StreamTokenizer(br);
        st.nextToken();
        int q = (int)st.nval;
        while (q > 0) {
            st.nextToken();
            long a = (long)st.nval;
            st.nextToken();
            long b = (long)st.nval;
            st.nextToken();
            long p = (long)st.nval;
            long base = 1;
            while (b > 0) {
                if (b % 2 == 1) {//将单数提出来单独算 ，以便后面分治
                    base = base * a;
                    base %= p;
                }
                a = a * a % p;
                b /= 2;
            }
            System.out.println(base % p);
            q--;
        }
    }
}