線性篩求約數個數與約數和

線性篩，顧名思義，就是歐拉篩，線上性時間内可以求出答案，也就是\(O(N)\)的時間，非常牛\(X\)的效率。

一、約數個數

根據數字唯一分解定理，設

\[\LARGE n=p_1^{r_1}*p_2^{r_2}*p_3^{r_3}*...*p_k^{r_k}

對于每個\(n\)的約數，一定是由以上質因數\(p_1 \sim p_k\)相乘而來，根據乘法原理，每個質因數都可以選擇\(0\)到\(r_i\)這\(r_i+1\)個選擇。

\(n\)的約數個數即為

\[\LARGE d(n)=(r_1+1)\times (r_2+1) \times ... \times (r_k+1) =\prod_{i=1}^k(r_i+1)

篩的過程中需要儲存\(n\)的最小質因子的出現個數即\(r_1\),原因後面會說明：

\(d[i]\)記錄\(i\)的約數個數
\(num[i]\)記錄\(i\)的最小質因數個數

分情況讨論:

(一)、\(i\)是質數

\[\large \left\{\begin{matrix}

d[i]=2 & \\

num[i]=1 &

\end{matrix}\right.

\(d[i]\):\(i\)是質數，是以約數隻有\(1\)和自身,約數個數為\(2\)
\(num[i]\):\(i\)是質數，最小質因子就是自己，個數是\(1\)

(二)、\(i\)取模枚舉的第\(j\)個質數為\(0\)， \(primes[j]\)整除\(i\)

\(Q1:\)我們在研究哪些數字之間的遞推關系？

\(A:\)既然是遞推，一般都是已知小的推出大的，這裡應該是已知\(d[i]\)推出\(d[i*primes[j]]\)的值。

\(Q2\):\(d[i*primes[j]]\)是啥？

\(A\): \(primes[j]\)是\(i\)的因子，\(i*primes[j]\)唯一分解不會産生新的質因子,依然是\(p_1,p_2,...p_k\)

\(primes[j]\)從小到大枚舉，是以一定是\(i\)的最小質因子！是以\(p_1^{r_1+1}\),按唯一分解定理展開:

\[\large d[i*primes[j]]=(1+r_1+1)*......*(1+r_k)

\(Q3\):\(d[i∗primes[j]]\)怎麼從\(d[i]\)轉移？

這個時候就可以用到我們之前維護的\(num[i]\)了。

轉移也就非常簡單了：

\[\large d[i∗primes[j]]=d[i]/(num[i]+1)∗(num[i]+2)

解釋：

\[\large \left\{\begin{matrix}

d(i)=(1+r_1)*......*(1+r_k) & ①\\

d(i*primes[j])=(1+r_1+1)*......*(1+r_k) & ②\\

\end{matrix}\right.

使用瞪眼大法(觀察法)，找出兩者之間的遞推關系，很明顯，就是 ①式除以\(1+r_1\),再乘上\(1+r_1+1\)即可轉化為 ②式,這下明白為什麼要記錄\(num[i]\)最小質因子的個數了吧~

\(Q4\):那麼\(num[i∗primes[j]]\)是不是也需要從\(num[i]\)進行轉移呢？

\(A\):\(num[i*primes[j]]\)也要轉移，加上最小質因子\(primes[j]\)的貢獻也就是：

\[\large num[i∗primes[j]]=num[i]+1

(三)、目前數取模枚舉的第\(j\)個質數不為\(0\)，即 \(primes[j]\) 不能整除 \(i\)

首先我們知道\(i∗primes[j]\)這個數中之前一定不包含\(primes[j]\)這個質因數,

那麼約數個數要加上\(prime[j]\)的，也就是：

\[\large d[i*primes[j]]=(1+r_1)*...*(1+r_k)*(1+1) \\

=d[i]*2=d[i]*d[primes[j]] \]

然後對于最小質因子，因為\(j\)是從小到大枚舉的，是以\(i∗primes[j]\)這個數的最小質因子也就是\(primes[j]\)

是以就可以得到：

\[\large num[i*primes[j]]=1

綜上，就可以寫出篩質因數個數的代碼了:

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 1010;

int primes[N], cnt; // primes[]存儲所有素數
bool st[N];         // st[x]存儲x是否被篩掉
int d[N];           // d[x]表示x的約數個數
int num[N];         // num[x]表示x的最小質因數的個數
int n;

//歐拉篩法+求約數個數
void get_primes(int n) {
    d[1] = 1; // 1的約數隻有1個,這個比較特殊

    for (int i = 2; i <= n; i++) {
        if (!st[i]) {
            primes[cnt++] = i;
            // i是質數
            d[i] = 2;   //約數個數是2個，一個是1，另一個是i
            num[i] = 1; //最小質因子個數是1，最小質因子就是自己i
        }

        for (int j = 0; i * primes[j] <= n; j++) {
            st[i * primes[j]] = true;
            if (i % primes[j] == 0) {
                d[i * primes[j]] = d[i] / (num[i] + 1) * (num[i] + 2);
                num[i * primes[j]] = num[i] + 1;
                break;
            } else {
                // d[i * primes[j]] = d[i] * d[primes[j]]; 等價于下面的代碼　
                d[i * primes[j]] = d[i] * 2;
                num[i * primes[j]] = 1;
            }
        }
    }
}

int main() {
    scanf("%d", &n);
    get_primes(n);
    //輸出1~n之間所有數字的約數個數
    for (int i = 1; i <= n; i++) printf("%d %d\n", i, d[i]);
    return 0;
}

二、約數和

設\(sd[i]\)表示\(i\)的約數和

根據算數基本定理得：約數和參考連結

\[\large sd[n]=(p_1^0+p_1^1+p_1^2+……+p_1^{r_1})∗(p_2^0+p_2^1+p_2^2+……+p_2^{r_2})∗……∗(p_k^0+p_k^1+p_k^2+……+p_k^{r_k})

那麼根據這個式子就可以開始幹了。。。

設\(num[i]\)表示最小質因子的那一項:

\[\large num[i]= p_1^0+p_1^1+p_1^2+……+p_1^{r_1}

分情況讨論:

(一)、\(i\)是質數

\[\large sd[i]=num[i]=i+1

解釋:

\(i\)是質數，它的約數隻有自己和\(1\),約數和是\(i+1\)
\(i\)是質數，質因子分解也隻能分解出自己，\(sd[i]=i^0+i^1=1+i\)

(二)、\(i\)取模枚舉的質數\(primes[j]\)不為0,即\(primes[j]\)不能整除\(i\)

注：下面的讨論中使用\(p_j\)代替\(primes[j]\)

\(i∗p_j\)裡原先沒有\(p_j\)這一項，加上這一項之後：

\[\large \because sd[i]=(p_1^0+p_1^1+p_1^2+……+p_1^{r_1})∗(p_2^0+p_2^1+p_2^2+……+p_2^{r_2})∗……∗(p_k^0+p_k^1+p_k^2+……+p_k^{r_k})

\[\large \because sd[i*p_j]=(p_1^0+p_1^1+p_1^2+……+p_1^{r_1})∗(p_2^0+p_2^1+p_2^2+……+p_2^{r_2})∗……∗(p_k^0+p_k^1+p_k^2+……+p_k^{r_k})*(p_j^0+p_j^1)

\(\large \because p_j\) 是質數 \(\large \therefore sd[p_j]=p_j^0+p_j^1\)

\(\large \therefore sd[i*p_j]=sd[i]*sd[p_j]\) 注：積性函數

同時更新一下\(num[i∗p_j]\)

\[\large num[i∗p_j]=num[p_j]=p_j^0+p_j^1=1+p_j

解釋：

因為質因子從小到大枚舉，那麼\(i∗p_j\)的最小質因子就應該是\(p_j\)，那麼\(num[i∗p_j]\)也就應該等于\(num[p_j]\)

(三)、\(i\)取模枚舉的質數\(j\)為0,即 \(primes[j]\)整除\(i\)

那麼\(sd[i∗p_j]\)中的第一項也就是\(num[i∗p_j]\)也一定是\(p_j\)的第一項

解釋：(等比數列變形小技巧)

\(1+p_i+p_i^2+……+p_i^{r_i}\)這個時候要變成\(1+p_i+p_i^2+……+p_i^{r_i}+p_i^{r_i+1}\)，那麼隻需要所有的都乘以一個\(p_i\)，然後再加一個\(1\)就好了。

\[\large (1+p_i+p_i^2+……+p_i^{r_i})*p_i+1= \\

1+p_i+p_i^2+……+p_i^{r_i}+p_i^{r_i+1}\]

結論：

\[\large num[i∗p_j]=num[i]∗p_j+1

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

const int N = 1e3 + 10;

int primes[N], cnt;
bool st[N];

int num[N]; //最小質因子p1組成的等比序列 p1^0+p1^1+...+p1^r1
int sd[N]; //約數和

int n;

void get_primes(int n) {
    sd[1] = 1; // 1的約數隻有自己，約數和是1

    for (int i = 2; i <= n; i++) {
        if (!st[i]) {
            primes[cnt++] = i;
            //質數
            sd[i] = num[i] = i + 1; // 1和自身是約數，約數和為i+1; 同時因為i是質數，是以隻有一個分拆項,并且分拆項内容=pj^0+pj^1=1+pj=1+i
        }
        for (int j = 0; primes[j] * i <= n; j++) {
            st[i * primes[j]] = true;

            if (i % primes[j]) {
                sd[i * primes[j]] = sd[i] * sd[primes[j]]; //積性函數
                num[i * primes[j]] = primes[j] + 1;
            } else {
                sd[i * primes[j]] = sd[i] / num[i] * (num[i] * primes[j] + 1);
                num[i * primes[j]] = num[i] * primes[j] + 1;
                break;
            }
        }
    }
}

int main() {
    scanf("%d", &n);
    get_primes(n);
    //約數和要不要自己本身,這裡是不想要自己本身
    for (int i = 1; i <= n; i++) printf("%d ", sd[i] - i);
    puts("");
    return 0;
}

線性篩求約數個數與約數和