杜教筛

简单的说是用来求数论函数的前缀和，时间复杂度低于线性时间复杂度

如求：\(S(n)=\sum_{i=1}^nf(i)\)

常规思路，构造类似数论分块的玩意儿\(S(\lfloor\frac ni\rfloor)\)，就这个

先构造函数\(g\)，考虑用迪利克雷卷积先乱搞一下 \[ \begin{align*} \sum_{i=1}^n\sum_{d|n}g(d)f(\frac id)&=\sum_{i=1}g(i)S(\lfloor\frac ni\rfloor)\\ &=\sum_{i=1}^ng(i)\sum_{j=1}^{\lfloor\frac ni\rfloor}f(j)\\ &=\sum_{i=1}^n\sum_{j=1}^{\lfloor\frac ni\rfloor\\}g(i)f(j) \\ \text{令: i * j = d}\\ &=\sum_{d=1}^n\sum_{i|d}^ng(i)f(\frac di)\qquad\text{证毕!!} \\\Leftrightarrow\sum_{i=1}^n(f*g)(i)&=\sum_{i=1}g(i)S(\lfloor\frac ni\rfloor)\\ \end{align*} \] 那么就可以有： \[ g(1)S(n)=\sum(f*g)(i)-\sum_{i=2}^ng(i)S(\lfloor\frac ni\rfloor) \] 嗯嗯，这个就可以数论分块乱搞了

来，看个实例

P4213 【模板】杜教筛（Sum)

求 \[ S_1 = \sum_{i=1}^n\varphi(i)\\ S_2 = \sum_{i=1}^n\mu(i) \] 先来看看第一问：

首先，我们知道\(\mu*1=id\)，这个应该是很好证明的，反正我不会 \[ \sum_{i=1}^n\sum_{d|i}\varphi(d)=\sum_{i=1}^nS_1(\lfloor\frac ni\rfloor)\\ \begin{align*} \therefore S_1&=\sum_{i=1}^n(\varphi*1)(i)-\sum_{i=2}^nS(\lfloor\frac ni\rfloor)\\ &=\sum_{i=1}^ni-\sum_{i=2}^nS(\lfloor\frac ni\rfloor) \end{align*} \] 来，再看看第二问： \[ \sum_{i=1}^n\sum_{d|i}\mu(d)=\sum S_2(\lfloor\frac ni\rfloor)\\ \begin{align*} \therefore S_2&=\sum_{i=1}^n(\mu*1)(i)-\sum_{i=2}^nS(\lfloor\frac ni\rfloor)\\ &=\sum_{i=1}^n\epsilon(i)-\sum_{i=2}^nS(\lfloor\frac ni\rfloor)\\ &=1-\sum_{i=2}^nS(\lfloor\frac ni\rfloor) \end{align*} \]

这个推出来了，问题就变得十分的简单了

但是我们又发现了一个更大的问题：数组开不下

怎么办？

我们发现问题是离散的，并不是连续的

那么我们就可以用\(map\)之类的好工具

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
unordered_map <int, int> Mu;
unordered_map <int, ll> Phi;
const int Maxn = 5e6;
int T, A, B;
int P[Maxn + 10], Cnt;
int mu[Maxn + 10];
ll phi[Maxn + 10];
bool Vis[Maxn + 10];

inline void Init()
{
    mu[1] = phi[1] = 1;
    for (int i = 2; i <= Maxn; ++i)
    {
        if (!Vis[i]) P[++Cnt] = i, mu[i] = -1, phi[i] = i - 1;
        for (int j = 1; j <= Cnt && i * P[j] <= Maxn; ++j)
        {
            Vis[i * P[j]] = 1;
            if (i % P[j]) mu[i * P[j]] = -mu[i], phi[i * P[j]] = phi[i] * phi[P[j]];
            else 
            {
                phi[i * P[j]] = phi[i] * P[j];
                break;
            }
        } 
    }
    for (int i = 1; i <= Maxn; ++i) mu[i] += mu[i - 1], phi[i] += phi[i - 1];
}

inline ll PPhi(int x)
{
    if (x <= Maxn) return phi[x];
    if (Phi[x]) return Phi[x];
    ll Ans = 1ll * x * (x + 1) / 2;
    for (ll l(2), r; l <= x; l = r + 1)
    {
        r = x / (x / l);
        Ans -= (r - l + 1) * PPhi(x / l);
    }
    return Phi[x] = Ans;
}

inline int MMu(int x)
{
    if (x <= Maxn) return mu[x];
    if (Mu[x]) return Mu[x];
    ll Ans(1);
    for (ll l(2), r; l <= x; l = r + 1)
    {
        r = x / (x / l);
        Ans -= (r - l + 1) * MMu(x / l);
    }
    return Mu[x] = Ans;
}

int main()
{
    Init();
    scanf ("%d", &T);
    while (T--)
    {
        scanf ("%d", &A);
        printf ("%lld %d\n", PPhi(A), MMu(A));
    }
    system("pause");
}