一些些筛子(埃氏筛、线性筛、杜教筛)

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

入门级:埃氏筛

假设当前有一块板,板上写着 \(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\)

热门相关:我家影后超甜的   高人竟在我身边   余生皆是喜欢你   黜龙   萌宝来袭:总裁爹地,宠上天