洛谷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;
}