參考博客
參考博客
參考博客

這個講的挺好
預備知識點：
大于1的數n可以分解質因數：
n=p1^a1×p2^a2×p3^a3*…*pk^a
n的約數的個數是(a1+1) * (a2+1) * (a3+1)…(ak+1)
我們先用線性篩來篩出素數

bool mark[maxn]; int prim[maxn]; int cnt; void initial() {cnt=0;for (int i=2 ; i<N ; ++i){if (!mark[i])prim[cnt++]=i;//存放素數for (int j=0 ; j<cnt && i*prim[j]<N ; ++j){mark[i*prim[j]]=1;//標記為素數if (!(i%prim[j]))break;}} }

求約數個數

n的約數的個數是(a1+1) * (a2+1) * (a3+1)…(ak+1)
我們可以用線性篩篩出當前n的約數個數
證明：
d[i]表示i的約數的個數
num[i]表示i的最小素因子的個數
prim[i]表示第i個素數
分下列情況：

i為質數
因為i為質數，所以素因子只有本身，且指數為1
所以num[i]=1,d[i]=2(1和本身)

i%prim[j]!=0
說明i不包含prim[j]這個素因子，但是i*prim[j]包含一個素因子prim[j]，所以
d(i?prime[j])=(1+r1)?……?(1+rk)?(1+1)=d[i] * d[prim[j]] = d[i] * 2
而且因為我們是從小到大枚舉，所以當前的prim[j]必然是i * prim[j]的最小素因子，所以num[i * prim[j]] = 1

i%prim[j]= =0
i中包含prim[j]，且為i的最小素因子
d(i?prime[j])=(1+r1+1)?……?(1+rk)
d(i?prime[j])=d(i)/(num(i)+1)?(num(i)+2)
num(i?prime[j])=num(i)+1

#include <iostream> #include <cstdio> #include <cstring>using namespace std;const int wx=1017;int isprime[wx],prime[wx],d[wx],num[wx]; int tot,n,m;inline int read(){int sum=0,f=1; char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();}while(ch>='0'&&ch<='9'){sum=(sum<<1)+(sum<<3)+ch-'0'; ch=getchar();}return sum*f; }void Euler(){memset(isprime,1,sizeof isprime); d[1]=1;for(int i=2;i<=n;i++){if(isprime[i]){prime[++tot]=i;d[i]=2;num[i]=1;}for(int j=1;j<=tot&&i*prime[j]<=n;j++){isprime[i*prime[j]]=0;if(i%prime[j]==0){d[i*prime[j]]=d[i]/(num[i]+1)*(num[i]+2);num[i*prime[j]]=num[i]+1; break;}else{d[i*prime[j]]=d[i]*2;num[i*prime[j]]=1;}}} }int main(){n=read(); Euler();for(int i=1;i<=n;i++)printf("%d %d\n",i,d[i]);return 0; }

線性篩約數和

我們用sd(i)表示i的約數和
根據算數基本定理：
sd(n)=(1+p1+p²1+……+p^r11)?(1+p2+p²2+……+p^r22)?……?(1+pk+p²k+……+p^rkk)
最小質因子的那一項是(1+p1+p²1+……+p^r11)
我們用num[i]來表示最小質因子的那一項
證明：
和上面一樣分類討論：

i為素數
sd(i)=i+1num(i)=i+1

i%prim[j] ! = 0
i?prime[j]里原先沒有prime[j]這一項，加上后：
sd(i?prime[j])=sd(i)?sd(prime[j])
num(i?prime[j])=1+prime[j]
（大體思路如上）

i%prim[j] = =0
d(i?prime[j])=(d(i)/num(i)?(num(i)?prime[j])+1
num(i?prime[j])=num(i)?prime[j]+1

代碼：

#include <iostream> #include <cstdio> #include <cstring>using namespace std;const int wx=1017; inline int read(){int sum=0,f=1; char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();}while(ch>='0'&&ch<='9'){sum=(sum<<1)+(sum<<3)+ch-'0'; ch=getchar();}return sum*f; }int isprime[wx],sd[wx],num[wx],prime[wx]; int n,tot;void Euler(){memset(isprime,1,sizeof isprime); sd[1]=1;for(int i=2;i<=n;i++){if(isprime[i]){prime[++tot]=i;sd[i]=1+i; num[i]=1+i;}for(int j=1;j<=tot&&prime[j]*i<=n;j++){isprime[i*prime[j]]=0;if(i%prime[j]!=0){sd[i*prime[j]]=sd[i]*sd[prime[j]];num[i*prime[j]]=prime[j]+1;}else{sd[i*prime[j]]=sd[i]/num[i]*(num[i]*prime[j]+1);num[i*prime[j]]=num[i]*prime[j]+1; break;}}} }int main(){n=read(); Euler();for(int i=1;i<=n;i++)printf("%d %d\n",i,sd[i]);return 0; }

總結

以上是生活随笔為你收集整理的[数论]线性筛——约数个数与约数和的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。