$\LARGE{题目描述}$

给定数论函数 $f$ 和正整数 $n$，求 $\sum_{i=1}^nf_i$ 的值。

$\LARGE{解决方法}$

设

$$S(n) = \sum_{i=1}^n f_i$$

找一个合适的数论函数 $g$ ，则

$$\sum_{i = 1}^n (f*g)(i)=\sum_{i=1}^n g(i) \sum_{j=1}^{\lfloor \frac{n}{i} \rfloor}f(j) = \sum_{i=1}^n g(i) S(\lfloor \frac{n}{i} \rfloor)$$

有

$$g(1)S(n) = \sum_{i=1}^n (f*g)(i) - \sum_{i=2}^n g(i) S(\lfloor \frac{n}{i} \rfloor)$$

若能找到一个数论函数 $g$ 满足单点计算复杂度为 $O(1)$ 且卷积计算 $f*g$ 复杂度也是 $O(1)$ ，那么可以用杜教筛快速求出 $S(n)$ 的值。

预处理后总时间复杂度为 $O(n^{\frac{2}{3}})$ 。

$\LARGE{例题}$

计算 $\sum_{i=1}^n \mu(i)$ 和 $\sum_{i=1}^n \varphi(i)$的值。

由于 $\mu * I = \varepsilon$ ，设 $g = I, f*g = \varepsilon$ 。

得到

$$S(n) = 1 - \sum_{i = 2}^n S(\lfloor \frac{n}{i} \rfloor)$$

由于 $\varphi * I = Id$ ，设 $g = I, f*g = Id$ 。

得到

$$S(n) = \frac{n * (n + 1)}{2} - \sum_{i = 2}^n S(\lfloor \frac{n}{i} \rfloor)$$

$\LARGE{实现}$

以 $\mu$ 和 $\varphi$ 的前缀和为例。

加了预处理和记忆化保证时间复杂度。

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

typedef long long LL; 
const int N = 1e6 + 10, maxn = 1e6;
LL phi[N], mu[N];
int p[N], tot;
bool vis[N];
unordered_map<int, LL> Sphi, Smu;

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

LL Get_Sphi(LL n) {
    if (n <= maxn) return phi[n];
    if (Sphi[n]) return Sphi[n];
    LL res = n * (n + 1) / 2;
    for (LL l = 2, r; l <= n; l = r + 1) {
        r = n / (n / l);
        res -= (r - l + 1) * Get_Sphi(n / l);
    }
    return Sphi[n] = res;
}

LL Get_Smu(LL n) {
    if (n <= maxn) return mu[n];
    if (Smu[n]) return Smu[n];
    LL res = 1;
    for (LL l = 2, r; l <= n; l = r + 1) {
        r = n / (n / l);
        res -= (r - l + 1) * Get_Smu(n / l);
    }
    return Smu[n] = res;
}

int main() {
    init();
    int T;
    scanf("%d", &T);
    while (T -- ) {
        LL n;
        scanf("%lld", &n);
        printf("%lld %lld\n", Get_Sphi(n), Get_Smu(n));
    }
    return 0;
}