杜教筛

一种在低于线性时间复杂度内求出某些积性函数前缀和的算法。

设我们要求 $s(n)=\sum_{i=1}^n f(i)$,令 $s_2(n)=\sum_{i=1}^n (f*g)(i)$,展开下去可以得到 $s_2(n)=\sum_{d=1}^ng(d)s(\lfloor\frac nd\rfloor)$。

因为我们有 $g(1)s(n)=\sum_{d=1}^ng(d)s(\lfloor\frac nd\rfloor)-\sum_{d=2}^ng(d)s(\lfloor\frac nd\rfloor)=s_2(n)-\sum_{d=2}^ng(d)s(\lfloor\frac nd\rfloor)$。后半部分整除分块,于是可以发现我们需要可以快速求出 $g$ 的前缀和以及 $f*g$ 的前缀和,这个就要求一些特殊的函数才能用杜教筛来求。

当然,杜教筛也有一个好处,就是可以记忆化下这些位置的值便于后面调用。

杜教筛的复杂度是 $O(n^{\frac34})$,因为整除分块一个根号,递归下去的近似于一个四次根号。

线性筛预处理前 $n^{\frac23}$ 项时可以做到 $O(n^{\frac23})$。

常见的狄利克雷卷积:

$$ \begin{aligned} \varepsilon=\mu*1\\ d=1*1\\ \sigma=\text{id}*1\\ \varphi=\mu*\text{id}\\ \text{id}=\varphi*1\\ \end{aligned} $$

举些简单的例子:

$f=\mu,g=1,f*g=\varepsilon$。

$f=\varphi,g=1,f*g=\text{id}$。

$f=\varphi\ {\color{red}{·}}\ \text{id},g=\text{id},f*g=\text{id}\ {\color{red}{·}}\ \text{id}$。

$n=\prod p_i^{a_i},f(n)=(-1)^{\sum a_i},g=1,(f*g)(n)=[n\text{是完全平方数}]$。

主要瓶颈在于找到合适的 $g$,这个感觉会需要很多练习啊...咕一咕吧先。

最后修改:2021 年 09 月 15 日
如果觉得我的文章对你有用,请随意赞赏