杜教筛

基础学习

发布日期: 2020-08-27

阅读次数:

前言

杜教筛应该也是属于网课内容的，~~而且很显然的，我没有听~~，为了帮助更好的理解杜教筛(?)，开始了$\lfloor\text{从 1 开始的杜教筛学习}\rceil$

注意，本文章前置知识可能有点长，请耐心看下去

关于杜教筛

其实关于杜教筛，它的使用范围并不广泛，大概只有可能是在一些级别比较高的比赛(省选/省选+) 里，它才会有用武之地。但即使在这样的比赛里，杜教筛也只会有少数极其毒瘤的出题人，会在最后的 $10pts-20pts$ 中，出现 $n<=10^{10}$ 这中数据考验，甚至杜教筛也有替代品——$min25\text{筛},\text{洲阁筛} $ 等筛法(相对来说杜教筛似乎要简单一些)

杜教筛其实本质上不是一种筛法，而是一种思想

一般来说，杜教筛我们在 OI 中的运用局限于优化线筛
但也有极少数情况(毒瘤题)需要运用杜教筛推式子
总的来说，理解杜教筛 $O(n^{\frac{2}{3}})$ 的思想还是很有用的

前置知识

函数

没错，就是数学中的函数
但身为一个OIer ，对于函数，你只需要知道有一个东西叫做数论函数
数论函数并不止一种，但幸运的是，身为一个OIer并不需要知道它具体的分类和定义
你只需要知道，我们在OI数论中运用的各种函数，如 $\mu$，$\varphi$ 等，都是数论函数
当了解数论函数之后，我们还需要知道一类函数，积性函数
同样的，我们平常所惯用的数论函数都是积性函数

积性函数

定义

如果一个已知函数为数论函数，且 $f(1)=1$ 并满足以下条件:
对于任意两个互质的正整数 $p,q$ 都满足 $f(p\cdot q)=f(p)\cdot f(q)$
则该函数为积性函数

特殊的，如果对于任意正整数 $p,q$ 都满足以上条件，则该函数为完全积性函数

常见积性函数

$\mu(x)$ 莫比乌斯函数，详情请见莫比乌斯反演，后文中也会再次提到
$\varphi(x)$ 欧拉函数，表示不大于 $x$ 且与 $x$ 互质的正整数的个数 $\varphi(x)=\sum_{i=1}^x[\gcd(i,x)=1]$
$d(x)$ 约数个数函数，表示 $x$ 的约数个数 $d(x)=\sum_{d|x}1$ 或 $d(x)=\sum_{d=1}^x[d|x]$
$\sigma(x)$ 约数和函数，表示 $x$ 的约数和 $\sigma(x)=\sum_{d|x}d$ 或 $\sigma(x)=\sum_{d=1}^xd\cdot[d|n]$

接下来是一些完全积性函数

$\epsilon(x)$ 元函数，$\epsilon(x)=[n=1]$ ,是不是感觉有点像莫比乌斯函数
$I(x)$ 恒等函数，即 $I(x)=1$
$id(x)$ 单位函数，即 $id(x)=x$

而杜教筛则是筛积性函数前缀和的筛法(?)
积性函数还有一个特别重要的性质，即积性函数卷积性函数仍然积性函数，这个性质可以用来判断是否可以使用杜教筛

狄利克雷卷积(⚝)

基本定义

根据算法名字长度与高深程度成正比的理论(例如：可持久化动态仙人掌问题)，这似乎是一个很高深的东西

~~由于该算法比较高深，所以我们直接就当一个运算符号处理~~，下面是狄利克雷卷积的定义:

两个数论函数 $f$ 和 $g$ 的卷积为 $(f * g)(n)=\sum_{d|n}f(d)\cdot g(\frac{n}{d})$，前面的括号表示将 $f$ 卷 $g$ ，后面的表示范围

狄利克雷卷积还满足这些运算规律:

交换律 $f * g=g * f$
结合律 $(f * g) * h=f * (g * h)$
分配律 $(f+g) * h=f * h+g * h$

显然的，我们在记忆上可以类比为乘法运算法则

与函数的关系

首先是元函数 $\epsilon$ 。所谓元函数指的就是在狄利克雷卷积中充当单位元的作用，即满足 $f∗ϵ=f$
除了元函数以外，我们还有一些常见且重要的函数例如 $\mu$ 和 $\varphi$ ,这些重要函数将在下文单独提出

莫比乌斯函数 $\mu$

在莫比乌斯反演中，我们曾了解过一个与 $\mu$ 有关的性质，即 $\sum_{d|n}\mu(d)=[n=1]$
我们可以将这个性质表示为狄利克雷卷积的形式，即 $\mu * I=\epsilon$ 这在狄利克雷卷积中是一个很常用的恒等式。同样的，我们也可以运用它证明莫比乌斯反演
$$
\begin{align}
&{\large\bf{\text{已知 }}\qquad} F(n)=\sum_{d|n}f(d)\\
&\to\qquad F=f * I\\
&\to\qquad \mu * F=f * I * \mu=f * \epsilon=f\\
&\to\qquad f=F * \mu
\end{align}
$$

因此我们可以得到
$$
f(n)=\sum_{d|n}\mu(d)\cdot F(\frac{n}{d})
$$

也可以得到
$$
f(n)=\sum_{n|d}\mu(\frac{d}{n})\cdot F(d)
$$

欧拉函数 $\varphi$

欧拉函数有一个很著名的性质即 $\sum_{d|n}\varphi(d)=n$
在这里我我们以这个性质作为结论使用，证明欧拉函数与莫比乌斯函数之间的关系
$$
\begin{align}
&{\large\bf{\text{已知 }}\qquad} \sum_{d|n}\varphi(d)=n\\
&\to\qquad \varphi * I=id\\
&\to\qquad \varphi * I * \mu=id * \mu\\
&\to\qquad \varphi=id * \mu
\end{align}
$$
即
$$
\varphi(n)=\sum_{d|n}\mu(d)\cdot\frac{n}{d}
$$
将式子两边同时除以 $n$ ，我们就可以推出
$$
\sum_{d|n}\frac{\mu(d)}{d}=\frac{\varphi(n)}{n}
$$

前置知识讲了那么多，现在终于可以开始杜教筛了

使用方法

虽然已经说过了，但我们还是再来一遍: 杜教筛到底是用来干什么的?

杜教筛是以低于线性的时间复杂度来计算积性函数的前缀和的筛法

即我们需要计算的式子大致可以变成这样: $\sum_{i=1}^nf(i)$ ( $f(i)$ 为积性函数)

理论知识

为了解决以上的问题，我们构造两个积性函数 $g$ 和 $h$ ，令 $h=f*g$
现在我们开始求 $\sum_{i=1}^nh(i)$

记 $S(n)=\sum_{i=1}^nh(i)$
$$
\begin{align}
\sum_{i=1}^nh(i)&=\sum_{i=1}^n\sum_{d|i}g(d)\cdot f(\frac{i}{d})
\\
&=\sum_{d=1}^ng(d)\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}f(i)
\\
&=\sum_{d=1}^ng(d)\cdot S(\lfloor\frac{n}{d}\rfloor)
\end{align}
$$
接下来，我们将左边式子的首项提出来，就可以得到
$$
\begin{align}
&\sum_{i=1}^nh(i)=g(1)S(n)-\sum_{d=2}^ng(d)\cdot S(\lfloor\frac{n}{d}\rfloor)\\
&\to g(1)S(n)=\sum_{i=1}^nh(i)-\sum_{d=2}^ng(d)\cdot S(\lfloor\frac{n}{d}\rfloor)
\end{align}
$$
经过各种大佬的分析，只要 $h(n)$ 的前缀和很好求，那么当我们对后面的式子进行整除分块时，求 $S(n)$ 的复杂度约为 $O(n^{\frac{2}{3}})$

知道杜教筛的大概式子之后，可能会思考如何选取 $h$ 和 $g$

但很遗憾的的是，这个只能靠平时的对于狄利克雷卷积中的各种式子的熟悉，以及观察式子性质的能力

应用

一

求 $S(n)=\sum_{i=1}^n\mu(i)\qquad n<=10^{10}$

根据我们得出的式子 $g(1)S(n)=\sum_{i=1}^nh(i)-\sum_{d=2}^ng(i)\cdot S(\lfloor\frac{n}{d}\rfloor)$ ，我们只需要找出某个函数 $g$ 与 $\mu$ 的卷积容易求
首先，我们知道 $\mu*I=\epsilon$ ，很显然的，单位元的前缀和非常好求，同时 $I$ 非常方便整除分块，我们将上述积性函数带入式子中就可以得到
$$
S(n)=1-\sum_{d=2}^nS(\lfloor\frac{n}{d}\rfloor)
$$
现在，我们已经学会了杜教筛莫比乌斯函数的前缀和1了

二

求 $S(n)=\sum_{i=1}^n\varphi(i)$

根据欧拉函数的性质，我们知道 $\varphi*I=id$ ，单位函数的前缀和我们也可以 $O(1)$ 求出，于是我们带入式子中得到
$$
S(n)=\frac{n(n-1)}{2}-\sum_{d=2}^nS(\lfloor\frac{n}{d}\rfloor)
$$
于是，我们也学会了杜教筛欧拉函数的前缀和了

三

求 $S(n)=\sum_{i=1}^ni\cdot\varphi(i)$

这个式子并不像上面两种式子，能够一眼看出我们需要的两个函数
我们考虑将式子化成狄利克雷卷积的形式 $\sum_{d|n}(d\cdot\varphi(d))\cdot g(\frac{n}{d})=h(n)$
考虑将式子里的 $d$ 化掉，我们将 $g$ 代为单位函数
$$
\begin{align}
h(n)=n\cdot\sum_{d|n}\varphi(d)=n^2
\end{align}
$$
对于 $h(n)$ 的前缀和，很显然我们可以用平方和公式 $O(1)$ 求出，于是答案即为
$$
S(n)=\sum_{i=1}^ni^2-\sum_{d=2}^nd\cdot S(\lfloor\frac{n}{d}\rfloor)
$$
现在，你已经基本掌握杜教筛的套路了

代码实现

筛$\mu$ 函数

ll getphi(int x)
{
    if(x<=maxn-5)return phi[x];
    if(ans_phi.count(x))return ans_phi[x];
    ll ans=(1ll*x*(x+1))/2;
    for(register int r,l=2;l<=x;l=r+1)
    {
        r=x/(x/l);
        ans-=1ll*(r-l+1)*getphi(x/l);
    }
    return ans_phi[x]=ans;
}

筛$\varphi$ 函数

ll getmu(int x)
{
    if(x<=maxn-5)return mu[x];
    if(ans_mu.count(x))return ans_mu[x];
    ll ans=1;
    for(register int r,l=2;l<=x;l=r+1)
    {
        r=x/(x/l);
        ans-=1ll*(r-l+1)*getmu(x/l);
    }
    return ans_mu[x]=ans;
}