欧拉函数板子

欧拉函数就是求与n互质的数的个数，作用就是这个，公式就是fin(n)=n*(1-1/p1) *(1-1/p2) *(1-1/p3) *…… *(1-1/pk) ，公式证明就不说了QAQ，需要用容斥原理去证明，代码掌握就好嘤嘤嘤

int x;
        cin>>x;
        int res=x;
        for(int j=2;j<=x/j;j++)
        {
            if(x%j==0)
            {
                res=res/j*(j-1);
                while(x%j==0)
                x/=j;
            }

        }
        if(x>1)
        res=res/x*(x-1);
        cout<<res<<endl;

欧拉函数板子

接下来再来说说另一个板子，上面是根据定义来求的，下面是用线筛顺便全部求出1——>n所有的欧拉函数，这个比较6

代码板子

long long get(long long n)
{
    phi[1]=1;
    long long res=0;
    for(int i=2;i<=n;i++)
    {
        if(!v[i])
        {
            v[i]=i;
            pr[++m]=i;
            phi[i]=i-1;
        }
        for(int j=1;j<=m;j++)
        {
            if(pr[j]>v[i]||pr[j]>n/i)
            break;
            v[pr[j]*i]=pr[j];
            if(i%pr[j]==0)
            {
                phi[pr[j]*i]=phi[i]*pr[j];
                break;
            }
            phi[pr[j]*i]=phi[i]*(pr[j]-1);
        }
    }
    for(int i=1;i<=n;i++)
    cout<<phi[i]<<' ';
    return res;
}

板子完毕QAQ