1、基本思路

2、代码

#include<iostream>
using namespace std;
typedef long long LL;
 
int qmi(LL a,LL k,LL p)
{
    LL res=1;
    while(k)
    {
        if(k&1==1)
            res=res*a%p;
        k=k>>1;
        a=a*a%p;
    }
    return res;
}
 
 
int main(){
    int n;cin>>n;
    while(n--)
    {
        LL a,k,p;
        cin>>a>>k>>p;
        cout<<qmi(a,k,p)<<endl;
    }
}