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

#include <bits/stdc++.h>
using namespace std;
int QuickPower(int x, int y, int n) { //取x^y的n进制的个位数
    int ans = 1;
    while (y) {
        if (y % 2) {
            ans = x * ans ;
            ans = ans % n ;
        }
        y = y / 2;
        x = x % n;
        x = x * x;
    }
    return ans;
}
int main() {
    int x, y, k;
    while(cin >> x >> y >> k){
        if(QuickPower(x,y,k-1)) cout << QuickPower(x,y,k-1) << endl;
        else cout << k-1 << endl;
    }

    return 0;
}