对埃筛的理解

以前学埃筛的时候, 自以为自己理解了, 可实际上并没有理解, 而且是属于那种完全不知道原理的状态. 从 2020 年小米邀请赛开始, 就接触过了一些关于整除关系转移的 dp 题, 直到上周(还是上上周来着? 咕太久了, 不知道哩)cf的两个题, 都能够用埃筛优化. 做 cf 那两题时, 把埃筛优化 dp 的原理想清楚了, 同时也理解了埃筛为什么能够加速求素数的原理.

埃筛原理

普通的筛法是: 枚举一个数, 把他的倍数筛掉. 复杂度 $O(n \log n)$

埃筛是基于整除的传递性, 即 $a | b, b | c \Rightarrow a | c$ 来加速的. 在枚举 $a$ 的乘数时, 会筛掉 $b$, 同时也会筛掉 $c$. 但是当枚举到 $b$ 时, 又会筛掉 $c$. 这显然是一个无用的计算. 埃筛就是考虑 $a$ 只筛掉 $b$, 而 $c$ 留给 $b$ 去筛. 这样, 每条链就只枚举一遍了, 而不是向之前的那样, 每条链都用 $O(len^2)$ 的计算去筛.

那么如何实现呢? 首先转换一下之前的思维. 以前理解筛法时, 是认为枚举质数筛质数的倍数. 这样写没问题, 但是复杂度还是 $O(n \log n)$, 因为不知道下一个枚举的数是不是质数. 所以第一层循环每个数都要枚举到. 而埃筛是这样做的: 枚举乘数, 再枚举质数. 相当于上面换了枚举的顺序. 这样做有什么好处呢? 由于质数是一边在生成的, 所以当乘数枚举到 $k$ 时, 质数 $p$ 不会超过 $k$, 也就是说, 最远到 $k^2$. 这个 $k^2$ 就很好玩了. 由于 $k | k^2$, 我们希望筛到这里停下来, 因为这里恰好把之前的所有素数都乘过了, 之后的倍数由更大的数去筛. 同时, 由于枚举的质因数 $p$ 都不超过 $k$, 如果 $k$ 中含有因子 $p$, 我们能够把 $sp^2$ 给筛掉. 也就是之前枚举的乘数 $s$, 它筛到 $sp$ 停止了, 之后的数被 $k = sp$ 筛掉了. 数学归纳一下, 就能够证明每个合数都能被筛掉.

关于复杂度? 我不会.

原理迁移

由于整除关系的传递性, 我们优化了复杂度. 那么把问题拓展到 dp, 只要 dp 状态的前驱是因数, 并且 dp 方程具有可传递性, 那么我们就能够通过相同的方法去优化复杂度.

比如说小米邀请赛那题:

从长度为 $n$ 的序列 $a$ 中取一些数, 要求两两满足倍数关系. 问最多取多少个数.

$1 \le n \le 2 \cdot 10^5, 1 \le a_i \le 10^7$

设 $dp(x)$ 表示取出来的数不超过 $x$ 且一定取 $x$, 最多能取的数量.

$$dp(x) = cnt(x) + \max_{y | x} dp(y)$$

其中 $cnt(x)$ 是 $x$ 在 $a$ 中出现的次数.

可以看到, $\max$ 在这个方程中是具有传递性的, 比如 $dp(2) \leftarrow dp(4) \leftarrow dp(8)$, $dp(2)$ 可以从 $dp(8)$ 转移过来, 但是 $dp(4)$ 也是从 $dp(8)$ 转移, 而且如果成功转移, 那么 $dp(2) \leftarrow dp(4)$ 实际上就是 $dp(2) \leftarrow dp(8)$. 所以, 我们可以通过同样的方法进行优化:

首先枚举乘数 $k$, 再枚举小于 $k$ 的质数 $p$ (质数表已经预处理出来了). 然后转移 $dp(k) \leftarrow dp(pk)$ 即可.

这道题的代码长这样:

1
2
3
4
5

for (int x = 1; x <= maxa; x++) {
	dp[x] += cnt[x];
	for (int j = 1; j <= prime_num, prime[j] * x <= maxa; j++)
		dp[prime[j] * x] = max(dp[prime[j] * x], dp[x]);
}

CF 那个题需要一个思考的过程, 懒得写题解了, 就直接放方程:

$$dp(i) = \max \{ \max_{y | x}\{dp(j) + i \cdot (cnt_i - cnt_j)\}, i \cdot cnt_i \}$$

和上面是一模一样的, 直接放代码了:

1
2
3
4
5
6
7
8

for (int i = maxa; i; i--) {
	dp[i] = 1ll * i * cnt[i];
	for (auto p : prime) {
		LL j = 1ll * p * i;
		if (j > maxa) break;
		dp[i] = max(dp[i], dp[j] + 1ll * i * (cnt[i] - cnt[j]));
	}
}