题解 | #求root(N, k)#

#include<iostream>

using namespace std;

long root(long x,long y,int k){
    int result=1;
    while(y!=0){
        if(y%2==1){
            result *= x;
            result %= k;
        }
        x *= x;
        x %=k;
        y/=2;
    }
    return result;
}

int main(){
    int x,y,k;
    while(cin>>x>>y>>k){
        int result=root(x,y,k-1);
        if(result==0){
            result = k-1;
        }
        cout<<result;
    }
    return 0;
}