G40 杜教筛

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1e7;
int pr,p[N+10];LL mu[N+10],phi[N+10]; bool v[N+10];
void init()
{
    memset(v,0,sizeof(v));
    pr=0;mu[0]=0;mu[1]=1,phi[1]=1;
    for(int i=2;i<=N;i++)
    {
        if(!v[i]) p[++pr]=i,mu[i]=-1,phi[i]=i-1; 
        for(int j=1;j<=pr&&p[j]*i<=N;j++)
        {
            v[i*p[j]]=1;
            if(i%p[j]==0){mu[i*p[j]]=0;phi[i*p[j]]=phi[i]*p[j];break;}
            mu[i*p[j]]=-mu[i];
            phi[i*p[j]]=phi[i]*(p[j]-1);
        }
    }
    for(int i=2;i<=N;i++)mu[i]+=mu[i-1],phi[i]+=phi[i-1]; 
}
map<LL,LL> mpmu;
LL Smu(LL x)  
{
    if(x<=N)return mu[x];
    if(mpmu[x]) return mpmu[x];
    LL res=1; 
    for(LL l=2,r;l<=x;l=r+1)//注意:l=2开始！ 
    {
        r=x/(x/l);
        res-=(r-l+1)*Smu(x/l);  
    }
    return mpmu[x]=res;
}
map<LL,LL> mpphi;
LL Sphi(LL x)  
{
    if(x<=N)return phi[x];
    if(mpphi[x]) return mpphi[x];
    LL res=x*(x+1)/2; 
    for(LL l=2,r;l<=x;l=r+1)//注意:l=2开始！ 
    {
        r=x/(x/l);
        res-=(r-l+1)*Sphi(x/l);  
    }
    return mpphi[x]=res;
}
int main()
{
    init();
    int T;scanf("%d",&T);
    while(T--)
    { 
        LL n;scanf("%lld",&n);
        LL ans1=Smu(n);
        LL ans2=Sphi(n);
        printf("%lld %lld\n",ans2,ans1);
    }
    return 0;
}

G40 杜教筛

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1e7;
int pr,p[N+10];LL mu[N+10],phi[N+10]; bool v[N+10];
void init()
{
    memset(v,0,sizeof(v));
    pr=0;mu[0]=0;mu[1]=1,phi[1]=1;
    for(int i=2;i<=N;i++)
    {
        if(!v[i]) p[++pr]=i,mu[i]=-1,phi[i]=i-1; 
        for(int j=1;j<=pr&&p[j]*i<=N;j++)
        {
            v[i*p[j]]=True;
            if(i%p[j]==0){mu[i*p[j]]=0;phi[i*p[j]]=phi[i]*p[j];break;}
            mu[i*p[j]]=-mu[i];
            phi[i*p[j]]=phi[i]*(p[j]-1);
        }
    }
    for(int i=2;i<=N;i++)mu[i]+=mu[i-1],phi[i]+=phi[i-1]; 
}
map<LL,LL> mpmu;
LL Smu(LL x)  
{
    if(x<=N)return mu[x];
    if(mpmu[x]) return mpmu[x];
    LL res=1; 
    for(LL l=2,r;l<=x;l=r+1)//注意:l=2开始！ 
    {
        r=x/(x/l);
        res-=(r-l+1)*Smu(x/l);  
    }
    return mpmu[x]=res;
}
map<LL,LL> mpphi;
LL Sphi(LL x)  
{
    if(x<=N)return phi[x];
    if(mpphi[x]) return mpphi[x];
    LL res=x*(x+1)/2; 
    for(LL l=2,r;l<=x;l=r+1)//注意:l=2开始！ 
    {
        r=x/(x/l);
        res-=(r-l+1)*Sphi(x/l);  
    }
    return mpphi[x]=res;
}
int main()
{
    init();
    int T;scanf("%d",&T);
    while(T--)
    { 
        LL n;scanf("%lld",&n);
        LL ans1=Smu(n);
        LL ans2=Sphi(n);
        printf("%lld %lld\n",ans2,ans1);
    }
    return 0;
}