• 欢迎光临~

线性筛和牠的伙伴们 : OI数论(1)

开发技术 开发技术 2022-07-21 次浏览

1.线性筛

我们知道一种筛法,叫艾氏筛,复杂度为(O(N loglogN))

这个算法的复杂度的确很小,但是并不是严格线性的,接下来隆重介绍真正的线性筛法——欧拉筛

首先,我们先要知道为什么艾氏筛不能做到线性呢?是因为它的很多数都被重复筛了好多遍

那么怎么避免重复筛呢?我们考虑每个数最小的质因子来筛它

我们需要两个数组,prime和v,prime代表了当前已经筛出的素数,(v[x])代表(x)的最小质因数

考虑以下步骤来得出答案:
1.若当前(v[i]=0),说明 i 是素数,加入prime末尾,此时显然(v[i]=i)
2.扫描不大于(v[i])的所有质数(p),令(v[i*p]=p)

主体代码如下

const int N = 11414514 ;//臭名远扬
int v[N];
vector<int> prime;
void pri(int n)
{
    memset(v,0,sizeof(v));
    for(int i=2;i<=n;i++)
    {
        if(v[i]==0) v[i]=i,prime.push_back(i);
        for(int j=0;j<prime.size();j++)
        {
            if(prime[j]>v[i] || prime[j]>n/i) break;
            v[i*prime[j]]=prime[j];
        }
    }
}

具体证明的话是利用算术基本定理,事实上搞懂(v)的含义就能理解后面的扩展运用了

2.互质和欧拉函数

互质的定义:(forall a,b in N,gcd(a,b)=1,则称a,b互质)

欧拉函数的定义:(phi (N)表示1 - N中与N互质的数的个数)

欧拉函数的计算式:(phi (N)=N*prod_{质数p|N}(1-frac{1}{p}))

上式证明?设(p)(N)的质因子,1-N中(p)的倍数有(N/p)个,(q)也是(N)的质因子,则(q)的倍数有(N/q),按照容斥原理,1-N中不含有(p)(q)质因子的数为

(N-frac{N}{p}-frac{N}{q}+frac{N}{pq}=N(1-frac{1}{p})(1-frac{1}{q}))

推广一下,就可以得出上式了

3.线性筛+欧拉函数性质线性算欧拉函数之和

现在我们需要算(sum_{i-1}^{n}phi (i))如果我们一个一个算的话需要质因数分解,十分浪费时间,接下来介绍线性计算方式

先明确两个性质

性质1:若(p|i 那么 phi (i*p)=p*phi (i))
性质2:若(p nmid i 那么 phi (i*p)=(p-1)*phi (i))

如果你一定要问证明,那么可以参考各种算法书上的,笔者没有精力写了

知道了这两个性质,再利用线性筛,就可以线性地求欧拉函数的和了

const int N = 114514;//再次臭名昭著
int v[N],phi[N];//phi[i]代表了欧拉函数(i)的值
vector<int> prime;
void euler(int n)
{
    memset(v,0,sizeof(v));
    for(int i=2;i<=n;i++)
    {
        if(v[i]==0)
        {
            v[i]=i;
            prime.push_back(i);
            phi[i]=i-1;
        }
        for(int j=0;j<prime.size();j++)
        {
            if(prime[j]>v[i] || prime[j]>n/i) break;
            v[i*prime[j]]=phi[i]*(i%prime[j]?(prime[j]-1):prime[j]);//根据两条性质写出来的式子
        }
    }
}
程序员灯塔
转载请注明原文链接:线性筛和牠的伙伴们 : OI数论(1)
喜欢 (0)