https://www.cnblogs.com/Mychael/p/8744633.html

#pragma GCC optimize(3, "Ofast", "inline")

#include

#define start ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ll long long
//#define int ll
#define ls st<<1
#define rs st<<1|1
using namespace std;
const int maxn = (ll) 5e6 + 5;
const int mod = 1000000007;
const int inf = 0x3f3f3f3f;
int mu[maxn];
ll phi[maxn];
bool vis[maxn];
int v[maxn];

inline void init() {
int cnt = 0;
mu[1] = phi[1] = 1;
for (int i = 2; i < maxn; ++i) {
if (!vis[i]) {
v[++cnt] = i;
mu[i] = -1;
phi[i] = i - 1;
}
for (int t = 1; t <= cnt && i * v[t] < maxn; ++t) {
int j = v[t];
vis[i * j] = true;
if (i % j) {
mu[i * j] = -mu[i];
phi[i * j] = phi[i] * phi[j];
} else {
mu[i * j] = 0;
phi[i * j] = phi[i] * j;
break;
}
}
}
for (int i = 1; i < maxn; ++i) {
mu[i] += mu[i - 1];
phi[i] += phi[i - 1];
}
}

unordered_map ansphi;
unordered_map ansmu;

inline int getmu(int n) {
if (n < maxn)
return mu[n];
if (ansmu[n])
return ansmu[n];
int ans = 1;
for (unsigned int l = 2, r; l <= n; l = r + 1) {
r = n / (n / l);
ans -= (r - l + 1) * getmu(n / l);
}
return ansmu[n] = ans;
}

inline ll getphi(int n) {
if (n < maxn)
return phi[n];
if (ansphi[n])
return ansphi[n];
ll ans = 1ll*n * (n + 1) / 2;
for (unsigned int l = 2, r; l <= n; l = r + 1) {
r = n / (n / l);
ans -= (r - l + 1) * getphi(n / l);
}
return ansphi[n] = ans;
}

signed main() {
start;
init();
int T;
cin >> T;
while (T--) {
int n;
cin >> n;
cout << getphi(n) << ' ' << getmu(n) << '\n';
}
return 0;
}