跳到主要内容

欧拉函数

参考资料​

定义​

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

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

实现​

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。