题解 P5091 【【模板】欧拉定理】

时间：2023-03-08 22:22:50

欧拉定理：若 \(gcd(a,n)=1\)，\(a^{\varphi(n)}\equiv 1(mod\ n)\)

设 \(1\sim n-1\) 中与 \(n\) 互素的 \(\varphi(n)\) 个数 \(x_1,x_2,...,x_{\varphi(n)}\in M_1\)，那么集合 \(M_1\) 为模 \(n\) 的一个缩系

再设 \(a\cdot x_1,a\cdot x_2,...,a\cdot x_{\varphi(n)}\in M_2\)，由于缩系的性质，集合 \(M_2\) 也为模 \(n\) 的缩系

\[\Longrightarrow a\cdot x_1\cdot a\cdot x_2\cdot ...\cdot a\cdot x_{\varphi(n)}\equiv x_1,x_2,...,x_{\varphi(n)}(mod\ n)
\]

化简得 \(a^{\varphi(n)}\equiv 1(mod\ n)\)

如何求一个数的欧拉函数？让我们先证明另一个定理。

定理：\(\varphi(a)=a\cdot (1-\frac {1}{p_1})\cdot (1-\frac {1}{p_2})\cdot ...\cdot (1-\frac {1}{p_n})\)

  • 当 \(a=p\) 时，即 \(a\) 是素数，\(\varphi(a)=a-1\)

  • 当 \(a=p^k(k>1)\) 时，即 \(a\) 是一个素数幂，先考虑与 \(p^k\) 不互素的数 \(a(1\leq a\leq p^k)\)，\(p^k\) 仅有因子 \(p\)，所以 \(p|a\) 必定成立。所以 \(a\) 的值可以有 \(p,2p,3p,...,p^{k-1}\cdot p\)，显然个数为 \(p^{k-1}\) 个。又知小于等于 \(a\) 的正整数总数为 \(p^k\) 个，所以 \(\varphi(a)=p^k-p^{k-1}=p^k\cdot (1-\frac {1}{p})\)

  • 当 \(a\) 为合数时，可表示为 \(a=p_1^{k_1}\cdot p_2^{k_2}\cdot ...\cdot p_n^{k_n}\)，是多个素数幂的积。由 \(\varphi(nm)=\varphi(n)\cdot \varphi(m)\) 得 $$\varphi(a)=\varphi(p_1^{k_1})\cdot \varphi(p_2^{k_2})\cdot ...\cdot \varphi(p_n{k_n})=p_1{k_1}\cdot (1-\frac{1}{p_1})\cdot p_2^{k_2}\cdot (1-\frac {1}{p_2})\cdot ...\cdot p_n^{k_n}\cdot (1-\frac {1}{p_n})$$ 合并所有 \(p_i^{k_i}\) 等于 \(a\)，证得 \(\varphi(a)=a\cdot (1-\frac {1}{p_1})\cdot (1-\frac {1}{p_2})\cdot ...\cdot (1-\frac {1}{p_n})\)

不少证明 \(\varphi(nm)=\varphi(n)\cdot \varphi(m)\) 都是一句话显然，所以有兴趣的话可以证明上述性质。

然后根据引理，可以在 \(O(\sqrt{n})\) 的时间内求出一个数的欧拉函数，这一般在不能线性筛出 \(\varphi\) 函数时使用。

扩展欧拉定理：

若 \(b<\varphi(m)\)，\(a^b\equiv a^b(mod\ m)\)

若 \(b\geq \varphi(m)\)，\(a^b\equiv a^{b\ mod\ \varphi(m)+\varphi(m)}(mod\ m)\)

\(b\) 的指数部分可以边乘边模，最后对 \(a^b\) 线性求或者快速幂即可

\(Code\ Below:\)

#include <bits/stdc++.h>

#define ll long long

using namespace std;

ll a,m,b;

inline ll read(ll m){

	register ll x=0,f=0;char ch=getchar();

	while(!isdigit(ch)) ch=getchar();

	while(isdigit(ch)){

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

		if(x>=m) f=1;

		x%=m;ch=getchar();

	}

	return x+(f==1?m:0);

}

ll phi(ll n){

	ll ans=n,m=sqrt(n);

	for(ll i=2;i<=m;i++){

		if(n%i==0){

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

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

		}

	}

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

	return ans;

}

ll fast_pow(ll a,ll b,ll p){

	ll ret=1;

	for(;b;b>>=1,a=a*a%p)

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

	return ret;

}

int main()

{

    scanf("%lld%lld",&a,&m);

    b=read(phi(m));

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

    return 0;

}

相关文章