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

前置知识：线性筛素数

从艾筛到欧拉筛

艾筛

艾筛是人们最早发现的筛素数的方法。假设需要筛出$\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 && 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)$

程序实现

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

版权属于：Noire02

本文链接：https://noire02.moe/archives/sieve.html

北京第三区交通委提醒您：复制千万条，版权第一条。转载删出处，博主两行泪。