洛谷P4213 【模板】杜教筛（Sum）杜教筛

P4213 【模板】杜教筛（Sum）

标签

• 杜教筛

前言

• 杜教筛的模板~
• 前置知识是线性筛，莫比乌斯反演，狄利克雷卷积~如果不会，需要稍微学习一下再来学杜教筛~

简明题意

• 需要求\(\mu\)和\(\phi\)的前缀和，范围在\(2^{31}?1\)，多组询问。

思路

• 杜教筛的模板。首先，杜教筛的核心是下面这个式子：（g函数你可以任意取）
  \[g(1)*S(n)=\sum_{i=1}^n(f*g)(i)-\sum_{i=2}^ng(i)S[\frac ni]\]

  我快乐的来推导一下吧~很简单
  首先我们任意取一个g函数，g和f的狄利克雷卷积的前缀和：
  \[\sum_{i=1}^n(g*f)(i)=\sum_{i=1}^n\sum_{d|i}g(d)f([\frac id])\]
  改为枚举d：
  \[\sum_{d=1}^n\sum_{i=1}^n[d|i]g(d)f([\frac id])\]
  然后\(\sum\limits_{i=1}^n[d|i]\)这个式子可以很容易变换上限，就成了\(\sum\limits_{i=1}^{[\frac nd]}1\)。变了上限之后枚举项i成了原来的\([\frac 1d]\)，所以后面的\(f([\frac id])\)就成了\(f([\frac {i*d}d])=f(i)\)，所以原式就成了：
  \[\sum_{d=1}^n\sum_{i=1}^{[\frac nd]}g(d)S(i)\]
  然后我们呢移项：
  \[\sum_{d=1}^ng(d)\sum_{i=1}^{[\frac nd]}f(i)\]
  很显然啊后面的式子就是f的前缀和，然后就成了：
  \[pre[f*g](n)=\sum_{d=1}^ng(d)S([\frac nd])\]
  然后自行前缀和一下：
  \[\sum_{d=1}^ng(d)S([\frac nd])-\sum_{d=2}^ng(d)S([\frac nd])=S(n)*g(1)\]

• 观察只要求出了\(g\)的前缀和，最后面的式子就分块了。因此对于一个积性函数，我们只要找到一个

1. 容易求前缀和
2. 容易求和原函数的狄利克雷卷积的函数

的函数g，那么就能完成。

• 先看\(\mu\)函数。容易知道\(\mu*I=\epsilon\)，那就令\(g=I\)，那么先把\(g\)用\(I\)代换，再把我们要求的\(\mu\)代换掉\(f\)：
  \[\sum\limits_{i=1}^n(\mu*g)(i)=\sum\limits_{i=1}^n(\mu*I)(i)\]

  \(\mu*I=\epsilon\)是常用的式子。证明：

  • 由狄利克雷卷积\(\mu*I=\sum\limits_{d|n}\mu(d)*I([\frac nd])\)
  • 而\(I(x)=1\)，带入上式，可以知道\(\mu*I=\sum\limits_{d|n}\mu(d)\)
  • 而由莫比乌斯反演（也可以称为莫比乌斯函数性质）可以知道\(\sum\limits_{d|n}\mu(d)=[n==1]=\epsilon\)，代入原式就有:
    \[\mu*I=\epsilon\]

• 然后很容易知道\(\mu*I=\epsilon\),所以原式就成了：
  \[\sum\limits_{i=1}^n\epsilon(i)=[n>=1]\]
• 简直太好求了。把这个带入原式就成了：
  \[S(n)=[n>=1]-\sum_{i=2}^nS[\frac ni]\]

• 现在问题就是求第二个式子\(\sum\limits_{i=2}^ng(i)S[\frac ni]\)，分块一下，简直简单了。

----------------------------------------------分鸽线----------------------------------------------

• 现在求\(\phi\)的前缀和。跟前面差不多很简单鸭。自行推导吧~
  ----------------------------------------------分鸽线----------------------------------------------
• 首先这个是可以记忆化搜索的，然而会T的很惨QAQ
• 优化。虽然杜教筛是低于线性复杂度的，但是有多组询问鸭！多组询问时，线性筛的复杂度反而优于杜教筛(线性筛\(O(n\))预处理，然后\(O(1)\)查询。但杜教筛...)所以，我们可以提前线性筛一下，预处理出能筛出的\(\mu和\phi\)的前缀和，然后杜教筛就能快很多！！！

注意事项

• 提前线性筛大概筛5e6比较合适~

总结

• 这个得熟记常见的狄利克雷卷积，然后找g函数的时候就会很快！这里总结一下常见的狄利克雷卷积：
• \(\mu*I=\epsilon\)
• \(\phi*I=id\)

AC代码

#include<cstdio>
#include<unordered_map>
using namespace std;

const int maxn = 5e6 + 10;

bool no_prime[maxn];
int prime[maxn], mu[maxn], phi[maxn], p_mu[maxn];
long long p_phi[maxn];
int shai(int n)
{
    int cnt = 0;
    mu[1] = phi[1] = 1;

    for (int i = 2; i <= n; i++)
    {
        if (!no_prime[i])
            prime[++cnt] = i, mu[i] = -1, phi[i] = i - 1;

        for (int j = 1; j <= cnt && prime[j] * i <= n; j++)
        {
            no_prime[i * prime[j]] = 1;
            mu[i * prime[j]] = i % prime[j] == 0 ? 0 : -mu[i];
            phi[i * prime[j]] = i % prime[j] == 0 ? phi[i] * prime[j] : phi[i] * (prime[j] - 1);
            if (i % prime[j] == 0) break;
        }
    }

    for (int i = 1; i <= n; i++)
        p_mu[i] = p_mu[i - 1] + mu[i], p_phi[i] = p_phi[i - 1] + phi[i];

    return cnt;
}

unordered_map<int, int> rec_mu;
unordered_map<int, long long> rec_phi;

int pre_mu(int n)
{
    if (n <= maxn - 10) return p_mu[n];
    if (rec_mu[n]) return rec_mu[n];

    int l = 2, r, ans = (n >= 1);
    while (l <= n)
    {
        r = n / (n / l);
        ans -= (r - l + 1) * pre_mu(n / l);
        l = r + 1;
    }
    return rec_mu[n] = ans;
}

long long pre_phi(int n)
{
    if (n <= maxn - 10) return p_phi[n];
    if (rec_phi[n]) return rec_phi[n];

    int l = 2, r;

    long long ans = n % 2 == 0 ? 1ll*n / 2ll * (n + 1) : (n + 1ll) / 2ll * n;
    while (l <= n)
    {
        r = n / (n / l);
        ans -= (r - l + 1) * pre_phi(n / l);
        if (l == 2147483647) break;
        l = r + 1;
    }
    return rec_phi[n] = ans;
}

void solve()
{
    shai(maxn - 10);

    int t;
    scanf("%d", &t);
    while (t--)
    {
        int n;
        scanf("%d", &n);

        printf("%lld %d\n", pre_phi(n), pre_mu(n));
    }
}

int main()
{
    solve();
    return 0;
}

洛谷P4213 【模板】杜教筛（Sum）杜教筛

原文：https://www.cnblogs.com/danzh/p/11302352.html