min_25 筛适用于求积性函数前缀和,并且能够找到一个完全积性函数使得两个函数质数处的取值相同。

约定

质数:表示质数集合。设表示从小到大第个质数,其中。另一方面,约定表示小于等于的质数构成的集合,即。特殊地,设表示的最小质因子。

函数定义:定义是一个积性函数。完全积性函数,且满足

摘要

  1. 我们的目标是求
  2. 由于是积性函数,因此。于是转化为
  3. 我们先求出,表示所有质数处的取值。
  4. 然后统计所有合数的贡献,再加上和 1 就是

第一部分

定义

表示满足以内的质数或者最小质因子大于的和。我们可以用埃氏筛来理解这个定义,相当于目前筛到了质数,最小质因子大于的数则没有被筛到。

显然。并且

考虑递归计算。讨论的关系。

如果,意味着。以内不存在最小质因子大于等于合数。即。因此得到

如果,那么相当于我们只需要在里减掉多余的部分就可以得到。具体地,我们减掉合数就可以了。由于是完全积性函数,因此这部分的和可以表示为

另一方面,后者可以用表示:

于是可以得到

综上,得到

,则上式可以简化为

容易发现,我们并不需要求出。设满足。那么显然

因此我们线性筛预处理出,然后预处理出,这样就可以计算了。实现可以使用滚动数组。

这部分的时间复杂度约为是

第二部分

定义

即所有最小质因子大于等于的和。那么可以得到

同样考虑求出的递归式。我们把质数和合数的贡献分开考虑。

质数部分的贡献显然是

对于合数部分,我们枚举它的最小质因子,假设是。然后枚举在合数中出现的次数,假设为。那么剩下的部分如果大于 1,就表示为。如果一个合数只含有质因子,那么表示为就行了。这时的贡献就是

综上得到

事实上,这里的可以完全由代替。

在实现的时候直接递归即可。

这个部分的复杂度是的。

时,Min_25 筛的总时间复杂度是的。

Luogu 5325 Min_25 筛

参考文献

duyi 的博客 - Min_25 筛