另一种更为优秀的快速筛莫比乌斯函数的筛法

关于 (mu) 函数的另一种较快速的筛法

(Q: sum_{i=1}^n mu(i))

注:接下来的两步,是最精彩的,也是最令人窒息的两步操作

首先,必然有一份贡献为 (mu(1) = 1) 那么,我们先将他给单独拿出来,又因为 (mu) 函数取值只为 (0,1,-1) ,所以我们可以再进行一点耐人寻味的操作

原式可变成 :

(1-sum_{i=2}^n (0-mu(i)))

然而对于这个 (0) ,我们还可以再变成一个妙妙的样子

(1-sum_{i=2}^n(sum_{jmid i}mu(j) - mu(i)))

紧接着,我们换一个角度来陈述这个式子,我们来枚举每个 (mu(i)) 出现的次数来统计它们的贡献

变化如下:

(1-sum_{j=2}^nmu(j)(lfloorfrac{n}{j} floor-1))

显然,当 (j > frac{2}{n}) 时,它的贡献为 (0)

所以原式最终化简为:

(1-sum_{j=2}^{lfloorfrac{n}{2} floor}mu(j)(lfloorfrac{n}{j} floor-1))

显然为了配合下底分块的方法来处理,我们需要线筛 (sum_{j=2}^{lfloorfrac{n}{2} floor}mu(j)) ,然后用前缀和的操作来解决问题

从而我们递归处理这一部分

当然,我们也可以先预处理出较小范围的 (mu) 的值

二者结合则可以较为优雅的解决这一系列的问题了

心如花木,向阳而生。
原文地址:https://www.cnblogs.com/LLppdd/p/8410607.html