「OI」欧拉函数 φ(n)

欧拉函数 (Euler’s totient function),即 $\varphi(n)$,表示的是小于等于 $n$ 和 $n$ 互质的数的个数。

欧拉函数

简单计算

考虑欧拉函数的性质,我们可以得出:

  1. $\varphi(1)=1$;
  2. $\varphi(p)=p-1,p\in\mathbb{P}$。

根据上面这两个简单的性质和定义,我们不难推出下面这个性质。

$$\gcd(a,b)=1\Rightarrow \varphi(ab)=\varphi(a)\varphi(b)$$

此外,我们还可以通过容斥原理得到欧拉函数的计算公式。

$$n=\prod p _ i^{c _ i}$$

$$\varphi(n)=n\times\prod (1-\frac{1}{p_i})$$

线性筛求欧拉函数

考虑欧拉函数的三个性质:

  1. $\varphi(p)=p-1,p\in\mathbb{P}$。
  2. $\gcd(a,b)=1\Rightarrow \varphi(ab)=\varphi(a)\varphi(b)$。
  3. $p\in\mathbb{P},p\mid a,\varphi(ap)=\varphi(a)\times p$。

我们就很快能仿照线性筛素数写出下面的代码。

inline void Getphi(reg int n){
    phi[1]=1;
    for(reg int i=2;i<=n;++i){
        if(!vis[i]){
            prime[++cnt]=i;
            phi[i]=i-1;
        }
        for(reg int j=1;j<=cnt&&i*prime[j]<=n;++j){
            vis[i*prime[j]]=true;
            if(i%prime[j]==0){
                phi[i*prime[j]]=phi[i]*prime[j];
                break;
            }
            else
                phi[i*prime[j]]=(prime[j]-1)*phi[i];
        }
    }
    return;
}

欧拉函数的应用

最常见的就是扩展欧拉定理了。

$$a^b\equiv\begin{cases}a^{b\bmod\varphi(p)},&\gcd(a,p)=1\\a^b,&\gcd(a,p)\ne 1,b<\varphi(p)\\a^{b\bmod\varphi(p)+\varphi(p)},&\gcd(a,p)\ne 1,b\ge\varphi(p)\\\end{cases}\pmod p$$

证明很简单,大家可以自己去看看。

欧拉函数与 Dirichlet 卷积

可以看看这篇文章「OI」莫比乌斯反演,里面有一个关键的证明。

参考资料