积性函数筛法（后记）_算法

后记

本篇文章经过了多次重构，希望能达到一个我满意的效果。

对于积性函数筛法，我曾有相当大的心结在其中，这是一个学起来会相当破防的东西。

最初我只打算学一个杜教筛，然后我打开了洛谷模板最优解，我发现跑的最快的 @XeCtera 的 #10 跑了 18ms，而我的 #10 跑了 1.31s。

七十多倍的性能差距让我有了很大的性能焦虑，试想如果某题（例：P3601 签到题）给定 $10^{13}$ 的数据范围，让你找到某些性质来减小复杂度，而别人拍了一个杜教筛过去了，你死活过不去，此时你真的会甘心去发现某些性质吗？

于是我打算学习这份跑的很快的代码。

首先代码中有一些十分有用的卡常技巧，譬如 $\rm Dirichlet$ 双曲线法代替整除分块，用两个数组分别存储低位和高位而不是维护映射，用递推代替递归，在瓶颈处把整数除法换为小数逆元等等，学习了这些技巧让我的 $\Theta(n^{2/3})$ 跑的飞快，已经是他最优解 $\Theta(n^{2/3}\log^{-1})$ 的两倍左右。

此时我便来了很强的兴致，打算学习这份没有地方讲的 $\Theta(n^{2/3}\log^{-1})$ 代码，在探索的过程中我读到了 OI中常用数论函数求和法的简化陈述 这篇深刻洞察了本质的文章，我感受到积性函数有相当美的一些性质，想要将其整理为模板化。

但在细化对本篇博客的理解中我逐渐发现事情并不对劲，那篇文章中附加和取消贡献的措辞让我想要照着该过程实现，但经过了优化的洲阁筛其实性质并没有那么好，最终我理解了三天选择抄一遍 $\rm dp$ 实现。

此时有了一定基础，学完 $\rm PN$ 筛的相关内容我便去学习 $\Theta(n^{2/3}\log^{-1})$ 求 $\mu$ 的块筛，当我总共花费一个周终于看懂并写出一份实现的时候，它跑的比我之前那份卡过常的暴力要慢，一下子，我这一个周的探索就像全在摆着度过了一般，我匆匆记了几笔就弃坑而逃，甚至没有做一道非板子题。

我初学时定下的两个目标，学很快的筛，以及学很通用的筛，其实都没有达成，所以学筛子我认为要有如下两点：

• 不要有性能焦虑，任何复杂度上的优化都不如你一个一个把代码中为了方便而写的映射下标给改成用两个数组存储，在瓶颈处少了一些除法。
• 不要一口气想要学一个万能筛法，需求不同用的筛法本来就不该相同，它们在码量、通用性、速度上各有差别，如果只想要学一个无脑筛法以便于遇到的时候直接贴板子，那就像一个人学数据结构走火入魔，遇到思维题动不起来脑子。