0
12

# problem

$\sum\limits_{i=1}^n\varphi(i),\sum\limits_{i=1}^n\mu(i)$

# solution

$$\varphi(i)$$和$$\mu(i)$$都是积性函数。

$$\mu$$预处理就直接是$$-h$$了。

RP–

# code

/*
* @Author: wxyww
* @Date:   2019-12-25 20:16:31
* @Last Modified time: 2019-12-25 21:38:39
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<ctime>
#include<cmath>
using namespace std;
typedef long long ll;
const int N = 500010;
ll read() {
ll x = 0,f = 1;char c = getchar();
while(c < '0' || c > '9') {
if(c == '-') f = -1; c = getchar();
}
while(c >= '0' && c <= '9') {
x = x * 10 + c - '0'; c = getchar();
}
return x * f;
}
ll m,n,pri[N],vis[N],js,tot,g[N],h[N],sum[N];
void pre() {
for(int i = 2;i <= 500000;++i) {
if(!vis[i]) pri[++js] = i,sum[js] = sum[js - 1] + i;
for(int j = 1;j <= js && 1ll * pri[j] * i <= 500000;++j) {
vis[pri[j] * i] = 1;
if(i % pri[j] == 0) break;
}
}
}
ll w[N],id1[N],id2[N];
ll Sphi(ll now,ll x) {
if(now <= 1 || pri[x] > now) return 0;

ll k;

if(now <= m) k = id1[now];
else k = id2[n / now];
ll ret = g[k] - h[k] - sum[x - 1] + x - 1;

for(int k = x;k <= tot && pri[k] * pri[k] <= now;++k) {
ll p = pri[k];
for(int e = 1;p * pri[k] <= now;++e,p *= pri[k]) {
ret += (pri[k] - 1) * (p / pri[k]) * Sphi(now / p,k + 1) + p * (pri[k] - 1);
}
}
return ret;
}
ll Smu(ll now,ll x) {
if(now <= 1 || pri[x] > now) return 0;

ll  k;
if(now <= m) k = id1[now];
else k = id2[n / now];

ll ret = -h[k] + x - 1;
for(int k = x;k <= tot && pri[k] * pri[k] <= now;++k) {

ret -= Smu(now / pri[k],k + 1);
}
return ret;
}
void solve() {
m = sqrt(n);
if(!n) return (void)puts("0 0");
tot = 0;
// memset(g,0,sizeof(g));memset(h,0,sizeof(h));

for(ll l = 1,r;l <= n;l = r + 1) {
r = n / (n / l);
w[++tot] = n / l;
if(n / l <= m) id1[n / l] = tot;
else id2[r] = tot;

g[tot] = ((w[tot] + 2) * (w[tot] - 1)) / 2;
h[tot] = w[tot] - 1;

}
// puts("!!");
for(int j = 1;j <= js && pri[j] <= m;++j) {
for(int i = 1;i <= tot && 1ll * pri[j] * pri[j] <= w[i];++i) {
ll tmp = w[i] / pri[j];
int k;
if(tmp <= m) k = id1[tmp];
else k = id2[n / tmp];

g[i] -= pri[j] * (g[k] - sum[j - 1]);
h[i] -= h[k] - j + 1;
}
}

// for(int i = 1;i <= tot;++i) printf("%lld ",h[i]);
// puts("");
// puts("!");
cout<<Sphi(n,1) + 1 <<" "<<Smu(n,1) + 1<<endl;
// puts("!!!");
}
int main() {
int T = read();

pre();

while(T--) {
n = read();solve();
}

return 0;
}



<