快速幂

思路

1. 当指数$k$为$0$的时候，返回$1$
2. 当指数$k$为奇数的时候，返回$x \times x^{k-1} \times x^{k-1}$
3. 当指数$k$为偶数的时候，返回$x^{k/2} \times x^{k/2}$

递归

#include <iostream>

using namespace std;
typedef long long LL;
int n,a,b,c;

LL check(int k) {
    if(k == 0) return 1;
    if(k & 1) return check(k - 1) % c * a % c;
    LL x = check(k / 2);
    return (x * x) % c;
}

int main() {
    cin >> n;

    while(n --) {
        cin >> a >> b >> c;
        cout << check(b) << endl;
    }
    return 0;
}

递推

#include <iostream>

using namespace std;
typedef long long LL;
int n,a,b,c;

LL check() {
    LL res = 1;
    while(b) {
        if(b & 1) res = res * a % c;
        a = (LL) a * a % c;
        b >>= 1;
    }
    return res;
}