root(N,k)

思路

乘方可以使用乘法快速幂，可以看看我在 leetcode 上的题解。

因为可能会溢出 int，那么我们使用 long long

对于root（N，k），根据题意有

同理可得 ，依次类推，

因为最后 ，所以，如果，说明

#include<iostream>

using namespace std;

long long quickpower(long long x, long long y, int k){
    long long ans = 1, temp = x;
    while(y){
        if(y & 1) ans = ans * temp % (k - 1);
        temp = temp * temp % (k - 1);
        y >>= 1;
    }
    return ans ? ans : k - 1;
}

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