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

2023-11-09 07:35 由 Liquefyx 发表于 #其他

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

入门级：埃氏筛

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

for(int i = 2; i <= n; i++)
    if(st[i] == 0)//判断是否为质数
        for(int j = 2 * i; j <= n; j += i)
            st[j] = 1; // j是i的一个倍数，j是合数，筛掉。

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

//更快写法：
for(int i = 2; i <= n / i; i++)
    if(st[i] == 0)
        for(int j = i * i; j <= n; j += i)
            st[j] = 1; // j是i的一个倍数，j是合数，筛掉。

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

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

进阶：欧拉筛/线性筛

for(int i = 2; i <= n; ++i) {
    if(!vis[i]) pri[++cnt]=i;
    for(int j = 1; j <= cnt && pri[j] <= B/i; ++j) {
        vis[pri[j]*i]=1;
        if(i%pri[j] == 0) 
            break;
    }
}

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

特殊的筛

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

杜教筛

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

\[\begin{aligned} &\sum_{i=1}^n\big(f+g\big)(i)\\ =&\sum_{i=1}^n\sum_{d|i}f(d)g(\frac{i}{d})\\ =&\sum_{d=1}^ng(d)\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}f(i)\\ =&\sum_{d=1}^ng(d)S(\lfloor\frac{n}{d}\rfloor)\\ \end{aligned} \]

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

\[g(1)S(n)=\sum_{i=1}^n\big(f*g\big)(i)-\sum_{i=2}^n g(d)S(\lfloor\frac n d\rfloor) \]

这就是杜教筛的核心式子了，在求积性函数 \(f\) 的前缀和 \(S\) 时，我们可以选择合适的积性函数 \(g\) ，使得函数 \(g\) 与 \(\sum_{i=1}^n\big(f*g\big)(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 <= n; l = r + 1) { // 注意从 2 开始
    r = (n / (n / l)); 
    ans -= (g_sum(r) - g_sum(l - 1)) * GetSum(n / l);
    // g_sum 是 g 的前缀和
    // 递归 GetSum 求解
  } return ans; 
}

μ 的前缀和

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

\(\varphi\) 的前缀和

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

\(\varphi*Id\) 的前缀和

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