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

#include<iostream>
typedef long long LL;
using namespace std;

int qpow(LL x,LL y,LL k)
{
	if(y == 0) return 1;
	if(y % 2 == 0) {
		LL temp = qpow(x,y / 2,k);
		return temp % (k - 1) * temp;
	}else{
		LL temp = qpow(x, y - 1,k);
		return temp * x % (k - 1);
	}
}

int main(void)
{
	LL x,y,k;
	while(cin >> x >> y >> k)
	{
		LL ans = qpow(x,y,k) % ( k - 1);
		if(ans == 0) cout << k - 1 << endl;
		else cout << ans << endl;
	}
	return 0;
}