杜教筛

· · 算法·理论

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)

那么假设我们能够

  1. 可以快速计算 \sum_{i = 1}^n (f * g)(i) 的值；
  2. 可以快速计算 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)

也可以类似的去算。