快速幂

求 m^k%p，时间复杂度 O(logk)。

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

#include <iostream>

using namespace std;
typedef long long LL;

LL n,a,b,p,res;


LL smi(int a,int b,int p){
    int x =a,num = 1%p;
    while(b){

        if(b&1)num=num*x%p;
        x= x*x%p;

        b>>=1;
    }

    return num;
}


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

        cin>>a>>b>>p;
        cout<<smi(a,b,p)<<endl;

    }


    return  0;
}