杜教筛
杜教筛
假设$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})$。