题解 | 【模板】快速幂Ⅰ ‖ 模小整数

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<ll> to_tb(ll len){
    vector<ll> res(len);
    res[0]=1;res[1]=2;
    for(ll i=2;i<len;i++) res[i]=(res[i-1])*2;
    return res;
}
vector<ll> to_ltb(ll a,ll p){
    vector<ll> res(32);
    res[0]=a;
    for(ll i=1;i<32;i++){
        res[i]=(res[i-1]%p)*(res[i-1]%p);
        res[i]%=p;
    }
    return res;
}
ll to_res(ll a,ll b,ll p,vector<ll> tb){
    a%=p;
    vector<ll> ltb = to_ltb(a,p);
    ll tol = 1;
    while(b>0){
        auto pot = lower_bound(tb.begin(),tb.end(),b);
        ll pos = pot - tb.begin()-1;
        if(pos<31&&tb[pos+1]==b)pos++;
        tol*=ltb[pos];
        tol%=p;
        b-=tb[pos];
    }
    return tol;
}

int main(){
    ll T;
    cin>>T;
    vector<ll> tb = to_tb(31);
    while(T--){
        ll a,b,p;
        cin>>a>>b>>p;
        if(b==0)cout<<1%p<<endl;
        else cout<<to_res(a,b,p,tb)<<endl;
    }
    return 0;
}