杜教筛模板

杜教筛模板

#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<map>
#define maxn 5000005
#define ll long long
using namespace std;
int T,n,flag[maxn],pri[maxn],tot,mu[maxn],phi[maxn];
ll sm[maxn],sp[maxn];
map<int,ll>s,S;
void init(){
    n=5000000;
    mu[1]=1;phi[1]=1;
    for(int i=2;i<=n;i++){
        if(!flag[i])pri[++tot]=i,mu[i]=-1,phi[i]=i-1;
        for(int j=1;j<=tot&&i*pri[j]<=n;j++){
            flag[i*pri[j]]=1;
            if(i%pri[j]==0){
                mu[i*pri[j]]=0;
                phi[i*pri[j]]=phi[i]*pri[j];
                break;
            }
            mu[i*pri[j]]=-mu[i];
            phi[i*pri[j]]=phi[i]*(pri[j]-1);
        }
    }
    for(int i=1;i<=n;i++)sm[i]+=sm[i-1]+mu[i],sp[i]=sp[i-1]+phi[i];
}
ll gmu(int x){
    if(x<=5000000)return sm[x];
    if(s[x])return s[x];
    ll tmp=0;
    for(ll l=2,r;l<=x;l=r+1){
        r=x/(x/l);
        tmp+=gmu(x/l)*(r-l+1);
    }
    s[x]=1-tmp;return s[x];
}
ll gph(int x){
    if(x<=5000000)return sp[x];
    if(S[x])return S[x];
    ll tmp=0;
    for(ll l=2,r;l<=x;l=r+1){
        r=x/(x/l);
        tmp+=gph(x/l)*(r-l+1);
    }
    S[x]=1LL*x*(1LL*x+1)/2-tmp;return S[x];
}
int main(){
    init();
    cin>>T;
    while(T--){
        scanf("%d",&n);
        printf("%lld %lld
",gph(n),gmu(n)); 
    }
    return 0;
}