筛法

数学 算法

---

杜教筛

杜教筛可以低于线性地求一个积性函数的前缀和

考虑Dirichlet 卷积的定义(记$\sum\limits_{i=1}^{n}f(i)=S(n)$)：

$$\begin{array}{l} \sum\limits_{i=1}^n(f*g)(i) &= \sum\limits_{i = 1}^n\sum\limits_{d|i}f(d)g(\frac{i}{d})\\ &=\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{\lfloor\frac{n}{i}\rfloor}g(i)f(j)\\ &=\sum\limits_{i=1}^{n}g(i)\sum\limits_{j=1}^{\lfloor\frac{n}{i}\rfloor}f(j)\\ &=\sum\limits_{i=1}^{n}g(i)S(\lfloor\frac{n}{i}\rfloor)\\ \end{array}$$

我们把这个重要的式子再写一遍:

$$\sum\limits_{i=1}^{n}(f*g)(i)=\sum\limits_{i=1}^{n}g(i)S(\lfloor\frac{n}{i}\rfloor)$$

我们再仔细观察这个式子 我们的目标是得到$S(n)$ 在上式中不难发现 在等式左边的$\sum$中间有一个$f(x)$的前缀和 而我们需要的$S(n)$在$i=1$的时候会出现 我们把要求东西放在等式左边 而其他乱七八糟的东西扔到等式的右边 我们不难得到:

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

推导到了这里 我们已经得到的我们最想看到的东西 我们只需要把$g(1)$除到右边去 就可以算出来$S(n)$ 因此左边我们不需要继续处理了 那么我们继续考虑右半边的式子可以怎么处理

不难发现 右边的$S(\lfloor\frac{n}{i}\rfloor)$可以使用整除分块(在前置芝士的引理2之后)来处理 那么我们可以改写一下右边的式子 变成:

$$g(1)S(n)=\sum\limits_{i=1}^{n}(f*g)(i)-\sum\limits_{i=2}^{n}g(i)S(\lfloor\frac{n}{i}\rfloor)=\sum\limits_{i=1}^{n}(f*g)(i)-\sum\limits_{d|n}S(\frac{n}{d})\sum\limits_{i=d}^{\frac{n}{d}}g(i)$$

上面这个式子 就是我们最终要的式子了 不难发现 我们如果要求出$S(n)$就需要$g(i)$的前缀和,$(f*g)(i)$的前缀和以及$S(\frac{n}{d})$

显然 处理$S(\frac{n}{d})$可以通过递归.事实上,对于较小的数,我们可以使用线性筛来求解

那么剩下的问题就是计算$g(i)$的前缀和以及$(f*g)(i)$的前缀和了

我们江无限递归调用杜教筛的方法作为课后思考题

我们注意到 我们一定要求的是$S(n)$ 而$g(i)$的前缀和以及$(f*g)(i)$的前缀和其实是由我们选择的$g(i)$决定的

所以最简单的方法就是 我们选一个前缀和可以$O(1)$求的函数$g(i)$同时$(f*g)(i)$的前缀和也可以$O(1)$求解的函数不就可以了吗

这样的例子有很多 以下列举一些比较常用的吧:

$$\begin{array}{l} &\mu * 1 = \varepsilon \\ &\mu * id = \varphi \\ &\varphi * 1 = id\\ &id_k*1=\sigma_k \end{array}$$

解释一下上面各个函数:

$$\begin{array}{l} &\mu(n) = \begin{cases} 1 & n = 1\\ 0 & \text{n含有平方因子}\\ (-1)^k & \text{k是n含有的不同质数因子数} \end{cases} \\ &\varphi（n） \text{是小于等于n的数中和n互质是数的个数}\\ &id_k(x) = x^k \\ &\sigma_k(n)\text{是n的因数的p次方之和}\\ &\varepsilon(n)\begin{cases} 1 & n = 1\\ 0 & \text{else}\\ \end{cases}\\ \end{array}$$

在这些函数中 $\varepsilon$的前缀和,$id_k$的前缀和都非常好求 我们经常要使用这些函数的前缀和来进行计算

接下来让我们看一些实际例题吧:

例一

这是一道板子题

题意:

求$\mu(x)$和$\varphi(x)$的前缀和

这个简直不能再板子了 我们只需要用$\mu * 1 = \varepsilon$加上我们之前推出来的这个式子:

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

就有:

$$S_{\mu}(n)=1-\sum\limits_{i=2}^{n}S_{\mu}(\lfloor\frac{n}{i}\rfloor)$$

通过上式我们就可以算出来$\mu$的前缀和了 注意小的$\mu$先用线性筛处理即可 一般我们会用线性筛处理到$n^{\frac{2}{3}}$左右(具体看个人习惯

而对于$\varphi$的前缀和 可以使用$\varphi * 1=id$进行杜教筛 在oiwiki的神秘代码的启发之下 在这里介绍一种更快的写法 即使用$\mu * id = \varphi$这个卷积 代入这个式子:

$$\sum\limits_{i=1}^{n}(f*g)(i)=\sum\limits_{i=1}^{n}g(i)S(\lfloor\frac{n}{i}\rfloor)$$

即:

$$\sum\limits_{i=1}^{n}\varphi(i)=\sum\limits_{i=1}^{n}\mu(i)S_{id}(\lfloor\frac{n}{i}\rfloor)$$

$$\begin{array}{l} 2S_{\varphi}(n) &= \sum\limits_{i=1}^{n}\mu(i)(\lfloor\frac{n}{i}\rfloor+1)\lfloor\frac{n}{i}\rfloor\\ &=\sum\limits_{i=1}^{n}\mu(i)\lfloor\frac{n}{i}\rfloor^2+\sum\limits_{i=1}^{n}\mu(i)\lfloor\frac{n}{i}\rfloor\\ &=\sum\limits_{i=1}^{n}\mu(i)\lfloor\frac{n}{i}\rfloor^2+1 \end{array}$$

利用上式大力整除分块即可

下面放一个这题的参考代码:

#include <bits/stdc++.h>
#define int long long
using namespace std;
int pri[2000005],cur,mu[2000005],sum_mu[2000005];
bool vis[2000005];
map <int,int> mp;
int S_mu(int x)
{
    if (x < 2000005) return sum_mu[x];
    if (mp[x]) return mp[x];
    int ret = 1,tmp;
    for (int i = 2; i <= x; i = tmp + 1)
    {
        tmp = x / (x / i);
        ret -= S_mu(x / i) * (tmp - i + 1);
    }
    return mp[x] = ret;
}
int S_phi(int x)
{
    int ret = 0,tmp;
    for (int i = 1; i <= x; i = tmp + 1)
    {
        tmp = x / (x / i);
        ret += (S_mu(tmp) - S_mu(i - 1)) * (x / i) * (x / i);
    }
    return ((ret - 1) >> 1) + 1;
}
signed main()
{   
    int t;
    scanf("%lld",&t);
    mu[1] = 1;
    for (int i = 2; i < 2000005; i++)
    {
        if (!vis[i])
        {
            pri[++cur] = i;
            mu[i] = -1;
        }
        for (int j = 1; j <= cur && i * pri[j] < 2000005; j++)
        {
            vis[i * pri[j]] = true;
            if (i % pri[j])
            {
                mu[i * pri[j]] = -mu[i];
            }
            else
            {
                mu[i * pri[j]] = 0;
                break;
            }
        }
    }
    for (int i = 1; i < 2000005; i++)
    {
        sum_mu[i] = sum_mu[i - 1] + mu[i];
    }
    while (t--)
    {
        int n;
        scanf("%lld",&n);
        printf("%lld %lld\n",S_phi(n),S_mu(n));
    }
    return 0;
}

读到这里 应该对于杜教筛已经构成了基本的认识了