杜教筛

2020-08-04 本文已影响0人 dachengquan

杜教筛是对线性筛的优化，用于快速求数论函数前缀和。我们可以使用O(n)的线筛求出一般的数论函数的前缀和，杜教筛可以优化到 $O(n^{\frac 2 3})$ 。
问题：求解 $\sum _{i=1}^n f(i)$ , $f(i)$ 是积性函数。
构造两个积性函数h,g。 $h = g*f$ , $\sum _{i=1}^n h = g*f$ 杜教筛就是推导 $\sum _{i=1}^n h(n)$
$\sum _{i=1}^n h(n) = \sum _{i=1}^n \sum_{d\mid i} g(d)*f(i/d)$
思考这一步，将整个式子展开，把g(d)相同的放在一起。
$=\sum_{d=1}^n g(d) * \sum_{i=1}^{\lfloor \frac n d \rfloor} f(i)$
我们假设 $s(n) = \sum _{i=1}^n f(i)$
$=\sum_{d=1}^n g(d) * s({\lfloor \frac n d \rfloor})$
最后我们得到公式
$\sum _{i=1}^n h(n) =\sum_{d=1}^n g(d) * s({\lfloor \frac n d \rfloor})$
求出 $g(1)s(n)$
$g(1)s(n) = \sum _{i=1}^n h(n) - \sum_{d=2}^n g(d) * s({\lfloor \frac n d \rfloor})$
使用杜教筛的关键是，对g(x)的选取，要求h(x)的前缀和非常好求，递归求解 $s({\lfloor \frac n d \rfloor})$ 。g(d)还能配合 $s({\lfloor \frac n d \rfloor})$ 使用整除分块求和。

杜教筛求莫比乌斯函数前缀和

求 $s(n) = \sum_{i=1}^n \mu(i)$
$g(1)s(n) = \sum _{i=1}^n h(n) - \sum_{d=2}^n g(d) * s({\lfloor \frac n d \rfloor})$
我们要求的就是上面的公式。首先确定g的选择。因为我们做过推导， $\mu*1 = \epsilon$ 。我们知道 $\epsilon$ 的前缀和特别好求，并且 $1$ 能配合整除分块。因此我们让g = 1，带入公式中。
$s(n) = 1 - \sum_{d=2}^n s({\lfloor \frac n d \rfloor})$

杜教筛时间复杂度证明

$s(n) = 1 - \sum_{d=2}^n s({\lfloor \frac n d \rfloor})$ 单独看这个公式感觉时间复杂度特别大，我们根据整除分块的知识知道， $\sum _{\lfloor \frac n d \rfloor} 1 <2*\sqrt n$ 。n最多被分为 $2*\sqrt n$ 个。每个还会再分，其中最大的一个是 ${\lfloor \frac n 2 \rfloor}$ ，我开始一直感觉这个时间复杂度是大于O(n)的，虽然我知道已经求解的s(i)会记忆，但是每次合并的时间就要 $O(\sqrt n)$ 如果被记忆的s，用到的很少，那么很明显时间复杂度会大于 $O(n)$ 。

R(n)是一个集合= $\{{\lfloor n/k\rfloor}\mid 2\leq k \leq n ,k \in \mathbb Z \}$ 。
引理：对于任意正整数 n， $\forall m \in R(n)$ ，有 $R(m)⊆R(n)$ 。
证明：因为 $m\in R(n)$ ,所以设 $m = \lfloor n/a\rfloor$ 。对于 $z\in R(m)$ ,有 $z=\lfloor m/b\rfloor =\lfloor n/(a*b)\rfloor$ ，当 $a，b>1,a\leq n,b\leq n/a$ 的时候有 $a*b\leq n$ 所以 $z\in R(n)$ 。
根据这个引理可知，s(n)无论递归多少次只会被分为 $2*\sqrt n$ 个数。从小到大计算整除分块后的s(i)，每个s(i)分块后的s(j)一定在前面被计算出来了，因此我们只需要花费递归1次合并的代价就可以了。
$\sum _{k=1}^{\lfloor \sqrt n \rfloor} \sqrt k + \sum _{k=1}^{\lfloor \sqrt n \rfloor} \sqrt {\frac n k} = Θ ( \int_0^{\sqrt n}{(\sqrt x + \sqrt {\frac n x}})dx) = Θ(n^{\frac 3 4})$
杜教筛采用预处理的方式优化，使用线筛 $O(n)$ 的时间复杂度预处理出前s项
$S+\sum_{i=1}^{\lfloor n/s \rfloor} \sqrt \frac n k = Θ ( \int_0^{\frac n s}{\sqrt {\frac n x}}dx) = Θ(S + \frac n {\sqrt S} )$
当S取 $n^{\frac 2 3}$ 时，整个算法时间复杂度最小，为 $Θ(n^{\frac 2 3})$

杜教筛

杜教筛求莫比乌斯函数前缀和

杜教筛时间复杂度证明

猜你喜欢

热点阅读