原理
前置知识：积性函数，狄利克雷卷积。
杜教筛可以在亚线性的时间内算出某些函数的前缀和。
假设我们要算出函数 \(f\) 的前缀和，我们要找到函数 \(g\)，记 \(f*g =h\)。
杜教筛的前提是 \(g\) 的前缀和与 \(h\) 的前缀和都可以快速计算，我们可以快速计算 \(f\) 的前缀和。
首先，我们考虑 \(h\) 的前缀和：
\[\begin{aligned} \sum_{i=1}^nh(i) &= \sum_{i=1}^n\sum_{d|i}g(d)f(\frac{i}{d})\\ &= \sum_{d=1}^n\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}g(d)f(\frac{d}{i})\\ &= \sum_{d=1}^ng(d)\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}f(\frac{d}{i})\\ \end{aligned} \]如果记 \(S_f(n)=\sum_{i=1}^nf(i)\)。
所以我们就有：
\[S_h(n)=\sum_{i=1}^ng(i)S_f(\lfloor\frac{n}{i}\rfloor) \]我们关心的是 \(S_f(n)\)，所以移一下项可以得到：
\[g(1)S_f(n) = S_h(n)-\sum_{i=2}^ng(i)S_f(\lfloor\frac{n}{i}\rfloor) \]这是一个关于 \(S_f\) 的递归式，我们可以配合数论分块递归求解。
直接记忆化搜索复杂度为 \(O(n^{\frac{3}{4}})\)，如果预处理出所有 \(\le n^{\frac{2}{3}}\) 的 \(S_f(n)\) 则可以达到 \(O(n^{\frac{2}{3}})\)。
证明要用微积分，不会，咕咕咕咕。
一些常见的：\(\mu * I = \varepsilon\)，\(\varphi * I = id\)。
模板题代码：
#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <cstring>
#include <algorithm>
#include <unordered_map>
using namespace std;
const int N = 2e6;
/*
mu * I = e
phi * I = id
*/
int pr[N + 5] = {0}, cur = 0;
bool p[N + 5] = {false};
long long mu[N + 5] = {0};
long long phi[N + 5] = {0};
void Euler() {//预处理前缀和
memset(p, true, sizeof p);
cur = 0;
p[0] = p[1] = false;
mu[1] = phi[1] = 1;
for (int i = 2; i <= N; i++) {
if (p[i]) {
pr[++cur] = i;
mu[i] = -1;
phi[i] = i - 1;
}
for (int j = 1; j <= cur && pr[j] * i <= N; j++) {
p[pr[j] * i] = false;
if (i % pr[j] == 0) {
mu[pr[j] * i] = 0;
phi[pr[j] * i] = pr[j] * phi[i];
break;
}
else {
mu[pr[j] * i] = mu[pr[j]] * mu[i];
phi[pr[j] * i] = phi[pr[j]] * phi[i];
}
}
}
for (int i = 1; i <= N; i++) {
mu[i] += mu[i - 1];
phi[i] += phi[i - 1];
}
}
unordered_map<int, long long> pfx_mu, pfx_phi;
long long get_pfx_mu(int n) {
if (n <= N)
return mu[n];
if (pfx_mu.count(n))
return pfx_mu[n];
long long ans = 1ll;
long long l = 2ll, r;
while (l <= n) {
r = n / (n / l);
ans -= (r - l + 1) * get_pfx_mu(n / l);
l = r + 1;
}
return pfx_mu[n] = ans;
}
long long get_pfx_phi(int n) {
if (n <= N)
return phi[n];
if (pfx_phi.count(n))
return pfx_phi[n];
long long ans = 1ll * n * (n * 1ll + 1) / 2;
long long l = 2ll, r;
while (l <= n) {
r = n / (n / l);
ans -= (r - l + 1) * get_pfx_phi(n / l);
l = r + 1;
}
return pfx_phi[n] = ans;
}
void slv() {
int n;
cin >> n;
cout << get_pfx_phi(n) << " " << get_pfx_mu(n) << endl;
}
int main() {
Euler();
int T;
cin >> T;
while (T--)
slv();
return 0;
}