洛谷P4213 【模板】杜教筛题解

题意：

给定一个正整数，求
$\mathrm{ans}_1=\sum_{i=1}^n\varphi(i) \\[4pt]\mathrm{ans}_2=\sum_{i=1}^n \mu(i)$
输入格式：

本题有多组数据。

输入的第一行为一个整数，表示数据组数 $T$。

接下来 $T$ 行，每行一个整数 $n$，表示一组询问。

输出格式：

对于每组询问，输出一行两个整数，分别代表 $\mathrm{ans}_1$ 和 $\mathrm{ans}_2$。

数据范围：

对于全部的测试点，保证 $1 \leq T \leq 10$，$1 \leq n \lt 2^{31}$。

杜教筛是一种能在非线性时间内求解积性函数的前缀和的算法。

设 $S(n) = \sum_{i=1}^{n} f(i)$ ，其中 $f$ 为积性函数。另设积性函数 $g$ ，考虑他们的狄利克雷卷积的前缀和

$\begin{aligned} \sum_{i = 1}^n (f * g) (i) &=\sum_{i=1}^n \sum_{d\mid i} f(d) \left(\frac{i}{d}\right) \\[6pt]&=\sum_{d=1}^n g(d)\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}f(i) \\[6pt]&=\sum_{d=1}^ng(d)S\left(\left\lfloor\frac{n}{d}\right\rfloor\right) \end{aligned}$

考察 $g(1)S(n)$ ，可知

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

由前面的式子可得

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

于是只要找到一个合适的积性函数 $g$ ，就可以快速计算 $\sum_{i=1}^n(f * g)(i)$ 和 $g$ 的前缀和

这样就可以用数论分块递归地求解（递归 $S$ ）。根据狄利克雷卷积的性质，可知

$\varphi * \mathbf{1}= \rm{id} \\[6pt] \mu * \mathbf{1}= \epsilon$

于是求 $\varphi$ 的前缀和可以设 $f=\varphi,\,g = \mathbf{1}$ ，则 $f * g = \mathrm{id}$ ，其前缀和为 $\frac{n(n+1)}{2}$ 。

同理对于 $\mu$ 的前缀和，可设 $f=\mu,\,g=\mathbf{1}$ ，则 $f*g = \epsilon$ ，其前缀和为 $1$ 。

那么杜教筛的基本流程如下

ll GetSum(int n) // 算 f 前缀和的函数
{
    ll ans = f_g_sum(n); // 算 f * g 的前缀和
    for(ll l = 2, r; l <= n; l = r + 1) // 注意从 2 开始数论分块
    {
        r = (n / (n / l)); 
        ans -= (g_sum(r) - g_sum(l - 1)) * GetSum(n / l); // g_sum 是 g 的前缀和
    } return ans; 
}

这个代码的复杂度是 $\mathcal{O}(n^{\frac{3}{4}})$ 的，并非最优方案，不过我们先来证明一下。

证明设复杂度为 $T(n)$ ，要求出 $S(n)$ 需要求出 $\sqrt{n}$ 个 $S\left(\left\lfloor\frac{n}{i}\right\rfloor\right)$ 的值，那么
$T(n) = \mathcal{O}\left(\sum_{i=1}^{\sqrt{n}} \left(\sqrt{i}+\sqrt{\frac{n}{i}}\right)\right)=\mathcal{O}(n^{\frac{3}{4}})$
$\square$

上面代码的形式使得我们考虑记忆化，并先用线性筛求出前 $m$ 个答案，则

$T(n)=\mathcal{O}\left(\sum_{i=1}^{\left\lfloor\frac{n}{m}\right\rfloor} \sqrt{\frac{n}{i}}\right) =\mathcal{O}\left(\frac{n}{\sqrt{m}}\right)$

当 $m = n^{\frac{2}{3}}$ 时，$T(n)$ 可以取到 $\mathcal{O}(n^{\frac{2}{3}})$ 。并且显然 $m$ 越大跑的越快。

另外可以想到用哈希表来记忆化，注意如果 $x \le m$ 时就不要扔到哈希表里了，直接查数组即可。

时间复杂度 $\mathcal{O}(Tn^{\frac{2}{3}})$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
#define rep(i, a, b) for(int i = (a), i##END = (b); i <= i##END; i++)
#define Rep(i, a, b) for(int i = (a), i##END = (b); i >= i##END; i--)
#define N ((int)(5e6 + 15))

char ck[N]; int pcnt, p[N]; int phi[N], mu[N];
unordered_map<int, int> sum_phi, sum_mu;
void init(const int _ = N - 5)
{
    phi[1] = mu[1] = 1;
    rep(i, 2, _)
    {
        if(!ck[i]) { p[++pcnt] = i; phi[i] = i - 1; mu[i] = -1; }
        for(int j = 1; j <= pcnt && i * p[j] <= _; j++)
        {
            const int pos = i * p[j]; ck[pos] = true;
            if(i % p[j] == 0) { phi[pos] = phi[i] * p[j]; break; }
            else { phi[pos] = phi[i] * phi[p[j]]; mu[pos] = -mu[i]; }
        }
    }
    rep(i, 1, _) { phi[i] += phi[i - 1]; mu[i] += mu[i - 1]; }
}
int get_sum_phi(int n)
{
    if(n <= N - 5) return phi[n];
    if(sum_phi[n]) return sum_phi[n];
    int res = 1ll * n * (n + 1) / 2;
    for(int l = 2, r; l <= n; l = r + 1)
    {
        r = n / (n / l);
        res -= 1ll * (r - l + 1) * get_sum_phi(n / l);
    }
    return sum_phi[n] = res;
}
int get_sum_mu(int n)
{
    if(n <= N - 5) return mu[n];
    if(sum_mu[n]) return sum_mu[n];
    int res = 1ll;
    for(int l = 2, r; l <= n; l = r + 1)
    {
        r = n / (n / l);
        res -= 1ll * (r - l + 1) * get_sum_mu(n / l);
    }
    return sum_mu[n] = res;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int qwq; cin >> qwq; init();
    while(qwq--) { 
        static int x; cin >> x;
        cout << get_sum_phi(x) << ' ' << get_sum_mu(x) << '\n';
    }
    return 0;
}