杜教筛

Published: by Creative Commons Licence

  • 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})$。