视力不好 20pts 后八个点MLE

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 3000010, MAXN = 3e6;
int primes[N], cnt;
int smo[N], mo[N];
ll sphi[N], phi[N];
bool f[N];
unordered_map<int, int> mem_mo;
unordered_map<int, ll> mem_phi;

void init(int n) {
    mo[1] = 1, phi[1] = 1, f[1] = 1;
    for (int i = 2; i <= n; i++) {
        if (!f[i]) {
            primes[++cnt] = i;
            phi[i] = i - 1, mo[i] = -1; 
        }

        for (int j = 1, t; j <= cnt && (t = i * primes[j]) <= n; j++) {
            f[t] = 1;
            if (i % primes[j] == 0) 
                mo[t] = 0, phi[t] = phi[i] * primes[j];
            else mo[t] = -mo[i], phi[t] = phi[i] * (primes[j] - 1);
        }
    }
    for (int i = 1; i <= n; i++) 
        smo[i] = smo[i - 1] + mo[i], sphi[i] = sphi[i - 1] + phi[i];
}

int f1(int n) {
    if (n <= MAXN) return smo[n];
    if (mem_mo[n]) return mem_mo[n];
    int res = 1;
    for (int i = 2, j; i <= n; i = j + 1) {
        j = n / (n / i);
        res -= f1(n / i) * (j - i + 1);
    }
    return mem_mo[n] = res;
}

ll f2(int n) {
    if (n <= MAXN) return sphi[n];
    if (mem_phi[n]) return mem_phi[n];
    ll res = (1ll + n) * n / 2ll;
    for (int i = 1, j; i <= n; i = j + 1) {
        j = n / (n / i);
        res -= 1ll * (j - i + 1) * f2(n / i);
    }
    return mem_phi[n] = res;
}

int main() {
    // freopen("test.in", "r", stdin);
    init(MAXN);

    int tt;
    cin >> tt;
    while (tt--) {
        int n;
        cin >> n;
        cout << f2(n) << " " << f1(n) << endl;
    }

    return 0;
}