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

root(N,k)=root(Nd,k);其中Nd=N%（k-1）

#include<iostream>
using namespace std;
#include<algorithm>
#include<cstring>
#include<string>
const int MAX = 1024;
int root(int x, int y, int k) {
	int res = 1;
	if (k <= 2)return 1;
	while (y != 1) {
		x %= k - 1;
		if (x == 0)return k - 1;
		if (y % 2 == 0) {
			y /= 2;
			x = x * x;
		}
		else {
			res = (res*x) % (k - 1);
			y--;
		}
	}
	
	if (res*x < k) {
		return res * x;
	}
	else {
		return res * x % (k - 1);
	}
}
int main() {
	ios::sync_with_stdio(false);
	int x, y, k;
	while (cin >> x >> y >> k) {
		cout << root(x, y, k) << endl;
	}

	return 0;
}