min_25筛(知识总结)

思路来源

https://www.cnblogs.com/cjyyb/p/9185093.html

https://www.cnblogs.com/zhoushuyu/p/9187319.html

https://www.mina.moe/archives/12287

心得

这个从去年上个月就想学的知识，终于在开学前被学会了

神仙min_25 QAQ 神仙zzt QAQ 神仙yyb QAQ

学会min_25筛比较难，但大概写一份能让初学者看懂的博客更难

然而学会之后，发现这个东西很模板，好像抄个板子改改就能过题

知识点

min_25筛，日本算竞选手min_25发明的，

一种埃筛思想的，求积性函数前缀和的，亚线性筛，

复杂度，不会证，

后来被他优化成的了，但常数比较大，所以用前面这个就行

目的

求

需要满足条件：

1.积性函数，若和互质，则

2.是个可以用多项式表示的值

3.可以快速计算

为了求这个式子，根据1、质数、合数把这个式子拆成三部分

质数部分

先求质数的部分，即，这里不妨令，

计是质数集合，表示第个质数。

为了求质数部分，引入

表示到中，满足是质数，或最小素因子大于第个质数的，的和

考虑如何求，dp思想，最后一次决策，是加入最小素因子等于第个质数的贡献，

所以，是要从里，删去最小素因子等于第个质数的贡献

 

由于满足最小素因子是的最小的数是，

①若，说明什么都没有删去，有

②否则，此时要删去最小素因子等于第个质数的贡献，记这样的数是，

那么的最小质因子也大于等于，就是大于

首先，提一个出来，其贡献是，这里是，

再乘上的最小质因子大于的贡献，即，

前一项多算了中的质数的贡献，后一项则减去这个多余的贡献

整理一下，就是

 

①、②，有

也即，

 

最终，即为所求，其中是小于等于的质数集合的大小，

毕竟，的数在里不存在

和埃筛的关系

个人感觉，就是先把所有数都当做质数，求一个和，

然后不断的用最小质因数的出现，把那些最小质因数是的合数从这个和中减掉，逼近最终的和，

当所有的合数都被划去时，就是真实的最终的和

 

以下段落截取自yyb大佬的博客，

根据上面的转移，需要的质数只有不大于的，所以只需要筛出这些质数就好了。

我们来思考一下函数所代表的含义，

我们可以理解为在模拟埃氏筛法的过程，

表示排成一列放在这里，但是你已经晒过一些质数了，

你把前个质数的倍数全部划掉了，剩下的求个的和就是函数。

所以转移的过程可以理解为已经筛完了前个质数，现在考虑删除第个质数的过程。

看到这里一定会感觉上面十分的有道理，但是又有一些疑问。

在上面的计算过程中，始终只考虑了≤的质数，那么，那些>的质数呢？

其实，我们的函数要计算的本来就只有质数的值，所以，我们的函数算出来的结果并不是真正的结果。

还记得上面对于这类积性函数有什么要求吗？能够快速的计算

所以，我们先假设所有的数的计算方法都等同于质数的计算方法，所以我们可以快速的计算前缀和

也就是，虽然这个值是假的。但是，如果中只包含了质数的值的话，那么它的计算结果就是真正的结果。

因此，预处理的过程，我们理解为一个计算所有质数的值的过程。

质数+合数部分

引入，

即求满足最小质因数大于等于的之和

也有维护大于的，二者转移式有微小差别，这里维护大于等于的

这个和分为两部分，

一部分是大于等于的质数，用所有质数的和减去小于的那些质数的和

一部分是最小质因数大于等于的合数，

考虑先枚举最小质因子，

再枚举的幂次，表明出现了几次，提一个的贡献出来，

剩下的质因数，就需要大于等于了，这部分是

当然，对于这个合数，也可能就这一个质因数，

形如，所以枚举的时候，再加上

写成公式的话，是

终极目的

第二维正着推求出，第二维倒着推求出，答案=质数+合数+F(1)，

结合的定义，答案是

细节

比如为了复杂度，实际用到的和状态没那么多，

求是基于数论分块的，所以只有个第二维的状态，

所以要开和和数组用于离散化这些状态，

记Sqr=sqrt(n)，不妨[l,r]这个区间段的n/l值相同，是第j个状态

若n/l<=Sqr，就用n/l记状态，id1[n/l]=j，

否则一定有r<=Sqr，就用r记状态，id2[r]=j，

还有必要写吗，这些不是都可以白嫖主义吗