一些些筛子（埃氏筛、线性筛、杜教筛）

有时我们需要求出一个范围内的质数，或者要计算一些积性函数的值，但往往题目无法承受直接判断质数、直接求函数值的时间复杂度，这时我们就可以用筛子了

入门级：埃氏筛

假设当前有一块板，板上写着 (2sim n) 的数，如果我们想快速找出质数，那么我们可以考虑标记那些合数，让划了斜线的数表示合数，于是我们从左往右依次看，当遇到一个质数时，就把后面他的所有的倍数都划上斜线，而这就是埃氏筛的原理

for(int i = 2; i 

这是埃氏筛的简单实现，但我们又会发现，枚举一个更大的质数 (i) 的倍数时，假设当前乘的 (j)，若 (j 那么当前枚举的这个倍数肯定会被之前的更小的质数枚举到，于是能够进一步优化：

//更快写法：
for(int i = 2; i 

两个代码的时间复杂度分别为 (O(nloglog n))、（带点常数但近似于）(O(n))

埃氏筛还是比较容易理解的，所以新手一般建议使用埃氏筛 QwQ

进阶：欧拉筛/线性筛

for(int i = 2; i 

其实，埃氏筛即使是第二种写法依旧会给一些合数进行多次筛除操作，比如在筛 (24) 时，先用 (2times12) 筛了一次，但又用 (3times 8) 筛了一次，所以我们使用欧拉筛，每次给当前数乘上一个质数使得乘质数为乘积的最小质因数，这样每个数就只会被筛一次了，因此时间复杂度为线性，(O(n))，线性筛常用于求欧拉函数 (varphi)、莫比乌斯函数 (mu) 这些积性函数

特殊的筛

下面的筛子（目前只写了杜教筛 QwQ）用于一些特殊的用途，比如求积性函数的前缀和等等，算是高级算法

杜教筛

若现在要求积性函数 (f) 的前缀和，设 (S(n)=sum_{i=1}^nf(i))，再找一个积性函数 (g)，则考虑它们的狄利克雷卷积的前缀和：

会发现 (d=1) 时，(lfloorfrac{n}{d}rfloor=n)，那么：

这就是杜教筛的核心式子了，在求积性函数 (f) 的前缀和 (S) 时，我们可以选择合适的积性函数 (g) ，使得函数 (g) 与 (sum_{i=1}^nbig(f*gbig)(i)) 的值方便计算，从而快速地数论分块+递归+记忆化算出 (S(n))

当线性筛先筛到 (n^{frac 2 3}) 时，杜教筛的时间复杂度为 (O(n^{frac 2 3}))，硬跑的时间复杂度为 (O(n^{frac 3 4}))

ll GetSum(int n) { // 算 f 前缀和的函数
  ll ans = f_g_sum(n); // 算 f * g 的前缀和
  // 以下这个 for 循环是数论分块
  for(ll l = 2, r; l 

μ 的前缀和

因为 (mu*pmb 1=epsilon)，所以取 (f=mu, g=pmb 1)

(varphi) 的前缀和

因为 (varphi*pmb 1=Id)，所以取 (f=varphi, g=pmb 1)

(varphi*Id) 的前缀和

由于 (Big(big(varphi*Idbig)*IdBig)(n)=sum_{d|n}varphi(d)times dtimesfrac{n}{d}=ntimessum_{d|n}varphi(d)=n^2)，所以取 (f=varphi*Id, g=Id)

机房租用，北京机房托管，大带宽租用，IDC机房服务器主机租用托管-价格及服务咨询 www.e1idc.net