欧拉函数

公式：

通项公式：

$$\varphi(x)=x\prod_{i=1}^n(1-\frac{1}{p_{i}})$$

其中p1,p2,p3,…,pn为x的所有质因数，x为不为0的整数

递推式：

$$\varphi(p^k)=(p-1)*p^{k-1}$$

证明：

由容斥原理，先用n减去p1,p2,…,pn的倍数的个数，即

$$n-\frac{n}{p_{1}}-\frac{n}{p_{2}}-\dots-\frac{n}{p_{k}}$$

但此时多减了同时为两之积的数，因此又要加上同为两个质因子的倍数的个数，但此时多减了同时为两之积的数，因此又要加上同为两个质因子的倍数的个数但此时多减了同时为两之积的数，因此又要加上同为两个质因子的倍数的个数，但此时多减了同时为两p之积的数，因此又要加上同为两个质因子的倍数的个数，即

$$\frac{n}{p_{1}p_{2}}+\frac{n}{p_{1}p_{3}}+\dots+\frac{n}{p_{k-1}p_{k}}$$

再加上同为三个质因子的倍数的个数……最终公式化为以下形式

$$\varphi(n)=\sum_{S\subset\{p_{1},p_{2},\dots\\,p_{k}\}}(-1)^{|S|}\frac{n}{\prod_{p_{i\in\\S}}}$$

此式与上式等价

$$n-\frac{n}{p_{1}}-\frac{n}{p_{2}}-\dots-\frac{n}{p_{k}}$$

性质：

1. 积性函数：若m,ｎ为互质，

$$\varphi (mn)=\varphi(m)\varphi(n)$$

1. 当n为奇数时

$$\varphi(2n)=\varphi(n)$$

1. 若n为质数

$$\varphi(n)=n-1$$

代码：

依赖于：

$$\varphi(N)=N*\prod(\frac{1}{p}*(p-1))$$

for(int i=1;i<=n;i++)e[i]=i;
for(int i=2;i<=n;i++){
    if(e[i]==i)//当e[i]为质数
        for(int j=i;j<=n;j+=i){
            e[j]=e[j]/i*(i-1);//使其倍数均对于此数做操作，同时筛掉合数
        }
}

e[i]即为$\varphi(i)$