线性筛详解

CodePandorum · 2021-09-30 21:34:39 · 个人记录

线性筛，可以理解为用 O(n) 的时间复杂度处理 \leqslant n 定义域范围内每个点对应的某个函数值。比如线性筛质数等。

而筛法的思想非常简单，就是我们要求每一个数都被且仅被其最小的质因数筛掉，即只有在 pri[j] \leqslant min(prime(i)) 时筛 。所以我们只需要在 i \% pri[j] == 0 后 break 掉就行了。（因为 pri[j] 是从小到大枚举的，所以如果存在 i \% pri[j] == 0 就说明 pri[j] 已经是 i 的最小质因子了）

那么现在我就介绍一下做题中常见的几个使用线性筛的场合。

1. 质数

线性筛质数是线性筛最基础的内容，其思想就是最简单的“用 i 的最小质因子筛掉 i”。不多解释，直接贴代码:

for(int i=2;i<=k;i++){
    if(tof[i] == false){
        tof[i] = true;
        prime[++tot] = i;
    }
    for(int j=1;j<=tot && i * prime[j] <= k;j++){
        tof[i * prime[j]] = true;
        if(i % prime[j] == 0) break;
    }
}

2. 欧拉函数

欧拉函数计算公式：

接着我们沿用上面线性筛的思想考虑下这个问题。

令 k = pri[j] 。

如果 i \% k = 0 ，则 k 是 i 的最小质因子 。 此时 \varphi(i \cdot k) = \varphi(i) \cdot k 。然后直接 break 。

如果 i \% k \neq 0 , 则 i 与 k 互质 。此时 \varphi(i \cdot k) = \varphi(i) \cdot (k - 1) 。

以上两个式子都可以将左右两边带到原式中证明，不做赘述。

代码：

for(int i=2;i<=n;i++){
    if(prime[i] == false){
        phi[i] = i - 1;
        p[++tot] = i;
    }
    for(int k=1;k<=tot && i * p[k] <= n;k++){
        int j = p[k];
        int now = i * j;
        prime[now] = true;
        if(i % j == 0){
            phi[now] = phi[i] * j;
            break;
        }
        phi[now] = phi[i] * (j - 1);
    }
}

可以看出，i^k 是完全积性函数。即若 i=a\cdot b ，则 i^k = (a \cdot b)^k = a^k \cdot b^k 。

而小于 n 的质数个数 \pi(i) \approx \frac{n}{\log n} 个。

所以直接快速幂求出所有质数的 p^k ，然后再用线性筛筛合数的 i^k 即可。

复杂度可视为线性。

代码：

for(int i=2;i<=n;i++){
    if(prime[i] == false){
        kk[i] = ksm(i , pos);
        phi[i] = i - 1;
        p[++tot] = i;
    }
    for(int k=1;k<=tot && i * p[k] <= n;k++){
        int j = p[k];
        int now = i * j;
        prime[now] = true;
        kk[now] = kk[i] * kk[j] % mod;
        if(i % j == 0){
            phi[now] = phi[i] * j;
            break;
        }
        phi[now] = phi[i] * (j - 1);
    }
}

约数个数计算公式：

若 x = \prod p_i^{ei}

则 \tau(x) = \prod (1+e_i)

观察这个式子，我们发现它也有可线性筛的性质。

我们用 g_i 代表 i 这个数字的最小质因子的指数 + 1 ，t_i 代表 \tau(i) 。

若 i 为质数，很显然 t_i = g_i = 2 。

令 k = pri[j] 。

如果 i \% k = 0 ，则 k 是 i 的最小质因子 。 此时 t_{i \cdot k} = \frac{t_i \cdot (g_i + 1)}{g_i} ，g_{i \cdot k} = g_i + 1 。然后直接 break 。

如果 i \% k \neq 0 , 则 i 与 k 互质 ，且 k 小于 i 的最小质因子。此时 g_{i \cdot k} = 2 , t_{i \cdot k} = 2t_i 。

和上面的线性筛欧拉函数大同小异。

for(int i=2;i<=MAXN;i++){
    if(tof[i] == false){
        g[i] = 2;
        t[i] = 2;
        prime[++tot] = i;
    }
    for(int j=1;j<=tot && prime[j] * i <= 1e6;j++){
        int k = prime[j];
        if(i % k != 0){
            g[i * k] = 2;
            t[i * k] = t[i] * 2;
            tof[i * k] = true;
        }
        else {
            t[i * k] = t[i] / g[i] * (g[i] + 1);
            g[i * k] = g[i] + 1;
            tof[i * k] = true;
            break;
        }
    }
}

5. 线性求逆元

线性求逆元并不属于线性筛，但由于它的复杂度为线性，所以我们在这里也简述一下。

设 p = k \cdot i + r 。

则 k = \lfloor \frac{p}{i} \rfloor ， r =p \% i 。

那么可得：k \cdot i + r ≡ 0 (\bmod p)

同乘 i^{-1} , r^{-1} 可得：

通过这个式子就可以线性求逆元了。

代码：

inv[1] = 1;
for(int i = 2; i < p; ++ i)
    inv[i] = (p - p / i) * inv[p % i] % p;