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

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]);//根据两条性质写出来的式子
        }
    }
}