「算法笔记」杜教筛

杜教筛通过 $\text{Dirichlet}$ 卷积,可以计算积性函数的前缀和。


定义

  • 积性函数:本文的所有函数都是积性函数。
  • 前缀和:函数 $f(x)$ 的前缀和为 $F(x) = \sum_{i = 1} ^ x f(i)$。
  • 卷积:$f \ast g = h$ 表示数论函数 $f, g$ 的 $\text{Dirichlet}$ 卷积。

思路

如果我们需要求一个积性函数 $f(x)$ 的前缀和 $F(x)$,最简单的想法就是直接线性筛出所有的 $f(x)$ 然后求和,这种朴素做法的复杂度为 $\mathcal O(n)$,只能承受 $10 ^ 7$ 级别的数据,一旦数据规模变大就力不从心了。

考虑找到一个积性函数 $g(x)$,设 $f$ 和 $g$ 的 $\text{Dirichlet}$ 卷积为 $h$,即 $f \ast g = h$,并且 $g, h$ 的前缀和可以在非线性复杂度内求出(即 $\mathcal O(1)$ 或 $\mathcal O(\log n)$),我们就可以愉快地推式子啦!注意:对于所有积性函数 $f$ 都有 $f(1) = 1$。

$$ \begin{align*} F(n) & = \sum_{i = 1} ^ n f(i) \\ & = \sum_{i= 1} ^ n \left(h(i) - \sum_{d \mid i, d \ne 1} g(d) \cdot f\left(\frac{i}{d}\right)\right) \\ & = H(n) - \sum_{i = 1} ^ n \sum_{d \mid i, d \ne 1} g(d) \cdot f\left(\frac{i}{d}\right) \\ & = H(n) - \sum_{i = 2} ^ n g(i) \sum_{j = 1} ^ {\left\lfloor\frac{n}{i}\right\rfloor} f(j) \\ & = H(n) - \sum_{i = 2} ^ n g(i) \cdot F\left(\left\lfloor\frac{n}{i}\right\rfloor\right) \\ \end{align*} $$

发现 $H(n)$ 和 $g(i)$ 都可以快速计算,产生了一个子问题 $F\left(\left\lfloor\frac{n}{i}\right\rfloor\right)$,显然可以数论分块解决,可以直接对其递归求解并记忆化。

直接这样做的复杂度为:

$$ T(n) = \sum_{i = 1} ^ {\sqrt n} T(i) + T\left(\left\lfloor\frac{n}{i}\right\rfloor\right) $$

我们考虑预处理前 $p$ 个 $f(x)$ 的值,线性筛预处理的复杂度为 $\mathcal O(p)$,则递归复杂度变为:

$$ T(n) = \sum_{i = 1} ^ {\left\lfloor\frac{n}{p}\right\rfloor} \sqrt{\frac{n}{i}} \approx \int_{0} ^ {\frac{n}{p}} \sqrt{\frac{n}{x}} \mathbb{dx} = \sqrt n \int_{0} ^ {\frac{n}{p}} x ^ {-\frac{1}{2}} \mathbb{dx} = \mathcal O\left(\frac{n}{\sqrt p}\right) $$

发现当 $p = n ^ {\frac{2}{3}}$ 时复杂度最优,为 $\mathcal O\left(n ^ {\frac{2}{3}}\right)$。


问题形式

$\varphi(i)$

$$ f = \varphi, g = 1, h = n $$

$\mu(i)$

$$ f = \mu, g = 1, h = \varepsilon $$

$i \cdot \varphi(i)$

$$ f = \text{ID}\cdot \mu, g = \text{ID}, h = n ^ 2 $$


习题

发表评论