对埃筛的理解 @ Wings            分类 ACM
发布于 星期四, 十二月 9 日, 2021 年
更新于 星期四, 十二月 9 日, 2021 年

以前学埃筛的时候, 自以为自己理解了, 可实际上并没有理解, 而且是属于那种完全不知道原理的状态. 从 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)$ 即可.

这道题的代码长这样:

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 \}$$

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

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]));
	}
}
留下昵称和邮箱, 可在第一时间获悉回复通知哦~

2021 FLAG

  • 找个妹子
  • 进计科
  • XCPC拿块金牌
  • 补全算法知识, 整全板子
  • 学会Web开发相关知识
  • 在服务器上搭建电子书库
  • 写个游戏并上线
  • 能弹一首曲子
  • 写首完整的曲子
  • 练习悠悠球

个人简介

我叫 Wings, 来自江西上饶, 目前人在西安, 是西电的一名学生.

常以 WingsWingsZengWingsWings的ID在各大小网站上游走, 一般来说, Wings不是我 😔, WingsZeng 一定是我 😊.

热爱算法, 喜欢钻研各种计算机技术.

业余爱好广泛, 只要不是文化课基本上都感兴趣😏.

开发/项目经历

  1. Android游戏 小墨滴的复仇 (弃坑)
  2. Android游戏 Circle Run (弃坑)
  3. Windows游戏 Snague (可能弃坑了吧)
  4. Python后端 Fathy' (可能弃坑了吧)

to be continued

教育经历

时间 学历 学校
2008-2014 小学 上饶市第十二小学
2014-2017 初中 上饶市第四中学
2017-2020 高中 上饶市第一中学
2020-2024 本科 西安电子科技大学
to be continued

比赛/竞赛经历

太久远太小的记不到了…

  1. 2017 国学竞赛初赛江西 没有分数或排名 二乙
  2. 2018 NOIP提高 258 省二
  3. 2019 CSP-S江西专场 145 省二
  4. 2019 数学竞赛初赛 70 没排名 (复赛打铁qaq)
  5. 2020 Gitee|Python贪吃蛇魔改大赛 可能是第四? 二等奖
  6. 2020 西电ACM训练基地熊猫杯 第四 银牌
  7. 2020 西安三校微软学生俱乐部Hackathon 和二等奖最后一名差0.5分 三等奖
  8. 2020 西电星火杯 三等奖
  9. 2020 西电ACM新生赛 第九 金牌
  10. 2020 ICPC 亚洲区域赛 济南站 132名 铜牌
  11. 2020-2021 第二届全国大学生算法设计与编程挑战赛(冬季赛) 924名 铜牌 (别骂了别骂了)
  12. 2020 ICPC 亚洲区域赛 昆明站 打星
  13. 2020 ICPC Asia-East Continent Final 签完到溜 打铁
  14. 西电"智能星"第一届自动驾驶小车比赛 第五 优胜奖|极速奖 本来可以冠军的别骂了别骂了
  15. 2021团体程序设计天体赛(CCCC) 个人二等奖
  16. 2021 西电 miniL CTF 优胜奖
  17. 2021 西电ACM校赛 第9名 金牌
  18. 2021 西电数模校赛 二等奖
  19. 2021 第15届IEEE 第48名
  20. 2021 CCPC 桂林站 打星
  21. [2021 ICPC 沈阳 105名 真银尾]
  22. [2021 CCPC 哈尔滨 银牌]
  23. [2021 ICPC 南京 铜牌]

to be continued

爱好

技术

  • 算法
  • 独立游戏开发

游戏

  • Minecraft
  • Black Survival
  • I Wanna
  • Celeste
  • Life is Strange
  • Need for speed

运动

  • 篮球
  • 桌球
  • 乒乓球
  • 羽毛球
  • 慢跑

音乐

  • 吉他
  • 词曲
  • 流行

玩具

  • 魔方
    • 三阶速拧
    • 三阶盲拧
    • 高阶
  • yoyo球

追星

  • VAE
  • Benedict Cumberbatch