Skip to main content

欧拉函数

Summary

欧拉函数 φ(n) 表示不超过 n 且与 n 互质的正整数个数，φ(1)=1，n 为质数时取 n−1。它是积性函数，由质因数分解可得连乘积公式，即 n 乘以每个质因子的 1 减 p 分之一。按此式枚举质因子累乘，单次求值时间复杂度为 O(根号 n)。与之紧密相关的欧拉定理指出：当 a 与 m 互质时，a 的 φ(m) 次方模 m 等于 1；扩展欧拉定理进一步给出 a、m 一般情形下的降幂公式，按 b 与 φ(m) 的大小分三种情况处理 a 的 b 次方取模。

参考资料​

定义​

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

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

φ(n)=n∏p∣n(1−1p)\varphi(n)=n\prod_{p\mid n}\left(1-\frac{1}{p}\right)

实现​

按上式枚举 nn 的质因子并累乘，时间复杂度为 O(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\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。