https://www.cnblogs.com/Mychael/p/8744633.html
#pragma GCC optimize(3, "Ofast", "inline") #include <bits/stdc++.h> #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<int, ll> ansphi; unordered_map<int, ll> 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) << ' '; } return 0; }