题解 | #快速幂#

//当b为偶数时，a^b可以转为a^2的b/2次方。
//当b为奇数时，a^b可以转为a^2的b/2次方，再乘以a。
//(a + b) % p = (a % p + b % p) % p  （1）
//(a - b) % p = (a % p - b % p ) % p （2）
//(a * b) % p = (a % p * b % p) % p  （3）
//a ^ b % p = ((a % p)^b) % p        （4）
#include <bits/stdc++.h>
using namespace std;

// 定义幂模运算函数，计算 a^b % p
long long mod_exp(long long a, long long b, long long p) {
    // 如果指数 b 为 0，则返回 1
    if (b == 0)
        return 1;

    // 递归计算 b/2 次幂，结果对 p 取模
    long long t = mod_exp(a, b / 2, p) % p;

    // 计算平方后对 p 取模，得到 t^2 % p
    t = (t * t) % p;

    // 如果指数 b 为偶数，则直接返回 t
    if (b % 2 == 0)
        return t;
    // 如果指数 b 为奇数，则需要额外乘以 a，并对结果再次对 p 取模
    else
        return (a * t) % p;
}

int main() {
    // 输入询问次数
    long long q;
    cin >> q;

    // 循环处理每个询问
    while (q--) {
        long long a, b, p;
        // 输入底数、指数和模数
        cin >> a >> b >> p;

        // 调用幂模运算函数计算结果，并输出
        cout << mod_exp(a, b, p) % p << endl;
    }
    return 0;
}