杜教筛模板题
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 const int N=4e6+10; 5 int phi[N],pri[N],np,isp[N],mu[N]; 6 ll sphi[N],smu[N]; 7 unordered_map<int,ll> mpsphi,mpsmu; 8 ll Sphi(int n) { 9 if(n<N)return sphi[n]; 10 if(mpsphi.count(n))return mpsphi[n]; 11 ll& ret=mpsphi[n]; 12 ret=(ll)n*(n+1)/2; 13 for(int l=2,r,k; l<=n; l=r+1) { 14 k=n/l,r=n/k; 15 ret-=Sphi(n/l)*(r-l+1); 16 } 17 return ret; 18 } 19 ll Smu(int n) { 20 if(n<N)return smu[n]; 21 if(mpsmu.count(n))return mpsmu[n]; 22 ll& ret=mpsmu[n]; 23 ret=1; 24 for(int l=2,r,k; l<=n; l=r+1) { 25 k=n/l,r=n/k; 26 ret-=Smu(n/l)*(r-l+1); 27 } 28 return ret; 29 } 30 int main() { 31 for(int i=2; i<N; ++i)isp[i]=1; 32 phi[1]=mu[1]=1; 33 for(int i=2; i<N; ++i) { 34 if(isp[i]) {pri[np++]=i,phi[i]=i-1,mu[i]=-1;} 35 for(int j=0; j<np&&i*pri[j]<N; ++j) { 36 isp[i*pri[j]]=0; 37 if(i%pri[j]==0) { 38 phi[i*pri[j]]=phi[i]*pri[j]; 39 mu[i*pri[j]]=0; 40 break; 41 } 42 phi[i*pri[j]]=phi[i]*(pri[j]-1); 43 mu[i*pri[j]]=-mu[i]; 44 } 45 } 46 for(int i=1; i<N; ++i)sphi[i]=sphi[i-1]+phi[i]; 47 for(int i=1; i<N; ++i)smu[i]=smu[i-1]+mu[i]; 48 int T; 49 for(scanf("%d",&T); T--;) { 50 int n; 51 scanf("%d",&n); 52 printf("%lld %lld ",Sphi(n),Smu(n)); 53 } 54 return 0; 55 }