什么是欧拉函数

记欧拉函数为$\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]];//性质一
        }
    }
}

欧拉函数的性质

欧拉函数是一个积性函数，因此我们有若$gcd(p,i/p)=1$，则$\varphi(i)=\varphi(i/p)*\varphi(p)$ （我不会证）
若$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$)) 证毕

欧拉函数学习笔记

什么是欧拉函数

怎么算欧拉函数

欧拉函数的性质