扩展埃氏筛

摘要

本文介绍一种比欧拉筛更高效的筛法,扩展 Eratosthenes 筛法。

杜教筛适用范围较小,未充分利用积性。扩展埃氏筛要求对于任意质数 p, 是一个关于 p 的低阶多项式。对于任意 的指数 可以快速求出。

约定

接下来先说明一下本文所用到的记号以及一些约定。

  1. ,即前缀和函数。
  2. 从小到大第 i 个质数记作 ,特别地,
  3. 以内的质数有 m 个。
  4. 对于集合 ,则

问题转化

我们要求的式子是

其中 是一个积性函数。首先我们知道 n 以内的数至多只有一个大于 的质因子,因此我们把数按照有无大于 的质因子分类考虑。对于含有大于 的一类,我们可以把这个质因子拎出来,剩下的就又是不含有大于 的一类。于是写出来就是这样的

注意到后半部分内层求和因子的条件,由于 ,因此 ,于是得到

问题转化为处理式子的前半部分和后半部分。

后半部分

我们考虑 的后半部分

先考虑这样一个问题,求

由于 是一个多项式,因此我们可以对每一项分别做,问题转化为求

我们考虑 DP。设 表示对于满足 的最大公约数为 1 的 的和。即

注意在上式中,一定满足 ,否则无法互质。

先考虑 ,这个可以用拉格朗日插值在 的时间内计算出来。另一个显然的边界是

然后考虑转移。从 转移到 ,我们希望 互质。显然这并不容易枚举,因此我们枚举不与 互质的部分,得到

变成然后再回到 ,你发现与 互质的 以内的数一定是质数,于是得到

那最终我们要求哪些 DP 值?由于 ,于是 不超过 种,可以递归做。这样做的复杂度是 。因为质数密度是 ,而计算 DP 值时我们只枚举 以内的质数(这部分质数直接先欧拉筛预处理)。

优化

上述 DP 方程仍可以优化。上文中我们分析过,对于满足 必须满足 。事实上,如果 ,说明 不可能满足 ,显然在这个区间的合数都不合法。这样可以得到:

  1. 时, ,前文所述。
  2. 时, ,因为这时候只有 满足条件。
  3. 时,有 ,则转移变成 。因为

思考这样一个过程:我们要计算 。于是我们从小到大枚举一个

时我们按照普通的 DP 方程直接转移计算

时,显然之后的所有的 都满足 ,于是可以直接累加 。因此我们记 ,表示 的转移的最后一个位置。于是得到

后半部分显然可以预处理前缀和。这样优化后,算法复杂度降低到

Min_25 筛

考虑另一种转化

我们仍按照质因子与 的大小关系分类:

接下来我们考虑DP。设

对于 函数,当 时,显然

否则 ,考虑DP的转移

答案即为


  转载请注明: Sshwy's Blog 扩展埃氏筛

 上一篇
约瑟夫问题 约瑟夫问题
摘要 约瑟夫问题由来已久,而这个问题的解法也在不断改进,只是目前仍没有一个极其高效的算法(log以内)解决这个问题。 问题描述 n个人标号 逆时针站一圈,从 号开始,每一次从当前的人逆时针数 个,然后
2019.07.16
下一篇 
上下界网络流 上下界网络流
摘要 对于普通的网络流问题,我们在一个网络 上求解相关的问题。网络的边有一个容量,即流量上界 。而有时候我们要求这条边有一个流量下界 ,这样的相关问题被归为上下界网络流问题。 无源汇可行
2019.07.11
  目录