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

记号说明

  1. 表示质数集合。

  2. 表示从小到大第个质数()。

  3. 表示小于等于的质数构成的集合,即
  4. 表示的最小质因子。

前提条件

定义是一个积性函数。完全积性函数,且在质数处的取值相同,即,且要能快速计算前缀和。

算法摘要

简单描述一下筛法的步骤:

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

第一部分

定义

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

显然。并且。边界情况。因此为了计算需要支持快速计算前缀和。

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

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

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

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

于是得到

,则汇总两个转移得到

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

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

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

第二部分

定义

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

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

质数部分的贡献显然是

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

综上得到

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

这个部分的复杂度是的。

小结

第一部分的本质上用于处理完全积性函数在质数处取值的前缀和问题。换言之对于在质数处的表达式,只要能将其分解为若干个完全积性函数的和的形式,那么就可以分别使用这一过程处理。

第二部分的核心部分是递归,这要求我们能快速计算在质数幂处的取值,这样利用第一个过程里预处理的部分就可以筛出来。

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

模板代码