什么是欧拉函数

记欧拉函数为\(\varphi(x)\)表示比\(x\)小且与\(x\)互质的数的个数。

---

怎么算欧拉函数

通项公式:\(\varphi(x)=x*\prod(1-\frac{1}{p_i})\) (\(p_i\)为\(x\)的质因数)

因为欧拉函数是一个积性函数，因此我们可以用欧拉筛(线性筛)在\(O(n)\)的时间内预处理出来：具体证明请见后文

void GetPrime()
{
    memset(IsPrime,1,sizeof IsPrime);
    IsPrime[1]=false;
    phi[1]=1;
    for(int i=2;i<=n;i++)
    {
        if(IsPrime[i]==true)
            prime[++prime_tot]=i,phi[i]=i-1;
        for(int j=1;j<=prime_tot and i*prime[j]<=n;j++)
        {
            IsPrime[i*prime[j]]=false;
            if(i%prime[j]==0)
            {
                phi[i*prime[j]]=phi[i]*prime[j];//性质二
                break;
            }
            phi[i*prime[j]]=phi[i]*phi[prime[j]];//性质一
        }
    }
}

---

欧拉函数的性质

1. 欧拉函数是一个积性函数，因此我们有若\(gcd(p,i/p)=1\)，则\(\varphi(i)=\varphi(i/p)*\varphi(p)\) （我不会证）

2. 若\(gcd(p,i/p)!=1\)，且\(p\)为质数，则\(\varphi(i)=\varphi(i/p)*p\)

   证明：
   因为\(gcd(p,i/p)!=1\)而且\(p\)为质数，所以\(i\)一定由至少两个\(p\)组成。
   所以说\(\varphi(i/p)=\varphi(i)/p\)(因为对累乘没有影响，只对最前面的\(x\)有影响(\(x\)指的是通项式中的\(x\)))
   证毕