C++

$\color{#cc33ff}{— > 算法基础课题解}$

时间复杂度：$O(logk)$

#include<iostream>
#include<algorithm>

using namespace std;

typedef long long ll;

// a ^ k % p
int qmi(int a, int k, int p) {
    int res = 1;
    while (k) {
        if (k & 1) res = (ll) res * a % p; // 判断 k 二进制下的最后一位是否为1
        k >>= 1; // k的二进制右移一位（删除最后一位）
        a = (ll) a * a % p;
    }

    return res;
}

int main() {
    int n;
    scanf("%d", &n);
    while (n --) {
        int a, k, p;
        scanf("%d%d%d", &a, &k, &p);

        printf("%d\n", qmi(a, k, p));
    }

    return 0;
}