牛客 root（N,k）快速幂、推公式（难题噢）

题

#include<bits/stdc++.h>

using namespace std;

#define ll long long

ll tui(int x, int y, int k){
    ll res = 1, t = x;
    while(y){
        if(y & 1) res = (res * t) % (k - 1);
        t = (t * t) % (k - 1);
        y >>= 1;
    }
    return res ? res : k - 1;
}

int main()
{
    int x, y, k;
    while(cin>>x>>y>>k){
        cout<<tui(x, y, k)<<endl;
    }
    return 0;
}