RainAir
My OI Blog
RainAir
杜教筛学习笔记

介绍

我们在 OI 题目中,不难会遇到给定一个积性函数 $f(x)$,求
$$\sum_{i=1}^N f(x)$$
的题目。虽然对于积性函数我们已经有成熟的线性筛方法来说可以做到 $O(n)$,可是有的出题人就是毒瘤,可是有的题目的数据范围要求给出一个复杂度小于线性的做法,这时候神仙就搞出了杜教筛这一东西。

前置芝士

芝士1:线性筛

首先我们知道,基本上所有的积性函数都可以线性筛。
积性函数的特点:
$$\forall x,y,(x,y) = 1 \Rightarrow f(xy) = f(x)f(y)$$
如果我们想线性筛积性函数,首先这个过程一定是建立在欧拉筛素数上的,然后我们考虑一些性质:
1. 当 $p$ 为质数时,$f(p)$ 的取值
2. 当这个数不是第一次被筛到的时候,取值的特性

我们拿 $\mu$ 举例:
什么你还不知道 $\mu$ 是什么?快去看看莫比乌斯反演吧。
首先发现 $\mu(p) = -1$,$p \in prime$。
然后发现当 $x$ 能不止被一种乘积筛出来的时候,$\mu(x) = 0$。
如果是被最小的质因数筛出的时候,就可以依据积性函数的定义来更新了。
直接放一个线性筛 $\mu$ 和 $\phi$ 的代码吧。

芝士2:常见积性函数

纯粹是列举一下防止后面因为符号不同的问题而看不懂。
$\mu(n)$,莫比乌斯函数。
$\phi(n)$,欧拉函数。
$d(n)$,约数个数,即 $d(n) = \sum_{i=1}^n [i|n]$。
$\sigma(n)$,约数和,即 $\sigma(n) = \sum_{i=1}^n i[i|n]$。
完全积性函数:$\forall x,y \Rightarrow f(xy) = f(x)f(y)$
$I(n)$:常函数 $I(n) = 1$。
$\epsilon(n)$:狄利克雷卷积单位元。
$id(n)$:单位函数 $id(i) = i$。
如果你学过莫比乌斯反演,应该已经掌握了所有的前置芝士了,现在我们进入正题。

杜教筛过程

下文中定义狄利克雷卷积的运算符号为 $ * $
我们现在要对于一个积性函数 $f(x)$,求
$$S(n) = \sum_{i=1}^n f(i)$$
考虑找到一个合适的函数 $g$,使得 $f * g$ 的前缀和易于计算。
我们考虑 $f * g$ 的前缀和,并加以推导,得
\begin{align}
&\sum_{i=1}^n (f * g)(i) \\
&= \sum_{i=1}^n \sum_{d|i} g(i)f(\frac{n}{i}) \\
&= \sum_{d=1}^n g(d) \sum_{i=1}^{\lfloor \frac{n}{d} \rfloor} f(i) \\
&= \sum_{i=1}^n g(i) S(\lfloor \frac{n}{i}\rfloor) \\
&= g(1)S(n) + \sum_{i=2}^n g(i)S(\lfloor \frac{n}{i}\rfloor)
\end{align}
考虑进行一些小的移项,最后可得我们一般使用的杜教筛的式子:
$$g(1)S(n) = \sum_{i=1}^n (f* g)(i) – \sum_{i=2}^n g(i)S(\lfloor \frac{n}{i} \rfloor)$$
如果我们对于 $(f* g)$ 的前缀和有快速求法(e.g. $O(1)$),那么预处理出 $f$ 函数的前 $n^{\frac{2}{3}}$,后面数论分块+递归求解,就可以做到 $O(n^{\frac{2}{3}})$ 的优秀复杂度内求得 $S(n)$。
现在我们来尝试用杜教筛来解决求一些函数的前缀和问题。

BZOJ 3944 Sum

题目链接
题目要让你求 $\sum_{i=1}^n \mu(i)$ 和 $\sum_{i=1}^n \phi(i)$,其中 $n \leq 2^{31}-1$。
首先考虑 $\mu$:
首先我们需要找到一个函数,使得它与 $\mu$ 的狄利克雷卷积的前缀和是容易计算的。注意到关于 $\mu$ 的一个性质:$\mu * I = \epsilon$。
发现 $\epsilon$ 的前缀和十分好算(就是 $1$),并且 $I$ 非常有利于乘法分块,于是我们取 $f(n) = \mu(n),g(n) = I(n)$,代入上式,得:
$$S(n) = 1-\sum_{i=2}^n S(\lfloor \frac{n}{i} \rfloor)$$
类比我们来考虑 $\phi$:
发现一个性质:$\phi * I = id$
$id$ 的前缀和可以用等差数列求和公式求得,代入上式可以发现:
$$S(n) = \sum_{i=1}^n i – \sum_{i=2}^n S(\lfloor \frac{n}{i} \rfloor)$$
也就是
$$S(n) = \frac{n(n+1)}{2} – \sum_{i=2}^n S(\lfloor \frac{n}{i} \rfloor)$$
现在我们来证明一下这东西的复杂度是什么 。
设 $T(n)$ 表示计算出 $S(n)$ 的复杂度,可以得到:
$$T(n) = O(\sqrt{n}) + \sum_{i=2}^{n}(T(i)+T(\frac{n}{i}))$$
展开一层就可以了,因为往下都是高阶小量可以不考虑。
$$T(n) =O(\sqrt{n})+\sum_{i=2}^n(O(\sqrt{i})+O(\sqrt{\lfloor \frac{n}{i} \rfloor})) = O(n^{\frac{3}{4}})$$
我们可以用筛法处理前 $k$ 个,如果 $k \geq \sqrt{n}$,则
$$T(n) = \sum_{i=1}^{\frac{n}{k}}O(\sqrt{\lfloor \frac{n}{i} \rfloor}) = O(\frac{n}{\sqrt{k}})$$
一般我们 $k$ 取 $n^{\frac{2}{3}}$,可以得到复杂度为 $O(n^{\frac{2}{3}})$ 的算法。

两道小题目

Sum 加强版

$$\sum_{i=1}^n (i \times \phi(i))$$
求上式的值,其中 $n$ 是线性筛跑不过的量级。
我们一眼看不出来 $g$ 用什么好,不妨先假定有了这个函数并代入狄利克雷卷积的形式:$\sum_{d|n} (d * \phi(d)) \times g(\frac{n}{d})$。
这个常数 d 太烦人了,不如我们想办法消去它。我们尝试取 $g = I$,代入化简得到
$$\sum_{d|n} (d* \phi(d))* \frac{n}{d} = n\sum_{d|n} \phi(d) = n^2$$
这样的话前缀和就很好求了,带回原式可得:
$$S(n) = \sum_{i=1}^n i^2 – \sum_{d=2}^n d* S(\lfloor \frac{n}{d}\rfloor)$$
大家都会 $O(1)$ 求 $\sum_{i=1}^n i^2$,也就是
$$\sum_{i=1}^n i^2 = \frac{n(n+1)(2n+1)}{6}$$

Hdu 5608 Function

题目链接
告诉你一个数论函数 $f(d)$,满足
$$\sum_{d|n} f(d) = n^2-3n+2$$
多次询问 $f$ 的前缀和。
$T \leq 500,N \leq 10^9$,只有五组 $N > 10^6$。
长得十分像莫比乌斯反演的经典形式。
我们设 $g(n) = n^2-3n+2$,原式转化为
$$g(n) = \sum_{d|n} f(d)$$
反演一波可以得到:
$$f(n) = \sum_{d|n} g(d)\mu(\frac{n}{d})$$
我们要求的答案变成了:
$$\sum_{i=1}^n \sum_{d|n} g(d) \mu(\frac{n}{d})$$
进行一些微小的变换,可以推导出
\begin{align}
& \sum_{i=1}^n \sum_{d|n} g(d) \mu(\frac{n}{d}) \\
& = \sum_{d=1}^n g(d) \sum_{i=1}^{\lfloor \frac{n}{d} \rfloor} \mu(i) \\
\end{align}
发现 $g$ 的前缀和十分好求,这样就可以通过数论分块+杜教筛 $\mu$ 来做了。

赞赏
知识共享许可协议
本文链接: https://blog.aor.sd.cn/archives/574
如文中无特殊声明,本文采用 CC BY-NC-SA 4.0 进行许可,转载请说明出处!
希望 NOIP 不要翻车,希望省选不要翻车
https://secure.gravatar.com/avatar/97c17c68a1e55e11bb5558bc0f10cc0d?s=256&d=mm&r=g

RainAir

文章作者

一个OIer。

发表评论

textsms
account_circle
email

  • https://secure.gravatar.com/avatar/9bf9bef5770fdd746be3c582ed28994a?s=80&d=mm&r=g
    lqy1416

    orz,RainAirtql

    6月前回复
  • https://secure.gravatar.com/avatar/e441eef7e735efd3cfe1df7d9215caba?s=80&d=mm&r=g
    lukelin

    %%% 杜教筛巨佬 RainAir

    2月前回复

RainAir

杜教筛学习笔记
介绍 我们在 OI 题目中,不难会遇到给定一个积性函数 $f(x)$,求 $$\sum_{i=1}^N f(x)$$ 的题目。虽然对于积性函数我们已经有成熟的线性筛方法来说可以做到 $O(n)$,可是有的出题人就是…
扫描二维码继续阅读
2019-03-31
标签
近期评论