[bzoj3944]Sum

 1 #include<bits/stdc++.h>
 2 #include<tr1/unordered_map>
 3 using namespace std;
 4 #define ll long long 
 5 #define N 5000005
 6 int t,n,mu[n],vis[n],p[n];
 7 ll cp[n];
 8 tr1::unordered_map<int,ll>@H_503_34@m1;
 9 tr1::unordered_map<int,int>@H_503_34@m2;
10 ll djs_cp(int n){
11     if (n<=N-5)return cp[n];
12     if (m1[n])return m1[n];
13     ll ans=(n+1LL)*n/2;
14     for(int i=2,j;;i=j+1){
15         j=n/(n/i);
16         ans-=djs_cp(n/i)*(j-i+1);
17         if (j==n)return m1[n]=ans;
18     }
19 }
20 int djs_mu(int n){
21     if (n<=N-5)return mu[n];
22     if (m2[n])return m2[n];
23     int ans=1;
24     for(int i=2,j;;i=j+1){
25         j=n/(n/i);
26         ans-=djs_mu(n/i)*(j-i+1);
27         if (j==n)return m2[n]=ans;
28     }
29 }
30 int main(){
31    mu[1]=cp[1]=1;
32    for(int i=2;i<=N-5;i++){
33       if (!vis[i])cp[i]=i+(mu[p[++p[0]]=i]=-1);
34       for(int j=1;(j<=p[0])&&(i*p[j]<=N-5);j++){
35           vis[i*p[j]]=1;
36           if (i%p[j]==0){
37               cp[i*p[j]]=cp[i]*p[j];
38               break;
39           }
40           mu[i*p[j]]=-@H_503_34@mu[i];
41           cp[i*p[j]]=cp[i]*(p[j]-1);
42       }
43    }
44    for(int i=2;i<=N-5;i++){
45        mu[i]+=mu[i-1];
46        cp[i]+=cp[i-1];
47    }
48     scanf("%d",&t);
49     while (t--){
50         scanf("%d",&n);
51         printf("%lld %d\n",djs_cp(n),djs_mu(n));
52     }
53 }