快速幂

#include<iostream>
using namespace std;
typedef long long LL;
// 快速幂 快速求出a^k mod p (1 <= a, p, k << 10^9)
// 核心：把k拆成2^0 + 2^1 + 2^2 ...

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

int main(){
    int a, k, p;
    cin >> a >> k >> p;
    cout << qmi(a, k, p) << endl;
    return 0;
}