P5091 【模板】扩展欧拉定理

题目链接

昨天考试考到了欧拉公式，结果发现自己不会，就来恶补一下。

欧拉公式

• \(a^b \bmod p = a^{b}\) \(b < \varphi(p)\)
• \(a^b \bmod p = a^{b\bmod \varphi(p) + \varphi(p)}\) $b \geq \varphi(p) $

具体证明的话可以看一下 扶咕咕的博客，我也是看他的博客才懂得QWQ。

在预处理的的时候，我们就可以判断一下 \(b\) 的大小，具体的话可以这么来实现

LL get(int p)

{

	bool flag = 0;//flag 表示当前读入的这个数是否大于p

	LL s = 0, w = 1; char ch = getchar();

	while(ch < '0' || ch > '9'){if(ch == '-') w = -1; ch = getchar();}

	while(ch >= '0' && ch <= '9')

	{

		s = s * 10 + ch - '0';

		if(s >= p) flag = 1;s %= p;//如果大于p的话，就把flag变为1，同时在对p取模

		ch = getchar();

	}

	if(flag) s += p;//根据欧拉定理如果指数大于p，则需要再加上一个p

	return s * w;

}

处理一个数的欧拉函数可以在 \(\sqrt n\) 的时间内求出来，根据他的递推公式 \(\displaystyle\varphi(n) = n \prod_{质数p\mid n}(1-{1\over p})\) 求一下就行

代码

LL Euler(LL n)

{

	LL res = n;

	for(int i = 2; i <= sqrt(n); i++)//枚举他的约数

	{

		if(n % i == 0)

		{

			res = res / i * (i-1);//递推公式

			while(n % i == 0) n /= i;//这个质因子除尽

		}

	}

	if(n > 1) res = res / n * (n-1);//最后剩下的质因子可能会大于 n，比如 6 = 2 * 3，这时候再把这个质因子算上就行

	return res;

}

AC代码

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cmath>

using namespace std;

#define LL long long

LL a,m,b,p;

LL get(int p)

{

	bool flag = 0;

	LL s = 0, w = 1; char ch = getchar();

	while(ch < '0' || ch > '9'){if(ch == '-') w = -1; ch = getchar();}

	while(ch >= '0' && ch <= '9')

	{

		s = s * 10 + ch - '0';

		if(s >= p)

		{

			flag = 1;

			s %= p;

		}

		ch = getchar();

	}

	if(flag) s += p;

	return s * w;

}

LL ksm(LL a,LL b,LL p)

{

	LL res = 1;

	for(; b; b >>= 1)

	{

		if(b & 1) res = res * a % p;

		a = a * a % p;

	}

	return res;

}

LL Euler(LL n)

{

	LL res = n;

	for(int i = 2; i <= sqrt(n); i++)

	{

		if(n % i == 0)

		{

			res = res / i * (i-1);

			while(n % i == 0) n /= i;

		}

	}

	if(n > 1) res = res / n * (n-1);

	return res;

}

int main()

{

	scanf("%lld%lld",&a,&m); p = Euler(m); b = get(p);

	printf("%lld\n",ksm(a,b,m) % m);

	return 0;

}