• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

线性筛详解

开发技术 开发技术 4小时前 2次浏览

线性筛,可以理解为用 (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;
    }
}
  1. 欧拉函数

欧拉函数计算公式:

(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);
    }
}
  1. (i^k)(k) 给定)

可以看出,(i^k) 是完全积性函数。即若 (i=acdot 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);
    }
}
  1. (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;
        }
    }
}
  1. 线性求逆元

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

(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;

程序员灯塔
转载请注明原文链接:线性筛详解
喜欢 (0)