思路

乘方可以使用乘法快速幂,可以看看我在 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;
}