AcWing
875. 快速幂
快速幂。将$a^k$拆分为$a^{2^0+2^1+\cdots}$的形式，相当于将$k$以二进制的形式表示。这样一来，$a^k~mod~p$可以看作：
\[(((a^{2^0}~mod~p)~\cdot~(a^{2^1}~mod~p))~mod~p~\cdot~\cdots~\cdot~(a^{2^N}~mod~p))~mod~p\]注意用long long处理所有可能爆int的地方。
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int n, a, k, p;
int qmi(int a, int k, int p){
int res = 1 % p;
while(k){
if(k & 1) res = (LL)res * a % p;
k >>= 1;
a = (LL)a * a % p;
}
return res;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n;
while(n--){
cin >> a >> k >> p;
cout << qmi(a, k, p) << '\n';
}
return 0;
}