Skip to main content

欧拉函数

参考资料​

定义​

欧拉函数（Euler's totient function），即 φ(n)\varphi(n)，表示的是小于等于 nn 和 nn 互质的数的个数。

例如 φ(1)=1\varphi(1)=1；当 nn 是质数的时候，显然有 φ(n)=n−1\varphi(n)=n-1。

实现​

ll phi(ll n)
{
	ll res=n;
	for(ll i=2;i*i<=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;
}

欧拉定理​

与欧拉函数紧密相关的一个定理就是欧拉定理。其描述如下：

若 gcd⁡(a,m)=1\gcd(a,m)=1，则 aφ(m)≡1(modm)a^{\varphi(m)}\equiv 1\pmod{m}。

扩展欧拉定理​

当然也有扩展欧拉定理，用于处理一般的 aa 和 mm 的情形。

ab≡{ab mod φ(m)gcd⁡(a,m)=1abgcd⁡(a,m)≠1,b<φ(m)ab mod φ(m)+φ(m)gcd⁡(a,m)≠1,b≥φ(m)(modm)a^b\equiv \begin{cases} a^{b\bmod\varphi(m)} & \gcd(a,m)=1 \\ a^b & \gcd(a,m)\ne 1,b<\varphi(m) \\ a^{b\bmod\varphi(m)+\varphi(m)} & \gcd(a,m)\ne 1,b\ge\varphi(m) \end{cases} \pmod m

例题​

洛谷 P5091 【模板】扩展欧拉定理

给你三个正整数 a,m,ba,m,b，求 ab mod ma^b \bmod m。

Code (1)
#include <bits/stdc++.h>
using namespace std;

using ll=long long;
const int mod=1e9+7;
ll phi(ll n)
{
	ll res=n;
	for(ll i=2;i*i<=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;
}
ll Pow(ll a,ll b,ll mod)
{
	a%=mod;
	ll res=1;
	while(b)
	{
		if(b&1)res=res*a%mod;
		a=a*a%mod;
		b>>=1;
	}
	return res;
}
ll Mod(string s,ll mod)
{
	ll res=0,f=0;
	for(auto c:s)
	{
		res=res*10+(c-'0');
		if(res>=mod)f=1;
		res%=mod;
	}
	return res+mod*f;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	ll a,mod;
	string b;
	cin>>a>>mod>>b;
	cout<<Pow(a,Mod(b,phi(mod)),mod)<<'\n';
	return 0;
}