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

/*
从题意里推导得到：(怎么推导的我目前也不知道，总之是数学知识)
当N%(k-1)!=0时，root(N,k)=N%(k-1);
当N%(k-1)==0时，root(N,k)=k-1;

*/

#include <iostream>
using namespace std;

//x和answer必须用long long 不然会越界
//不用快速幂就会乘y次x，会超时
int Fastmi(long x,long y,int k)//求N%(k-1)
{
    long long answer=1;
    while(y!=0)
    {
        if(y%2==1)
        {
            answer*=x;
            answer%=(k-1);
        }
        x*=x;
        x%=(k-1);
        y/=2;
    }
    return answer;
}



int main()
{
    int x,y,k;
    while(cin>>x>>y>>k)
    {
        if(Fastmi(x,y,k)==0)cout<<k-1<<endl;
        else cout<<Fastmi(x,y,k)<<endl;
    }
}