C++

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

思路：

快速幂 -> 核心思想：反复平方法

$关于 a^bmod\ p:$

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

#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;
}

$code2:$

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long ll;

int qmi(int a, int b, int p) {
    int res = 1;
    while (b) {
        if (b & 1) res = (ll)res * a % p;
        b >>= 1;
        a = (ll)a * a % p;
    }
    return res;
}

int main() {
    int n; cin >> n;

    while (n -- ) {
        int a, b, p; cin >> a >> b >> p;
        cout << qmi(a, b, p) << endl;
    }
    return 0;
}