杜教筛

Published: July 21, 2020 by Daltao

• Categories:
• algorithm 101

• Tags:

• 杜教筛

杜教筛

假设$f$是积性函数，求解：

$$\sum_{i=1}^nf(i)$$

很显然，你可以利用线性筛（欧拉筛）以$O(n)$的时间复杂度计算${f(1),f(2),\ldots,f(n)}$。之后加总就可以了，总的时间复杂度为$O(n)$。

但是这在$n$特别巨大的情况下，就很难完成，比如$n=10^{12}$。

接下来我们就需要引出杜教筛，它可以以$O(n^{\frac{2}{3}})$的时空复杂度完成计算。

首先我们需要引入一个精心挑选的积性函数g，记$h=f*g$，其中$*$操作表示的是狄里克雷卷积。因此有

$$h(n)=\sum_{d|n}f(d)g(n/d)$$

很显然$h$也是积性函数。我们简单记$S(n)=\sum_{i=1}^nf(i)$。由于

$$\sum_{i=1}^nh(n)\\ =\sum_{i=1}^n\sum_{d|i}f(d)g(n/d)\\ =\sum_{d=1}^ng(d)\sum_{i=1}^{\lfloor n /d\rfloor}f(n/d)\\ =\sum_{d=1}^ng(d)S({\lfloor n /d\rfloor})\\$$

将右式中$g(1)S(n)$提取出来得到：

$$g(1)S(n)=\sum_{i=1}^nh(n)-\sum_{d=2}^ng(d)S({\lfloor n /d\rfloor})$$

如果函数h和g的连续和的计算都能以$O(1)$时间复杂度完成。那么我们可以利用数论分块和打表（利用哈希表）的技巧快速求解。

首先我们要理解$\lfloor \frac{\lfloor \frac{a}{b} \rfloor}{c} \rfloor=\lfloor \frac{a}{bc} \rfloor$。记${S(\lfloor n/i \rfloor)}$为$S(n)$的依赖集合，其中$i=1,2,\ldots,n$。对于任意$j\leq\lfloor{\frac{n}{i}}\rfloor$，由于$\lfloor \frac{\lfloor \frac{n}{i} \rfloor}{j} \rfloor=\lfloor \frac{n}{ij} \rfloor$，因此可知$S(\lfloor{n/i}\rfloor)$的依赖集合是$S(n)$的依赖集合的子集。因此我们只需要从大到小遍历$i$，计算$S(\lfloor{n/i}\rfloor)$值，就可以得到$S(n)$的整个依赖集合。

注意到${\lfloor \frac{n}{1} \rfloor\,\lfloor \frac{n}{2} \rfloor,\ldots,\lfloor \frac{n}{n} \rfloor}$集合的大小为$O(\sqrt{n})$，而计算$S(n)$仅需要利用仅需要利用${S(\lfloor \frac{n}{1} \rfloor)\,S(\lfloor \frac{n}{2} \rfloor),\ldots,S(\lfloor \frac{n}{n} \rfloor)}$中的值的加总。因此可以得出时间复杂度：

$$\sum_{i=1}^{\sqrt{n}}{O(\sqrt{\frac{n}{i}})}=O(\int_1^\sqrt{n}\sqrt{\frac{n}{x}}dx)=O(\sqrt{n}[x^{1/2}]_1^\sqrt{n})=O(n^{\frac{3}{4}})$$

假如我们利用线性筛计算了前B条记录：$S(\lfloor \frac{n}{1} \rfloor)\,S(\lfloor \frac{n}{2} \rfloor),\ldots,S(\lfloor \frac{n}{B} \rfloor)$。那么总的时间复杂度为

$$O(B)+\sum_{i=1}^{n/B}{O(\sqrt{\frac{n}{i}})}=O(B)+O(\int_1^{n/B}\sqrt{\frac{n}{x}}dx)=O(B+\sqrt{n}[x^{1/2}]_1^{n/B})=O(B+\frac{n}{\sqrt{B}})$$

选取$B=n^{2/3}$，可以得到最优的时间复杂度$O(n^{2/3})$。很显然需要的空间复杂度就是一开始通过线性筛打表的部分，也是$O(n^{2/3})$。