线性筛

貌似今天CCF倒闭了，不过还是要把学完的东西写完。
感觉数论的好多东西都被我胡乱堆……
索引：唯一分解定理与积性函数 + 线性筛素数 + 线性筛因子个数 + 线性筛因子和……

一 引入

1 唯一分解定理

唯一分解定理就是说这么一个东西：任意一个自然数都可以被写成若干质数的幂次之积，就像下面这样：

$$\forall n\in N, n = p_1^{a_1}\times p_2^{a_2}\times …\times p_k^{a_k} $$

其中$p$是质数，$a_k\in N$。

根据唯一分解定理将一个整数拆分成若干质数的次幂之积的过程，被称作分解质因数。

2 积性函数

对于一个函数$f(x)$，若对任意互质的两数$a,b$，有$f(a\times b) = f(a)\times f(b)$，则称$f(x)$为积性函数。
例如：欧拉函数$\varphi(x)$（定义为小于$x$的与$x$互质的数的个数），莫比乌斯函数等都是积性函数。
积性函数总是可以通过线性的筛法求得的。

---

二 线性筛素数

1 理论

实际上也叫欧拉筛。其实在OI模板中有一份关于筛素数的代码，实际上那个是Eratosthenes筛，这个是$O(n\log\log n)$，并不是严格的线性筛法。

欧拉筛的想法是：对于每个合数，只用它的一个质因数（实际上它的是最小质因子）把它筛掉。因此一个合数只会被筛一次，也就保证了严格的线性。

实际的做法是：用一个数$i$和小于$i$的且与$i$互质的所有质数（已经筛出）$\text{prime}[j]$去筛$i\times \text{prime}[j]$。为什么这样做呢？前面说一个数只被它的最小质因子筛掉，而当$i$与$ \text{prime}[j]$不互质时，假设存在一个比$\text{prime}[j]$小的质数$\text{prime}[k]$，那么$i\times \text{prime}[k]$一定是$\text{prime}[j]$的倍数。换言之此时$\text{prime}[j]$并不一定是$i\times \text{prime}[j]$的最小质因子。实际上这个这个结论是总成立的，即此时$\text{prime}[j]$不是$i\times \text{prime}[j]$的最小质因子。因此只需枚举到$\text{prime}[j]$与$i$不互质就好了。

具体的做法请见代码。

2 代码

const int CN = 1e7+7;
int n,m;
int prime[CN]; bool not_prime[CN]; //标记一个数字不是素数

//线性筛素数
not_prime[1] = true;
for(int i=2;i<=n;i++){
    if(!not_prime[i]) prime[++prime[0]] = i; //记录素数
    for(int j=1;j<=prime[0] && i*prime[j]<=n;j++){
        not_prime[i*prime[j]] = true; //筛，prime[j] 总是 i 的最小质因子
        if(!(i % prime[j])) break; //欧拉筛之所以线性之处
        /*
        i mod prime[i] = 0, 即 prime[j] 是 i 的质因子
        也就说明对于其它的质数 prime[k], i*prime[k] 总会是 prime[j] 的倍数
        那么就不需要继续用 prime[j] 继续往下筛了
        */
    }
}

---

三 线性筛因子个数

1 理论

我们用$d(x)$表示$x$的因子个数。$d()$函数也是积性函数，因此可以线性筛。

若将$x$分解质因子，得$x = p_1^{a_1}\times p_2^{a_2}\times …\times p_k^{a_k} $。每个质因子$p_i$可以产生$a_i+1$种不同的因子，即$p_i^0,p_i^1,…,p_i^{a_i}$。而任意若干上述“不同的因子”相乘又会得到新的因子，因此$x$共有$(a_1+1)·(a_2+1)·…·(a_k+1)$个因子，即$d(x) = (a_1+1)(a_2+1)…(a_k+1)$。

实际上可以表示成$d(x) = \prod\limits_{i=1}^k a_i+1$。

然后考虑如何线性筛。对于上面的欧拉筛代码，考虑在筛$i\times \text{prime}[j]$时求出$d(i\times \text{prime}[j])$。
可以分类讨论：

若$i$与$\text{prime}[j]$互质，则根据积性函数的定义可得$d(i\times \text{prime}[j]) = d(i)\times d(\text{prime}[j])$。

若$i$与$\text{prime}[j]$不互质，首先$\text{prime}[j]$一定是$i$的最小质因子，则根据$i = p_1^{a_1}\times p_2^{a_2}\times …\times p_k^{a_k} $，可知$\text{prime}[j]$会是质因数分解里面最小的那个质因子，也就是$p_1$。于是得$i\times \text{prime}[j] = i·p_1 = p_1^{a_1+1}\times p_2^{a_2}\times …\times p_k^{a_k}$。原来的$d(i) = (a_1+1)(a_2+1)…(a_k+1)$，现在变成了$d(i) \times \text{prime}[j] = (a_1+2)(a_2+1)…(a_k+1)$，于是可知$d(i\times \text{prime}[j]) = d(i)/(a_1+1) \times(a_1+2) $。这个最小质因子的指数$a_1$可以记录下来，设它是$m_i$，则有$d(i\times \text{prime}[j]) = d(i)/(m_i+1) \times (m_i+2) $。

这个$m_i$也是可以线性推广到$m_{i\times \text{prime}[j]}$的。对于情况一，既然$\text{prime}[j]$是$i\times \text{prime}[j]$的最小质因子，且又只乘了一个$\text{prime}[j]$，显然有$m_{i\times \text{prime}[j]} = 1$；而对于情况二，从$i$变成$i\times \text{prime}[j]$，实际上是最小质因子又被乘了一遍，即它的指数又被加上了$1$，所以有$m_{i\times \text{prime}[j]} = m_i+1$。

于是我们就找到了一种线性筛因子个数的方法。

2 代码

const int CN = 1e7+7;
int n,m;
int prime[CN]; bool not_prime[CN];
int d[CN],mi[CN]; //mi[x] 记录 x 的质因数分解中最小的质因子的指数

//线性筛因子个数d()
not_prime[1] = true;
d[1] = 1; mi[1] = 0; // 1 仅有 1 个因子，质因数分解为任意负数的零次方
for(int i=2;i<=n;i++){
    if(!not_prime[i]){ //记录素数
        prime[++prime[0]] = i;
        d[i] = 2; mi[i] = 1; //素数仅有两个因子，质因数分解为自身的一次方
    }
    for(int j=1;j<=prime[0] && i*prime[j]<=n;j++){
        /*prime[j] 一定是 i*prime[j] 的最小质因子*/
        not_prime[i*prime[j]] = true;
        if(i % prime[j]){ //互质时，根据积性函数的特性推出
            d[i*prime[j]] = d[i]*d[prime[j]];
            mi[i*prime[j]] = 1;
        }
        else{ //不互质
            d[i*prime[j]] = d[i]/(mi[i]+1) * (mi[i]+2);
            mi[i*prime[j]] = mi[i]+1;
            break; 
        }
    }
}

---

四 线性筛因子和

1 理论

设$D(x)$表示$x$的所有因子之和。$D()$函数同样是积性函数，可以进行线性筛。

同样，先推通项公式（貌似也可以叫它解析式…）。把$x$分解质因数，得$x = p_1^{a_1}\times p_2^{a_2}\times …\times p_k^{a_k}$。$x$的所有因子应该是什么呢？同上所述，所有的形如$p_i^j (j\in [0,a_i],i\in [1,k])$的数都可以作为$x$的因子，但是这并不是全部。实际上，在其中任取若干个数$p_{i1}^{j1},p_{i2}^{j2},…$相乘，所得的积也会是$x$的一个因子。因此把所有可能的因子分组并根据乘法原理相乘，就得到$D(x) = (1+p_1^1+p_1^2+…+p_1^{a_1})(1+p_2^1+p_2^2+…+p_2^{a_2})…(1+p_k^1+p_k^2+…+p_k^{a_k})$。

也就是$D(x) = \prod\limits_{i=1}^k \sum\limits_{j=0}^{a_i} p_i^j$。

然后再考虑线性筛。设$\text{prime}[j]$是$i$的最小质因子，枚举$i$，考虑$O(1)$推出$D(i\times \text{prime}[j])$。首先$\text{prime}[j]$与$i$互质时显然可以直接相乘得到，不再多说。

不互质呢？观察$D(i)$和$D(i\times \text{prime}[j])$的通项表达式有什么区别？实际上是$D(i\times \text{prime}[j]) = D(i)/(1+p_1^1+p_1^2+…+p_1^{a_1}) \times (1+p_1^1+p_1^2+…+p_1^{a_1+1})$。同样把后面的那个东西设作$w_i$，得到$D(i\times \text{prime}[j]) = D(i)/w_i \times w_{i\times \text{prime}[j]}$。

此时实际上$w_{i\times \text{prime}[j]} = w_{i}\times \text{prime}[j] +1$；而对于互质的情况，有$w_{i\times \text{prime}[j]} = \text{prime}[j] +1$。

因此我们找到了一种线性筛因子和的方法。

2 代码

const int CN = 1e7+7;
int n,m;
int prime[CN]; bool not_prime[CN];
int D[CN],w[CN];

//线性筛因子和D()
not_prime[1] = true;
D[1] = 1; w[1] = 1; 
for(int i=2;i<=n;i++){
    if(!not_prime[i]){ //记录素数
        prime[++prime[0]] = i;
        D[i] = i+1; w[i] = i+1; //两个因子: 自身(i) + 1
    }
    for(int j=1;j<=prime[0] && i*prime[j]<=n;j++){
        /*prime[j] 一定是 i*prime[j] 的最小质因子*/
        not_prime[i*prime[j]] = true;
        if(i % prime[j]){ //互质时，根据积性函数的特性推出
            D[i*prime[j]] = D[i]*D[prime[j]];
            w[i*prime[j]] = prime[j]+1; //即最小质因子的零次方和一次方
        }
        else{ //不互质
            D[i*prime[j]] = D[i]/w[i] * (w[i]*prime[j]+1);
            w[i*prime[j]] = w[i]*prime[j]+1;
            break; 
        }
    }
}