【模板】杜教筛

 1 #include<bits/stdc++.h>
 2 #define ll long long
 3 #define R register
 4 using namespace std;
 5 const int N=6000010;
 6 int p[N],tot,siz,u[N];
 7 ll phi[N];
 8 bool isp[N];
 9 map<int,ll>hphi;
10 map<int,int>hmu;
11 inline void getpre(int lim){
12     u[1]=phi[1]=1;
13     for(R int i=2;i<=lim;i++){
14         if(!isp[i]) p[++tot]=i,u[i]=-1,phi[i]=i-1;
15         for(R int j=1;j<=tot&&(long long)p[j]*i<=lim;j++){
16             isp[i*p[j]]=1;
17             if(i%p[j]) u[i*p[j]]=-u[i],phi[i*p[j]]=phi[i]*(p[j]-1);
18             else{u[i*p[j]]=0,phi[i*p[j]]=phi[i]*p[j];break;}
19         }
20     }
21     for(R int i=2;i<=lim;i++) u[i]+=u[i-1],phi[i]+=phi[i-1];
22     return;
23 }
24 int sum_mu(R int k){
25     if(k<=siz) return u[k];
26     if(hmu[k]) return hmu[k];
27     ll l=2,r;
28     int res=1;
29     while(l<=k){
30         r=k/(k/l);
31         res-=(r-l+1)*sum_mu(k/l);
32         l=r+1;
33     }
34     hmu[k]=res;
35     return res;
36 }
37 ll sum_phi(R int k){
38     if(k<=siz) return phi[k];
39     if(hphi[k]) return hphi[k];
40     ll l=2,r,res=((long long)k+1)*k/2;
41     while(l<=k){
42         r=k/(k/l);
43         res-=(r-l+1)*sum_phi(k/l);
44         l=r+1;
45     }
46     hphi[k]=res;
47     return res;
48 }
49 int main(){
50     int T,n;
51     siz=6000000;
52     getpre(siz);
53     scanf("%d",&T);
54     while(T--){
55         scanf("%d",&n);
56         printf("%lld %d\n",sum_phi(n),sum_mu(n));
57     }
58     return 0;
59 }