欧拉函数

定义

欧拉函数$\varphi(x)$表示不大于$x$的与$x$互质的正整数的数量。特别的，$\varphi(1)=1$。
$$
\begin{align*}
& \varphi(n)=n\frac{\prod_{i=1}^k(p_i-1)}{\prod_{i=1}^kp_i},p_i为n的质因子
\end{align*}
$$

性质

1.

若$p$是质数，则$\varphi(p^n)=p^{n-1}(p-1)$。

$$
\begin{align*}
& 证明:\
& 在不大于p^n的正整数中，不与之互质的只有p的倍数: p,2p,3p,…p^{n-1}\cdot p,共p^{n-1}个\
& ，所以\varphi(x)=p^n-p^{n-1}\
& \
& 证毕.
\end{align*}
$$

2.

若$ a|x $，则$\varphi(ax)=a\varphi(x)$
$$
\begin{align*}
& 证明:\
& 设\varphi(x)个整数分别为d_1,d_2,d_3\cdots d_{\varphi(x)},由于a|x,这些数也和a互质。所以当a>1,\
&则d_1+x,d_2+x,\cdots ,d_{\varphi(x)}+x也小于ax并与之互质。当a>2，同理，d_1+x,\
&d_2+x,\cdots ,d_{\varphi(x)}+x也小于ax并与之互质。一共有a组，所以共有a组，\varphi(ax)=a\varphi(x)\
& 证毕.
\end{align*}
$$

3.

若$a,b$互质，则$\varphi(a)\varphi(b)=\varphi(ab)$

$$
\begin{align*}
& 证明:\
& 设a=p_1\times p_2 \times \cdots p_k,b = p_{k+1} \times p_{k+2}\times\cdots p_{k+m}\
& 带入公式\
& \varphi(a)=a\frac{(p_1-1)(p_2-1)\cdots (p_k-1)}{p_1p_2p_3\cdots p_k}\
& \varphi(b)=b\frac{(p_{k+1}-1)(p_{k+2}-1)\cdots (p_{k+m}-1)}{p_{k+1}p_{k+2}p_{k+3}\cdots p_{k+m}}\
& 两式相乘\
& \varphi(a)\cdot\varphi(b)=ab\frac{(p_1-1)(p_2-1)\cdots(p_{k+m}-1)}{p_1p_2p_3\cdots p_{k+m}}\
& 因为a,b互质，p_{1-k}和p_{k+1,k+m}无相等值，所以上式=\varphi(ab)\
& 证毕.
\end{align*}
$$

代码

既然公式都有了，那代码就很好写了

int phi(int n){
    int res = n;
    for(int i=2;i*i<=n;i++){
        if(n%i==0)(res/=i)*=(i-1);
        while(n%i==0)n/=i;
    }
    if(n>1)(res/=n)*(n-1);
}

复杂度$O(\sqrt n)$

可以用筛法来求

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

复杂度$O(n \log \log n)$

还可以优化

int phi[MAXN],np[MAXN],primes[MAXN],m;
void Init(int n){
    phi[1]=1;
    for(int i=2;i<=n;i++){
        if(!np[i])primes[++m]=i,phi[i]=i-1;//性质一
        for(int j=1;j<=m;j++){
            int p = primes[j];
            if(p*i>n)break;
            np[p*i]=1;
            if(i%p==0)phi[p*i]=phi[i]*p;//性质二
            else phi[p*i]=phi[p]*phi[i];//性质三 
        }
    }
}

这种做法用到了上面的三种性质，复杂度为$O(n)$。