【学习笔记】线性筛的综合运用

前置知识:线性筛素数

从艾筛到欧拉筛

艾筛

艾筛是人们最早发现的筛素数的方法。假设需要筛出$\leq n$的所有素数,只需要开一个数组标记合数。按顺序遍历$\in [2, \sqrt{n}]$,如果没被标记,就把范围内它的倍数全部标记上。复杂度是$O(n\log\log n)$

欧拉筛

欧拉筛也就是线性筛素数,复杂度严格线性$O(n)$。具体方法如下:

  • 开一个数组标记合数,并记录一个素数集合。开始先把$1$标记为合数
  • 遍历$\in [2,n]$的所有数$i$

    • 如果不是素数,放入素数集合
    • 遍历素数集合,筛掉范围内的合数
    • 剪枝:在遍历素数集合的过程中,如果该素数$j$能整除$i$,那么直接开始遍历$i + 1$

代码实现

namespace Prime{
    bool com[MAXN];
    vector<int> prm;
    void GetPrm(int n) {
        com[1] = true;
        for (int i = 2; i <= n; i++) {
            if (!com[i]) prm.push_back(i);
            for (int j : prm) {
                if (i * j > n) break;
                com[i * j] = true;
                if (i % j == 0) break;
            }
        }
    }
}

前置知识:积性函数

  • 定义:对于一个定义域为$x \in Z$的数论函数$f(x)$,对于满足$gcd(x,y)=1$的$\forall x, y$,$f(xy)=f(x) \times f(y)$,那么函数$f(x)$为积性函数
  • 常见积性函数:

    • 欧拉函数$\varphi(x)$
    • 莫比乌斯函数$\mu(x)$
    • $x$的约数个数$d(x)$
    • $x$的约数之和$\sigma(x)$
  • 共同性质:可以利用线性筛来进行预处理

线性筛欧拉函数$\varphi$

定义

  • 我们定义欧拉函数$$\varphi(x)=\sum^{x-1}_{i=1}1[gcd(x,i)=1]$$,也就是比$x$小且与$x$互素的数的个数
  • 特殊的,我们规定$$\varphi(1)=1$$

性质

  • 显然,比一个素数小的所有数与他互素,也就是$$\varphi(prm)=prm-1$$
  • $\varphi(x)$是一个积性函数,所以对于$\forall x,y$,如果满足$gcd(x,y)=1$,都有$$\varphi(x \times y) = \varphi(x) \times \varphi(y)$$
  • 通过上一条性质易得出,对于任意素数$prm$和一个数$x$,如果$prm$不是$x$的一个因子,那么$$\varphi(prm \times x) = \varphi(prm) \times \varphi(x)$$
  • 对于任意素数$prm$和一个数$x$,如果$prm$是$x$的一个因子,那么$$\varphi(prm \times x) = prm \times \varphi(x)$$,在纸上推一推能证出来

程序实现

根据欧拉函数的性质,我们可以通过魔改线性筛素数来实现

namespace Euler{
    int phi[MAXN];
    int cnt = 0, prm[MAXN];
    bool com[MAXN];

    void Sieve(int n) {
        phi[1] = 1;
        com[1] = true;
        for (int i = 2; i <= n; i++) {
            if (!com[i]) {
                phi[i] = i - 1;
                prm[++cnt] = i;
            }
            for (int j = 1; j <= cnt ans i * prm[j] <= n; j++) {
                com[i * prm[j]] = true;
                if (i % prm[j] == 0) {
                    phi[i * prm[j]] = phi[i] * prm[j];
                    break;
                } else {
                    phi[i * prm[j]] = phi[i] * phi[prm[j]];
                }
            }
        }
    }
}

线性筛莫比乌斯函数$\mu$

莫比乌斯函数是在莫比乌斯反演时常用的函数,也可以通过线性筛求出。

定义

  • 将一个数$x$进行质因数分解
  • 如果$x$的质因子有重复的,$\mu(x) = 0$
  • 如果$x$的质因子没有重复

    • 如果有奇数个质因子,$\mu(x) = -1$
    • 如果有偶数个质因子,$\mu(x) = 1$
  • 特殊的,$\mu(p) = -1$,$\mu(1) = 1$

性质

  • $\mu(x)$是一个积性函数,所以满足$gcd(x,y)=1$的$\forall x, y$,$\mu(xy)=\mu(x) \times \mu(y)$
  • 根据积性函数和素数的性质,不难看出$\mu(x \times prm) = -\mu(x)$

程序实现

我们同样可以根据莫比乌斯函数的性质魔改欧拉筛