杜教筛
Aleph_Drawer
·
·
算法·理论
0 前言
在莫比乌斯反演中我提到了有更快的筛法。
(注:还没写完,写完再发)
那么杜教筛就是这个要说的筛法,时间复杂度是 O(n^{2/3}) 的。而可以求出一个数论函数的前缀和。
甚至不是积性函数也可以做,只要会构造。这在后面再提及。
1 \mu
我们先考虑一个小函数:\mu。
在莫比乌斯反演当中,\mu 是相当关键的一个函数,其前缀和更是关键中的关键,其实我们好像只要用前缀和来着。
首先我们知道
\sum_{i = 1}^n \varepsilon(i) = 1
所以
\sum_{i = 1}^n \sum_{d \mid i} \mu(i) = 1
所以
\sum_{i = 1}^n\sum_{d \mid i} \mu(\dfrac id) = 1
然后套路拆
\begin{aligned}
& \sum_{d = 1}^n \sum_{i= 1}^n [d \mid i] \mu(\dfrac id) = 1 \\
\Rightarrow & \sum_{d =1}^n \sum_{i = 1}^{\lfloor n / d\rfloor} \mu(i) = 1
\end{aligned}
此时令 S(i) 为 \mu(i) 的前缀和。
那么就有
\sum_{d = 1}^n S(\left\lfloor \dfrac nd \right\rfloor) = 1
我们要 S(n),拆开
S(n) = 1 - \sum_{d = 2}^n S(\left\lfloor \dfrac nd \right\rfloor)
然后你就发现这就成了一个递推式的样子。如果你递推去做 S(n),加上整除分块和记忆化,时间复杂度是 O(n^{3/4}) 的,大概说一下。
根据整除分块相关知识,时间复杂度是
T(n) = O(\sqrt n) + O(\sum_{i = 2}^{\sqrt n} T(\left\lfloor \dfrac ni \right\rfloor))
你发现后面那个东西可以进一步去拆,然后后面那个部分其实是可以丢掉的,因为它已经递归了两层了。
所以
T(n) = O(\sqrt n) + O(\sum_{i = 2}^{\sqrt n} \sqrt{\dfrac ni})
后面那个明显比 \sqrt n 大。所以前面那个部分也丢掉。
积分一下
T(n) = O(\int_{0}^{\sqrt{n}} \sqrt{\dfrac ni} \mathrm di)
这个结果是 O(n^{3/4})。
发现有大量的时间都用在了一些比较小的范围计算上面,我们其实可以先用线性筛把它们筛出来的。
这里具体应该有个边界,以下用线性筛,以上就用这个方法。取多少最优呢?
假设这个边界是 k。我们就只需要算 k \sim n 的部分,这里算出这个部分的时间复杂度是 O(\dfrac n{\sqrt k}) 的。
所以总的时间复杂度是 O(k) + O(\dfrac n{\sqrt k})。均值不等式一下发现 k = \dfrac{n}{\sqrt k} 最优,即 k = n^{2/3}。
此时时间复杂度是 O(\sqrt {n \sqrt k}) = O(\sqrt{n \cdot n^{1/3}}) = O(n^{2/3})。
这样我们就得到了一个挺优秀的做法。搜索加记忆化加整除分块即可。
再额外补充一点细节,怎么记忆化?
首先你可以用 map
,但是这样会带 \log。
观察到由于我们只需要记忆化 > n ^ {2/3} 的部分,我们需要的 \left\lfloor n / \left\lfloor \dfrac nd \right\rfloor\right\rfloor 互不相同,而且在 \left\lfloor \dfrac nd \right\rfloor > n^{2/3} 的时候这个值会 < n^{1/3},用这个记忆化即可。
2 其他的数论函数
现在不妨把这个思想扩展到其他的数论函数上面。
先令 S(x) = \sum_{i = 1}^x f(x),其中 f(x) 是我们要的那个数论函数。
我们先按照上面的套路构造一个 S(n) 关于 S(\left\lfloor \dfrac nd \right\rfloor) 的式子。
考虑狄利克雷卷积。先掏出一个函数 g,这个 g 需要满足什么条件下文会提及。
\begin{aligned}
\sum_{i = 1}^n (f * g)(i) &= \sum_{i = 1}^n \sum_{d \mid i} g(d)f(\dfrac id) \\
&= \sum_{d = 1}^n \sum_{i = 1}^n [d \mid i] g(d) f(\dfrac id) \\
&= \sum_{d = 1}^n \sum_{i = 1}^{\lfloor n / d \rfloor} g(d)f(i)\\
&= \sum_{d = 1}^n g(d) S(\left \lfloor \dfrac nd \right \rfloor)
\end{aligned}
好,常规的把 d = 1 搞出来放到一边。
g(1)S(n) = \sum_{i = 1}^n (f * g)(i) - \sum_{d = 2}^n g(d)S(\left \lfloor \dfrac nd \right \rfloor)
那么假设我们能够
- 可以快速计算 \sum_{i = 1}^n (f * g)(i) 的值;
- 可以快速计算 g 的单点值。
那么我们就可以考虑使用杜教筛来解决问题。
不妨令这两个操作的时间复杂度是 O(1) 的,那么总的时间复杂度就是 O(n^{2/3})。
在筛 \mu 的时候,我们使用的 g 是 \mathbf 1。由于 \mu * \mathbf 1 = \varepsilon 就是 1,而 g 的单点也很好算,所以就挺简单。
考虑一个难一点的函数:\varphi。
首先我们知道
\varphi * \mathbf 1 = \mathrm{id}
不妨仍然以 \mathbf 1 作为 g,那么此时
g(1)S(n) = S(n) = \dfrac {n(n+1)}2 - \sum_{d = 2}^n S(\left \lfloor \dfrac nd \right \rfloor)
最后再举一例,求 f(i) = i \cdot \varphi(i) 的前缀和。
此时构造 g = \mathrm{id}。此时
\sum_{i = 1}^n (f * g)(i) = \sum_{i = 1}^n \sum_{d \mid i} \varphi(d) \cdot d \cdot \dfrac id = \sum_{i = 1}^n i \sum_{d \mid i} \varphi(d)
你说得对,但是 \varphi * \mathbf 1 = \mathrm{id}。所以这其实是一个平方和。
需要注意的是,只要你 g 合适,f 积不积性都无所谓的。
其实 \varphi 也可以更快的用一些小技巧,从 \mu 中得来。
我们知道 \varphi = \mu * \mathrm{id}。
\begin{aligned}
\sum_{i = 1}^n \varphi(n) =& \sum_{i = 1}^n \sum_{d \mid i} \mu(d) \cdot \dfrac id \\
=& \sum_{d = 1}^n \mu(d) \sum_{i = 1}^n [d \mid i] \dfrac id \\
=& \sum_{d = 1}^n \mu(d) \sum_{i = 1}^{\lfloor n / d \rfloor} i \\
\end{aligned}
这个东西可以整除分块,时间复杂度 O(\sqrt n),但是缺点是你要先筛 \mu。
观察到对于 h = f * g,有类似的
\sum_{i = 1}^n h(i) = \sum_{d = 1}^n f(d) \sum_{i = 1}^{{\lfloor n / d \rfloor}} g(i)
也可以类似的去算。