luoguP5091 【模板】扩展欧拉定理

我太弱了

【模板】扩展欧拉定理

本来以为可以秒杀的（毕竟是板子），但遗忘的比我想象的严重，主要是当 $b < \varphi(m)$ 时，不能让 $b = (b \mod \varphi(m)) + \varphi(m)$ 这个特判改了 ${\color{red} \text{三次}}$

#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 20000000 + 5;
int a, m, phi, p;
char b[N];
int qpow(int x, int y)
{
	int res = 1;
	while (y)
	{
		if (y & 1)
			res = (LL)res * x % p;
		x = (LL)x * x % p;
		y >>= 1;
	}
	return res;
}
int main()
{
	scanf("%d%d%s", &a, &m, b + 1);
	phi = p = m;
	for (int i = 2, j; i <= m; ++i)
		if (m % i == 0)
		{
			phi = (LL)phi * (i - 1) / i;
			while (m % i == 0)
				m /= i;
		}
	int n = strlen(b + 1), bb = 0;
	if (n <= 8) //特判
	{
		for (int i = 1; i <= n; ++i)
			bb = bb * 10 + b[i] - '0';
		if (bb >= phi)
			bb = bb % phi + phi;
	}
	else
	{
		for (int i = 1; i <= n; ++i)
			bb = (bb * 10 + b[i] - '0') % phi;
		bb += phi;
	}	
	printf("%d", qpow(a, bb));
	return 0;
}