题解

递归

#include <iostream>
#include <cstdio>
#define int long long
using namespace std;
int n, k, p;
int power_mod_p(int n, int k, int p){
	if(k == 1) return n % p;
	if(k % 2) return n % p * power_mod_p(n, k / 2, p) % p * power_mod_p(n, k / 2, p) % p;
	return power_mod_p(n, k / 2, p) % p * power_mod_p(n, k / 2, p) % p;
}
signed main(){
	cin >> n >> k >> p;
	printf("%d^%d mod %d=%d", n, k, p, power_mod_p(n, k, p));

	return 0;
}

时间复杂度：$O(log_2k)$