筛法

二gou子 · 2021-06-09 10:53:35 · 个人记录

线性筛

感觉一直对线性筛理解的不是很到位，重新写一下原理

素数

首先筛素数有个初学 OI 的人都会的 O(n\sqrt{n}) 筛出 n 以内的所有素数。然后有一个简单易实现的埃氏筛（其实线性筛代码也很好写），就是每次找到一个质数就把它所有在 n 以内的质数全部标记为合数，这样做下来的复杂度是 O(nloglogn) ，至于为什么我也不会证，反正很接近于线性了。而线性做法也很简单，只要保证每个数只被筛一次就可以了。我们可以通过用最小质因子筛掉来保证这一点。比如说，6 这个数会被 2 和 3 筛掉，也就是会被筛两次，这样就遍历了冗余情况。所以我们如果可以保证 6 只被 2 筛掉就可以达到线性了

代码如下：

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<queue>
using namespace std;
typedef long long int ll;
const int N=1e8+3;
int inline read(){
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
    while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n,q,tot;
int pri[N];
bool vis[N];
void xxs(){
    for(int i=2;i<=n;i++){
        if(!vis[i]){
            pri[++tot]=i;
        }
        for(int j=1;j<=tot&&pri[j]*i<=n;j++){
            vis[i*pri[j]]=1;
            if(i%pri[j]==0) break;//这一句是关键，保证了只被最小质因子筛掉
        }
    }
}
int main()
{
    n=read();q=read();
    xxs();
    for(int i=1;i<=q;i++){
        int x;
        x=read();
        printf("%d\n",pri[x]);
    }
    return 0;
}

好了，然后我们发现数组里面是两个数的乘积，这也启发我们可以用线性筛出积性函数（比如欧拉函数和莫比乌斯函数），而因数和和因数个数恰好也都是积性函数（或许是？），所以可以线性筛出来

因数个数

首先先来说因数个数，先把任意一个数 a 表示成 a_1^{p_1}*a_2^{p_2}*...*a_n^{p_n} ，那么很明显因数个数是 (p_1+1)*(p_2+1)*...*(p_n+1) 。这个东西根据乘法原理可以很轻松的推出来，每一个质因子都有 0~p_i 共 p_i+1 种选择，把它们乘起来就是最后的结果。但是现在我们就要运用线性筛求出因数个数

先设两个数组：num_i 表示 i 的最小质因子的个数，是一个辅助数组，sum_i 表示 i 的因数个数

来一波分类讨论：

$2.$ $i\%pri_j==0$ ，那么说明 $pri_j$ 是 $i$ 的最小质因子（根据线性筛的原理，如果不是就已经 $break$ 掉了）。那么 $num_{i*pri_j}=num_i+1$ 是显然的，现在我们可以把 $i*pri_j$ 表示成 $a_1^{p1+1}*a_2^{p_2}...*a_n^{p_n}$ ，递推一下就会发现 $sum_{i*pri_j}=sum_i/(p_1+1)*(p_1+2)$ ，直接推过去就好了 $3.$ $i\%pri_j!=0$ ，那么说明此时 $pri_j$ 是 $i*pri_j$ 的最小质因子，那么就相当于在 $i$ 的基础上多舔了一个 $a_1^{p_1}$ ，其中 $p_1=1$ 。所以直接 $sum_{i*pri_j}=sum_i*2,num_{i*pri_j}=1

以上三种情况就已经覆盖了所有情况，并且可以实现 O(1) 递推转移。由于线性筛本来就是线性的，所以时间复杂度还是 O(n)

核心代码如下：

void xxs(){
    for (int i=2;i<=N;i++){
        if(!vis[i]){
            pri[++tot]=i;
            num[i]=1;
            sum[i]=2;
        }
        for (int j=1;j<=tot&&i*pri[j]<=N;++j)
        {
            vis[i*pri[j]]=1;
            if (!(i%pri[j]))
            {
                num[i*pri[j]]=num[i]+1;
                sum[i*pri[j]]=sum[i]/(num[i]+1)*(num[i*pri[j]]+1);
                break;
            }
            sum[i*pri[j]]=sum[i]*2;
            num[i*pri[j]]=1;
        }
    }
}

约数和

下面来说如何求约数和：首先我们发现每一个质因子有 p_i+1 种选择，而每种选择对应着一种贡献。所以可以将约数和表示为 (1+a_1^1+a_1^2+...+a_1^{p_1})*...*(1+a_n^1+a_n^2+...+a_n^{p_n}) ，这个式子不难理解，下面我们要做的就是 O(1) 转移

根据上面的经验，我们发现线性筛过程中每次筛的时候都是用最小的质因子筛掉，这启发我们只需要开一个辅助数组来记录一下最小质因子所代表的等比数列的和就可以了（即 1+a_1^1+a_1^2+...+a_1^{p_1}) ，每次更新即可，下面依然来分类讨论：

先开几个数组：cnt_i 代表辅助数组，含义如上；sum_i 代表约数和

$2.$ $i\%pri_j==0$ ，这也就是说 $i*pri_j$ 的最小质因子多了一项，所以这个时候我只需要推一下式子，发现更新之后辅助数组应该是这样的：$(1+a_1^1+a_1^2+...+a_1^{p_1+1})$ ，所以我们在原来的基础上乘以 $a_1$ 再加 $1$ 就可以转移过来了。和同理，除以原来的再加上新的就好了 $3.$ $i\%pri_j!=0$ ，那么 $i*pri_j$ 的最小质因子是 $pri_j$ 而且只有一个，所以说直接 $cnt_{i*pri_j}=pri_j+1,sum_{i*pri_j}=sum_i*(1+pri_j)$ 就好了代码就不放了，和求约数个数是差不多的，改一下等号右边的式子就好了至此，我们做到了 $O(n)$ 求出 $n$ 以内的质数，并且求出了每个数的约数个数和约数之和，感觉非常神奇，所以写一下其实学这个只是因为有一个题目要用，但是考虑到这个不是关键的一步，所以就干脆不放那道题了 $QAQ

Upd:6/28，欧拉函数和莫比乌斯函数也来筛一筛

欧拉函数

欧拉函数的定义：φ(n) 表示在 [1,n] 这个区间内和 n 互素的数的个数，例如 φ(1)=1 ，而显然如果 n 是质数，φ(n)=n-1，欧拉函数有如下的递推式：

设 p_1 是 n 的最小质因数，n'=n/p_1 ，如果 n'\%p_1=0 ，那么 φ(n)=p_1*φ(n')；反之，那么 φ(n)=φ(p_1)*φ(n')

这两个式子需要结合欧拉函数的性质，在另一篇博客里会单独详细地介绍，在此只是写出筛法的式子，所以不再赘述

而我们可以根据这个递推式在 O(n) 的时间复杂度内使用线性筛，把 [1,n] 的欧拉函数都筛出来。但如果要求单个数的欧拉函数，~~我只会 O(\sqrt{n}) 暴力枚举~~

莫比乌斯函数

莫比乌斯函数定义：设 n 的莫比乌斯函数值为 μ(n)，则如果 n=1 ，μ(n)=1；如果 n 含有平方因子，μ(n)=0；如果不满足以上两个条件，则 μ(n)=(-1)^k，其中 k 为 n 的不同的质因子个数

先把 Code 扔上来再讲原因：

void xxs(){
    for(int i=2;i<=n;i++){
        if(!vis[i]){
            mi[i]=-1;//质数只有它本身一个质因子 
            pri[++tot]=i;
        }
        for(int j=1;j<=tot&&pri[j]*i<=n;j++){
            vis[i*pri[j]]=1;
            if(i%pri[j]==0){
                //说明这个数有平方因子
                mi[i*pri[j]]=0;
                break; 
            }
            mi[i*pri[j]]=-mi[i];//多了一个质因子 
        }
    }
}

好吧不用讲原因了，直接看注释就好了

~~学欧拉函数性质和莫比乌斯反演去了，兄弟们再会~~