题解 | 好多次方

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
i64 euler(i64 x){//求p的欧拉函数
    i64 res=x;
    for(i64 i=2;i<=x/i;i++){
        if(x%i==0){
            res=res-res/i;
            while(x%i==0){
                x/=i;
            }
        }
    }
    if(x>1) res=res-res/x;
    return res;
}
i64 qkpow(i64 a,i64 n,i64 mod){//求快速幂
    i64 res=1;
    while(n){
        if(n&1) res=(res%mod*a%mod)%mod;
        a=(a%mod*a%mod)%mod;
        n>>=1;
    }
    return res;
}
int main(){
    const i64 p = 1e9+7;
    i64 p_euler=euler(p);
    int t;cin>>t;
    while(t--){
        i64 a,b,c;cin>>a>>b>>c;
        //a^n mod p = a^(n mod p的欧拉函数 + p的欧拉函数) mod p
        i64 ans=qkpow(a , qkpow(b,c,p_euler)+p_euler ,p);
        cout<<ans<<'\n';
    }
    return 0;
}