杜教筛

Published: by Creative Commons Licence

  • Tags:

杜教筛

假设$f$是积性函数,求解:

很显然,你可以利用线性筛(欧拉筛)以$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$也是积性函数。我们简单记$S(n)=\sum_{i=1}^nf(i)$。由于

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

如果函数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)}$中的值的加总。因此可以得出时间复杂度:

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

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