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

#include <bits/stdc++.h>
using namespace std;
//快速幂模板：求x ^ y
long long QuickPower(long long x, long long y, int n) { 
    long long ans = 1;
    while (y) {
        //判断奇偶性
        if (y % 2) ans = x * ans % n; 
        //取模运算
        x = x * x % n;
        //除2
        y = y / 2;
    }
    return ans;
}

int main() {
    long long 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;
}