线性筛详解_数组筛法[通俗易懂]

大家好，欢迎来到IT知识分享网。

线性筛，可以理解为用 \(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. 欧拉函数

欧拉函数计算公式：

\(\varphi (x) = x \cdot \prod (1 – \frac{1}{p_i})\)

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

令 \(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);
    }
}

3. \(i^k\)（ \(k\) 给定）

可以看出，\(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);
    }
}

4. \(\tau\)（约数个数）

约数个数计算公式：

若 \(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}\) 可得：

\(k \cdot r^{-1} + i^{-1} ≡ 0\) \((\bmod\) \(p)\)

\(i^{-1} ≡ -k \cdot r^{-1}\) \((\bmod\) \(p)\)

\(i^{-1}≡ -\lfloor \frac{p}{i} \rfloor \cdot (p \% i)^{-1}\) \((\bmod\) \(p)\)

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

代码：

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