rt
做P1226时想出来的玄学做法
AC

#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
#include<math.h>
using namespace std;
#define int long long
#define putchar_unlocked putchar
inline int brand() {
	return (rand() << 15) + rand();
}
inline bool gb(int x, int w) {
	return x & (1 << (w - 1));
}
inline void wb(int& x, int w, bool z) {
	if (z) {
		x = x | (1 << (w - 1));
	}
	else {
		x = x & ~(1 << (w - 1));
	}
}
int _now = 1 << 16;
int _rma = 1 << 16;
char buff[1 << 16];
inline char getch() {
	if (_now == _rma) {
		if (_rma != 1 << 16)return EOF;
		_rma = fread(buff, 1, _rma, stdin);
		_now = 0;
	}
	return buff[_now++];
}
inline void write(int s, bool c = 1) {
	if (!s) {
		if (c)putchar_unlocked('0');
		return;
	}
	write(s / 10, 0);
	putchar_unlocked(s % 10 + '0');
}
inline void swrite(const char* in) {
	while (*in != '\0')putchar_unlocked(*in++);
}
//#define getch() getchar();
inline int read() {
	int out = 0;
	bool sf = 0;
	char get = getch();
	while (get < '0' || get > '9') {
		if (get == '-')sf = 1;
		get = getch();
	}
	while (get >= '0' && get <= '9')out *= 10, out += get - '0', get = getch();
	return sf ? -out : out;
}
int ksm(int a, int b, int mod) {
	int c = 1;
	if (b <= 4) {
		for (int i = 1; i <= b; i++)c *= a, c %= mod;
		return c % mod;
	}
	c = sqrt(b);
	return ksm(ksm(a, c, mod), c, mod) * ksm(a, b - c * c, mod) % mod;
}
signed main() {
	int a = read(), b = read(),c=read();
	cout << a << '^' << b << " mod " << c << "=" << ksm(a, b, c);
	return 0;
}