P4213 【模板】杜教筛（Sum）

#include <bits/stdc++.h>
#include <tr1/unordered_map>
using namespace std;
typedef long long ll;
const int N = 4e6 + 5;

int prime[N], tot;
bool vis[N];
ll phi[N], mu[N];

void init() {
    phi[1] = mu[1] = 1;
    for (int i = 2; i <= N; ++i) {
        if(!vis[i]){
            prime[++tot] = i; phi[i] = i-1; mu[i] = -1;
        }
        for(int j = 1;j <= tot && i*prime[j] <= N; ++j){
            vis[i*prime[j]] = true;
            if (i % prime[j]) {
                phi[i*prime[j]] = phi[i] * (prime[j]-1);
                mu[i*prime[j]] = -mu[i];
            } else {
                phi[i*prime[j]] = phi[i] * prime[j];
                mu[i*prime[j]] = 0; break;
            }
        }
        mu[i] = mu[i] + mu[i-1]; phi[i]= phi[i-1] + phi[i];
    }
}

map<int, ll> mp1; map<int, ll> mp2;
ll calc_phi(int n) {
    if(n <= N) return phi[n];
    if(mp1.count(n)) return mp1[n];
    ll ans = 1LL* n* (n+1) / 2;
    for(int l = 2, r; l <= n; l = r+1){
        r = n / (n / l);
        ans -= (r-l+1) * calc_phi(n/l);
    }
    return mp1[n] = ans;
}

ll calc_mu(int n) {
    if ( n <= N) return mu[n];
    if (mp2.count(n)) return mp2[n];
    ll ans = 1;
    for(int l = 2, r; l <= n;l = r+1){
        r = n / (n / l);
        ans -= (r-l+1) * calc_mu(n/l);
    }
    return mp2[n] = ans;
}

int main() {
    init(); int T; cin >> T;
    while (T--) {
        int n; cin >> n;
        cout << calc_phi(n) << " " << calc_mu(n) << endl;
    }
    return 0;
}