算法1

(暴力/STL) $O(n^2)$

不用说吧……

算法2

(快速幂) $O(n\log n)$

每一次维护$base\times a$，用$b$右移一位。

C++ 代码

#include<bits/stdc++.h>
#define fs(i,x,y,z) for(int i=x;i<=y;i+=z)
#define ll long long
using namespace std;
ll n,a,b,p;
ll ksm(ll x,ll y,ll z){
    ll ans=1,base=x;
    while(y){
        if(y&1)ans*=base,ans%=z;
        base*=base;base%=z;
        y>>=1;
    }
    return ans;
}
int main(){
    cin>>n;
    fs(i,1,n,1){
        cin>>a>>b>>p;
        cout<<ksm(a,b,p)<<endl;
    }
}