欧拉函数求法的理解

容斥求欧拉函数证明

以前一直对容斥原理求欧拉函数的求法有些不解，昨晚领悟透彻之后准备记录一下。

首先对于一个正整数 $n$，在 $1-n$ 中与其互质的数满足一个条件：他们没有相同的质因子

因此考虑从 $n$ 中删除这些相同质因子的贡献，针对每个质因子 $p$，在 $1-n$ 中都存在：

$$p,2p,...,\lfloor\frac{n}{p}\rfloor×p$$

这些数字都与 $n$ 有相同的质因子，而且数量为 $\lfloor\frac{n}{p}\rfloor$ 个，所以考虑删除该质数的贡献。

但是又针对另外一个质因子 $q$，在 $1-n$ 中同样存在：

$$q,2q,...,\lfloor\frac{n}{q}\rfloor×q$$

发现如果同时删除 $p$ 和 $q$ 的贡献时，$p*q$ 将会被反复删除，所以应该加回 $\lfloor\frac{n}{pq}\rfloor$ 的贡献。

因此这两个质数同时对欧拉函数的贡献为：

$$n-\frac{n}{p}-\frac{n}{q}+\frac{n}{pq}$$

提取公因式得到：

$$n(\frac{(p-1)(q-1)}{pq})$$

又可得到：

$$n(1-\frac{1}{q})(1-\frac{1}{p})$$

因此根据乘法原理，每个质数 $p$ 都有 $(1-\frac{1}{p})$ 的贡献在 $n$，所以根据乘法原理，得到欧拉函数公式为：

$$n×\prod_{p|n}^{p为质数}(1-\frac{1}{p})$$

需要注意的是，这种求法意为每一个质数只被考虑一次，即使 $n/p>1$。

分解质因子求欧拉函数

可以采用算数基本定理中的不同方法分解质因数来求欧拉函数，复杂度即分解质因数的复杂度。

以经典试除法来举例，复杂度为 $O(\sqrt{N})$。

有两种方法理解该代码，第一种为直接考虑每个质数的贡献然后除去该质数进行分解质因数的步骤，每个质数可以做出 $\frac{n}{p}$ 的贡献，而 $n$ 在计算完贡献之后就会除去 $p$，这样理解的方法不需要考虑 $\frac{1}{pq}$ 的情况。

通式见下：

定义 $S(n,p)=\{x|x为n的质因数且x\leq p\}$

$$\phi(n)=n-\sum_{p\in S(n,n)}\frac{n}{\prod_{k\in S(n,p)}k}$$

第二种方法是直接从容斥原理的式子倒推：

$$n×\prod_{p|n}^{p为质数}(1-\frac{1}{p})$$ $$n×\prod_{p|n}^{p为质数}(\frac{p-1}{p})$$

这两种方法有什么联系呢？只需要考虑每次 $n*(\frac{p-1}{p})$ 实际上等价于 $n-\frac{n}{p}$ 即可轻松转化。

代码实现如下：

long long euler(long long n){
    long long ans=n;
    for(long long i=2;i*i<=n;++i)
        if(n%i==0){
            ans-=ans/i;//对于第二种理解方法应改为ans=ans/i*(i-1)
            while(n%i==0)n/=i;
        }
    return n>1?ans-ans/n:ans;
}

埃筛求欧拉函数

有一种采用埃筛实现的求欧拉函数的方法：

从 $2$ 到 $n$ 枚举质数，然后对于该质数的所有倍数，如果没有被标记过，则标记为自己，接下来再执行 $phi[j]=phi[j]/i*(i-1)$ 的语句。

我们对上述语句的式子展开发现实际上与分解质因子求欧拉函数的式子相同，而我们采用埃筛筛出了质数，这些质数只会出现一次，每个质因数都可以对自己的倍数做出贡献，而这些贡献重叠起来就交集成了最终解。

因此该算法的思想实际上也是分解质因子，不过比刚才的方法更加高效。

int phi[MAXN];
void GetPhi(int n){
    phi[1]=1;
    for(int i=2;i<=n;i++){
        if(!phi[i]){
            for(int j=i;j<=n;j+=i) {
                if(!phi[j])phi[j]=j;
                phi[j]=phi[j]/i*(i-1);
            }
        }
    }         
}

另外还有一种线性求解欧拉函数的方法，在线筛及其应用中提及。