欧拉函数

参考资料

• 欧拉函数 - OI Wiki

定义

欧拉函数（Euler's totient function）$\varphi(n)$ 表示不超过 $n$ 且与 $n$ 互质的正整数个数。$\varphi(1)=1$；$n$ 为质数时 $\varphi(n)=n-1$。

它是积性函数。设 $n$ 的质因数分解为 $n=\prod p_i^{k_i}$，则

$$\varphi(n)=n\prod_{p\mid n}\left(1-\frac{1}{p}\right)$$

实现

按上式枚举 $n$ 的质因子并累乘，时间复杂度为 $O(\sqrt n)$。

158 Bcpp

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$，则 $a^{\varphi(m)}\equiv 1\pmod{m}$。

扩展欧拉定理

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

$$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,b$，求 $a^b\bmod m$。