C20250069's blog
数论分块与筛法入门
C20250069 LV 10 @ 2023-9-15 11:02:13

数论分块与筛法入门

数论分块

数论分块与一般的数列分块不同。数列分块一般是强行将一个区间划分成 $\sqrt{n}$ 个子区间，而数论分块的划分一般确保块内的情况相同。

例如说，对于 $\lfloor\frac{n}{i}\rfloor$ 这种东西，我们可以把值相同的 $\lfloor\frac{n}{i}\rfloor$ 划为一块。可以发现，在 $i \gt \sqrt{n}$ 时，最多有 $\sqrt{n}$ 种取值；在 $i \lt \sqrt{n}$ 时，取值互不相同，故 $\lfloor\frac{n}{i}\rfloor$ 最多有 $2\sqrt{n} + 1$ 种取值，这个时候用分块做的复杂度和数列分块是一样的。

数论函数

数论函数，一般指 $\N^* \to \Z$ 的一类函数。或者，也可以理解为一个无穷的整数数列。常见的数论函数有这些：

$\text{id}$ ， $\text{id}_k(x) = x^k$ ，默认有 $\text{id} = \text{id}_1$ 。
阶乘，即 $x!$ 。
$1$ ，即单位函数， $1(x) = 1$ 。
$\varphi$ ，即欧拉函数， $\varphi(x)$ 表示 $1$ 到 $x$ 中与 $x$ 互质的整数的个数。

这些是没学 $\text{oi}$ 可能不知道的：

$\varepsilon$ ，有 $\varepsilon(x) = [x = 1]$ 。
$\omega$ ， $\omega(x)$ 表示 $x$ 的不同质因子的个数。
$\mu$ ，莫比乌斯函数，若 $x$ 的某个质因子的次数大于 $1$ ，那么 $\mu(x) = 0$ ，否则 $\mu(x) = (-1)^{\omega(x)}$ 。

$$x = \sum_{i = 1}^{\omega(x)}p_i^{q_i}\\ \varphi(x) = x\prod_{i=1}^{\omega(x)}\frac{p_i - 1}{p_i}\\ \mu(x) = \begin{cases} 0 & \exists d \gt 1, d^2 | n\\ (-1)^{\omega(x)} & \text{otherwise} \end{cases}\\ $$

一般来说，函数相乘（和卷积及其他四则运算）可以简写，例如：

$$\text{id}_2(x) \times \varphi(x) = (\text{id}^2\varphi)(x) $$

这样写（估计）是为了方便写公式。

积性函数

数论函数 $f$ 是积性函数当且仅当 $\forall p, q \in \N^*, (p, q) = 1$ ，有 $f(pq) = f(p)f(q)$ 。

积性函数是筛法的主要研究对象（？

刚才提到的 $\text{id}, 1, \varphi, \varepsilon, \mu$ 都是积性函数。而 $\omega$ 是加性函数。

依靠感官，你可以感觉这几个函数确实是积性函数。

看看他们的公式，可以发现他们很多都是乘在一起的。

完全积性函数

令 $x = \sum_{i = 1}^{\omega(x)}p_i^{q_i}$ ，则根据定义，积性函数 $f$ 满足：

f(x) = \prod_{i = 1}^{\omega(x)}f(p_i^{q_i})

若 $f$ 是完全积性的，则还满足：

f(x) = \prod_{i = 1}^{\omega(x)}(f(p_i))^{q_i}

狄利克雷卷积

对于两个数论函数 $f, g$ ，定义他们的卷积 $f * g$ 为：

(f * g)(x) = \sum_{d|x}f(d)g(\frac{x}{d})\\

若有 $h(x) = \sum_{d|x}f(d)g(\frac{x}{d})$ ，则可简写为：

h = f * g

常见的卷积：

$$\mu * 1 = \varepsilon, \text{这个尤其重要}\\ \varphi * 1 = \text{id}\\ f * \varepsilon = f\\ $$

狄利克雷卷积具有几个性质：

交换律， $f * g = g * f$ 。
结合律， $f * (g * h) = (f * g) * h$ 。
分配律， $f * (g + h) = f * g + f * h$ 。

同时，对于积性函数 $f, g$ ， $f * g$ 也是积性的。

莫比乌斯反演

莫反就是利用卷积公式 $\mu * 1 = \varepsilon$ 来进行的一些计算。

一般来说，假设我们知道了 $f * 1 = g$ ，以及 $g$ 的定义，那么我们可以通过 $g * \mu = f$ 来求出 $f$ 。

例题：$\sum_{i = 1}^n \varphi(i), \sum_{i=1}^n\sum_{j = 1}^n [(i, j) = 1]$。

---分割线---

筛法

较多的筛法都是用来求一些积性函数的前缀和的。他们的设计目的都是使计算前缀和的时间复杂度可以降到亚线性，例如常见的有 $O(n^{\frac{2}{3}})$ 和 $O(n^{\frac{3}{4}})$ 的。这样的复杂度可以让他们处理 $10^8$ 甚至 $10^9$ 的数据规模。

常见的筛法有杜教筛，PN 筛，Min 25 筛，洲阁筛等。~~可以发现，这类筛法的模版题都是紫或以上。~~

杜教筛

这个筛法已经是他们当中最简单的筛法了。模版是紫的 ~~，但是有蓝的非模版题~~。

据说，杜教筛是 IOI 金牌选手 dyh 发明或引进的一个筛法。

这个筛法的主要思路是将积性函数 $f$ 的前缀和 $F(n)$ 转化为和 $F(\lfloor\frac{n}{i}\rfloor)$ 有关的子问题。

如果我们想要用杜教筛去计算 $f$ 的前缀和 $F$ ，需要构造一个（积性）函数 $g$ ，使得：

$g$ 是积性的。
$g$ 易求前缀和。
$f * g$ 易求前缀和。

那么最终，我们可以推导出 $F(n)$ 的公式：

$$g(1)F(n) = \sum_{i = 1}^n (f * g)(i) - \sum_{i = 2}^ng(i) F(\lfloor\frac{n}{i}\rfloor) $$

具体来证一遍：

$$\begin{align} \sum_{i=1}^n(f * g)(i) &= \sum_{i=1}^n\sum_{d | i}g(d)f(\frac{i}{d})\\ &= \sum_{d=1}^n g(d)\sum_{d|i}f(\frac{i}{d})\\ &= \sum_{d=1}^n g(d)\sum_{dj \le n} f(j)\\ &= \sum_{d=1}^n g(d)F(\lfloor\frac{n}{d}\rfloor) \end{align} $$

带入 $d = 1$ 得：

$$g(1)F(n) = \sum_{i=1}^n(f * g)(i) - \sum_{d=2}^n g(d)F(\lfloor\frac{n}{d}\rfloor)\\ $$

这就是杜教筛的公式了。

可以发现， $F(\lfloor\frac{n}{d}\rfloor)$ 要用数论分块， $g$ 和 $f*g$ 都可以线性求。

杜教筛的复杂度是 $O(n^{\frac{3}{4}})$ 的，如果前缀和可以线性筛的话，可以优化到 $O(n^{\frac{2}{3}})$ 。~~证明我也不会~~，就贺一下 OI-wiki 上的证明：

$$\begin{align} T(n) &= O(\sqrt{n}) + O(\sum_{i=2}^{\sqrt{n}}T(\lfloor\frac{n}{i}\rfloor))\\ T(\lfloor\frac{n}{i}\rfloor) &= O(\sqrt{\lfloor\frac{n}{i}\rfloor}) + O(\sum_{j = 2}^{\sqrt{\lfloor\frac{n}{i}\rfloor}}T(\lfloor\frac{n}{ij}\rfloor))\\ &= O(\sqrt{\lfloor\frac{n}{i}\rfloor}) \text{，后面的是高阶无穷小}\\ T(n) &= O(\sqrt{n}) + O(\sum_{i=2}^{\sqrt{n}}O(\sqrt{\lfloor\frac{n}{i}\rfloor}))\\ &= O(\sum_{i=2}^{\sqrt{n}}O(\sqrt{\lfloor\frac{n}{i}\rfloor}))\\ &= O(\int_{0}^n\sqrt{\frac{n}{x}}\text{d}x)\\ &= O(n^{\frac{3}{4}}) \end{align} $$

例题：$\sum_{i=1}^n\mu(i), \sum_{i = 1}^n\sum_{j = 1}^n ij(i, j)$。

PN 筛

PN 筛全称为 Powerful Number 筛，应该是译作~~力量数~~高幂次数筛。可以把他当作杜教筛的拓展。

先说说 PN 是啥。

一个数 $x$ 是 PN 当且仅当若 $x = \sum_{i=1}^np_i^{q_i}$ ，有 $q_i$ 均大于 $1$ 。

可以证明， $x$ 一定能表示为 $a^2b^3$ 的形式，并且 $1$ 到 $n$ 中的 PN 有 $O(\sqrt{n})$ 个。

那么，我们若要求 $f$ 的前缀和，则要构造两个函数 $g, h$ ，使得：

$g$ 是积性的。
$g$ 易求前缀和（可以用其他筛法）。
$f(x)$ 和 $g(x)$ 在 $x$ 为质数时取等。

我们令 $g * h = f$ 。根据证明， $h$ 只在 PN 处有值，那么类似的，有：

$$\begin{align} F(n) &= \sum_{i=1}^nh(i)G(\lfloor\frac{n}{i}\rfloor)\\ &= \sum_{i \text{ is PN}}^n h(i)G(\lfloor\frac{n}{i}\rfloor)\\ \end{align} $$

这个时候就可以用深搜求 PN 然后数论分块 + 杜教筛了。

~~这个筛法可以水 Min 25 筛模版。~~

$$\sum_{i=1}^n\sum_{j=1}^n[(i, j) = 1]\\ = \sum_{i=1}^n\sum_{j=1}^n\sum_{d|i, d|j}\mu(d)\\ = \sum_{d=1}^n\mu(d)\sum_{d|i}^n\sum_{d|j}^n1\\ = \sum_{d=1}^n\mu(d)\lfloor\frac{n}{d}\rfloor^2\\ $$