bzoj 3944 杜教筛

题目中要求phi和miu的前缀和，利用杜教筛可以推出公式。我们令为

那么有公式

类比欧拉函数，我们可以推出莫比乌斯函数的和公式为  （公式证明懒得写了，主要核心是利用Dirichlet卷积的性质 phi * 1 =id, mu * 1 =0(n>1) 然后利用神奇的杜教筛搞一搞 )

因为有一个n=1的特例，所以这里有一个1，我一开始错在这里，总和答案差1........

所以我们可以预处理一波phi和mu的前缀和 然后递归的处理，用map记忆一下就可以了，复杂度为n的三分之二次幂（我不会证明）——by VANE

#include<bits/stdc++.h>

using namespace std;

const int M=5e6;

bool not_prim[M+];

typedef long long ll;

int prim[M>>],prim_tot;

ll mu[M+],phi[M+];

map<int,ll> _phi,_mu;

void pre()

{

    mu[]=;not_prim[]=;

    phi[]=;

    for(int i=;i<=M;++i)

    {

        if(!not_prim[i])

        {

            prim[++prim_tot]=i;

            phi[i]=i-;

            mu[i]=-;

        }

        for(int j=;j<=prim_tot&&prim[j]<=M/i;++j)

        {

            not_prim[prim[j]*i]=;

            if(i%prim[j]==)

            {

                phi[prim[j]*i]=phi[i]*prim[j];

                mu[prim[j]*i]=;

                break;

            }

            phi[prim[j]*i]=phi[i]*phi[prim[j]];

            mu[prim[j]*i]=-mu[i];

        }

    }

    for(int i=;i<=M;++i)

    {

        phi[i]+=phi[i-];

        mu[i]+=mu[i-];

    }

}

ll calcphi(ll n)

{

    if(n<=M) return phi[n];

    map<int,ll>::iterator it;

    if((it=_phi.find(n))!=_phi.end())

    return _phi[n];

    ll i,last;ll res=1ll*n*(n+)/;

    for(i=;i<=n;i=last+)

    {

        last=n/(n/i);

        res-=(last-i+)*calcphi(n/i);

    }

    return _phi[n]=res;

}

ll calcmu(ll n)

{

    if(n<=M) return mu[n];

    map<int,ll>::iterator it;

    if((it=_mu.find(n))!=_mu.end()) return _mu[n];

    ll i,last;ll res=;

    for(i=;i<=n;i=last+)

    {

        last=n/(n/i);

        res-=(last-i+)*calcmu(n/i);

     }

     return _mu[n]=res;

}

int main()

{

    pre();

    int t;

    scanf("%d",&t);

    while(t--)

    {

        ll n;

        scanf("%lld",&n);

        printf("%lld %lld\n",calcphi(n),calcmu(n));

    }

}