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

//土尔逊Torson 编写于2023/05/18
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>

using namespace std;

long long MyPow(long long x, long long y, int k) {//快速幂
	long long answer = 1;             //初始化为 1   

	//因为N<k 即 N <= k-1 时 N' 表示N的K进制表示的各位数字之和
	//又因为 N = a0 + a1k + a2k^2 + ...  N' = a0 + a1 + a2 + ...
	//N-N' = a1(k-1) + a2(k^2-1)... --> (N-N')%(k-1) = 0 
	//(x * y) % k = (x % k) * (y % k) % k
	//同上 因为 N'<K 所以N'= N % (k-1),如果 N%(K-1)==0,说明 N'=k-1

	while (y != 0) {           //不断把y转换为二进制      
		if (y % 2) {           //若当前位为 1，累乘 x 的 2^k 次幂  
			answer *= x;
			answer %= (k - 1); //求后 k-1 位
		}   
		y /= 2;
		x *= x;                //x 不断平方
		                       //2^1 = 2;
		                       //2^2 = 2^1 * 2^1 = 4;
		                       //2^4 = 2^2 * 2^2 = 16;
		                       //...

		x %= (k - 1);          
		                       //例： 9 = 1 + 8
		                       // 23 = 1 + 2 + 4 + 16
		                       //3^29;
		                       //29 = 1 + 4 + 8 + 16;
		                       //29(2) = 11101
		                       //11101 = 2^0 + 2^2 + 2^3 + 2^4
		                       //3^29 = 3^1 * 3^4 * 3^8 * 3^16
	}
	return answer ? answer : k - 1;
}

int main() {
	long long x, y;
	int k;
	while (scanf("%lld%lld%d", &x, &y, &k) != EOF) {
		printf("%lld\n", MyPow(x, y, k));
	}
}
// 64 位输出请用 printf("%lld")