常见的迪利克雷卷积

[varphi * I = id ]

[mu * I = e([n = 1]) ]

[mu * i * varphi = e * varphi ]

[mu * id = varphi ]

杜教筛

比如我们需要求

[S(n) = sum_{i = 1} ^ n f(i) ]

找一个积性函数 (g)

考虑

[sumlimits_{i = 1} ^ n (f * g)(i) ]

[=sum_{i = 1} ^ n sum_{d | i} f(d) g(frac i d) ]

[= sum_{d = 1} ^ n g(d) sum_{i le frac n d} f(i) ]

[= sum_{d = 1} ^ n g(d) S(frac n d) ]

考虑把第一项拿出来

[g(1) s(n) = sum_{d = 1} ^ n g(d) S(frac n d) - sum_{d = 2} ^ ng(d) S(frac n d) ]

[g(1) s(n) = sumlimits_{i = 1} ^ n (f * g)(i) - sum_{d = 2} ^ ng(d) S(frac n d) ]

如果可以快速求得 (sumlimits_{i = 1} ^ n (f * g)(i)) 那就可以整除分块递归求 (sumlimits_{d = 2} ^ n g(d) S(frac n d))

求 (sum varphi(i))
让

[f = varphi, g = I, f * g = id ]

[g(1) = 1 ]

[sum_g(n) = n ]

[sum_{i = 1} ^ n (f * g) (i) = sum_{i = 1} ^ n id(i) = frac {(1 + n) * n} 2 ]

求 (sum mu(i))
让

[f = mu, g = I, f * g = e ]

[g(1) = 1 ]

[sum_g(n) = n ]

[sum_{i = 1} ^ n (f * g)(i) = 1 ]

(code)

#include <bits/stdc++.h>
#include <tr1/unordered_map>
using namespace std :: tr1;
using namespace std;
#define rg register
#define gc getchar
#define rep(i, a, b) for(int i = a; i <= b; ++i)
inline int read(){
    rg char ch = gc();
    rg int x = 0, f = 0;
    while(!isdigit(ch)) f |= (ch == '-'), ch = gc();
    while(isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = gc();
    return f ? -x : x;
}
const int N = 2e6 + 5;
int prime[N], pre[N], cnt;
#define ll unsigned long long
ll mu[N], phi[N];
unordered_map<int, ll> ansm, ansp;
const int mod = 1000013;
// struct Hash_map{
//     int head[mod], nxt[N], id[N], tot;
//     ll val[N * 4];
//     inline ll find(int x){
//         for(int i = head[x % mod]; i; i = nxt[i])
//             if(id[i] == x) return val[i];
//         return 2e18;
//     }
//     inline void add(int x, ll y){
//         for(int i = head[x % mod]; i; i = nxt[i])
//             if(id[i] == x) return;
//         val[++tot] = y;
//         id[tot] = x;
//         nxt[tot] = head[x % mod];
//         head[x % mod] = tot;
//     }
// }ansp, ansm;
inline void ola(){
    mu[1] = 1;
    phi[1] = 1;
    for(int i = 2; i < N; ++i){
        if(!pre[i]){
            pre[i] = i;
            prime[++cnt] = i;
            mu[i] = -1;
            phi[i] = i - 1;
        }
        for(int j = 1; j <= cnt && prime[j] * i < N; ++j){
            pre[prime[j] * i] = prime[j];
            if(prime[j] == pre[i]){
                mu[prime[j] * i] = 0;
                phi[prime[j] * i] = phi[i] * prime[j];
                break;
            }
            mu[prime[j] * i] = mu[i] * -1;
            phi[prime[j] * i] = phi[i] * (prime[j] - 1);
        }
    }
    for(int i = 2; i < N; ++i) mu[i] += mu[i - 1], phi[i] += phi[i - 1];
}
ll get_sum_phi(int n){
    if(n < N) return phi[n];
    if(ansp[n]) return ansp[n];
    // ll to = ansp.find(n);
    if(to != 2e18) return to;
    ll res = (ll) (1 + n) * n >> 1;
    for(ll l = 2, r; l <= n; l = r + 1){
        r = n / (n / l);
        res -= (r - l + 1) * get_sum_phi(n / l);
    }
    // ansp.add(n, res);
    return ansp[n] = res;
}
ll get_sum_mu(int n){
    if(n < N) return mu[n];
    if(ansm[n]) return ansm[n];
    // ll to = ansm.find(n);
    if(to != 2e18) return to;
    ll res = 1;
    for(ll l = 2, r; l <= n; l = r + 1){
        r = n / (n / l);
        res -= (r - l + 1) * get_sum_mu(n / l);
    }
    // ansm.add(n, res);
    return ansm[n] = res;
}
inline void Main(){
    int n = read();
    printf("%lld %lld
", get_sum_phi(n), get_sum_mu(n));
}
signed main(){
    ola();
    int t = read();
    while(t--) Main();
    gc(), gc();
    return 0;
}