数学 线性筛约数个数和,约数和

线性筛约数个数和,约数和

一,线性筛约数个数和

​ 根据唯一分解定理,可得:
\[ n=p_1^{r_1}*p_2^{r_2}*……*p_k^{r_k} \]
​ 对于每个n的约束,肯定是由以上质因数\(p_k\)相乘得来的,那么根据乘法原理,每个质因数都可以选择\(0\)\(r_k\)\(r_k+1\)个选择。

​ 那么n的约数个数即为
\[ d(n)=\prod_{i=1}^k(r_i+1) \]
筛的过程中需要保存n的最小质因子的出现个数即\(r_1\)

我们设d(i)表示\(i\)的约数个数和,num(i)表示i的最小质因数的个数。

那么就可以愉快地分情况讨论了。

(一),如果当前数是素数,那么可得:
\[ d(i)=2\\num(i)=1 \]
(二),当前数取模枚举的第j个素数不为0,即\(i%prime[j]!=0\)

​ 我们要去更新\(i*prime[j]\)的有关信息。

​ 首先我们知道\(i*prime[j]\)这个数中之前一定不包含\(prime[j]\)这个质因数。

​ 那么约数个数和就要加上\(prime[j]\)的,也就是:
\[ d(i*prime[j])=(1+r_1)*……*(1+r_k)*(1+1)\\=d(i)*d(prime[j]) \]
​ 然后对于最小质因子,因为j是从小到大枚举的,所以\(i*prime[j]\)这个数的最小质因子也就是\(prime[j]\)

​ 所以就可以得到:
\[ num(i*prime[j])=1 \]
(三),当前数取模枚举的第j个素数为0,即\(j%prime[j]==0\)

​ 依旧要去更新\(i*prime[j]\)的信息。

​ 这个时候\(i*prime(j)\)中已经存在\(prime[j]\)这个质因子了,并且\(prime[j]\)也一定是\(i*prime[j]\)的最小质因子,所以就可以得到:
\[ d(i*prime[j])=(1+r_1+1)*……*(1+r_k) \]
那么怎么从\(d(i)\)转移呢?

这个时候就可以用到我们之前维护的num(i)了。

转移也就非常简单了:
\[ d(i*prime[j])=d(i)/(num(i)+1)*(num(i)+2) \]
num也要转移,加上最小质因子\(prime[j]\)的贡献也就是:
\[ num(i*prime[j])=num(i)+1 \]
综上,就可以写出筛质因数个数的代码了。

code:

#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]*d[prime[j]];
                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+p_1+p_1^2+……+p_1^{r_1})*(1+p_2+p_2^2+……+p_2^{r_2})*……*(1+p_k+p_k^2+……+p_k^{r_k}) \]
​ 那么根据这个式子就可以开始干了。。。

​ 这个时候我们需要记录最小质因子的那一项也就是\((1+p_1+p_1^2+……+p_1^{r_1})\)

可以设\(sd(i)\)表示i的约数和。设\(num(i)\)表示我们需要记录的最小质因子的那一项(等比数列?)。

好了,开始分情况讨论吧。

(一),当前数是一个素数:

​ 易知:
\[ sd(i)=i+1\\num(i)=i+1 \]
(二),当前数取模枚举的质数不等于0

​ 易知\(i*prime[j]\)里原先没有\(prime[j]\)这一项,加上这一项之后可得:
\[ sd(i*prime[j])=sd(i)*sd(prime[j]) \]
​ (好吧我又犯懒了。。。但是思路是和上面一样的)

​ 同时更新一下\(num(i*prime[j])\)
\[ num(i*prime[j])=1+prime[j] \]
这是因为质因子从小到大枚举,那么\(i*prime[j]\)的最小质因子就应该是\(prime[j]\),那么\(num(i*prime[j])\)也就应该等于\(num(prime[j])\)

(三),当前数取模枚举的质数等于0

​ 那么\(sd(i*prime[j])\)中的第一项也就是\(num(i*prime[j])\)一定是\(prime[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\)也就是\(prime[j]\),然后再加一个一就好了。

​ 即:
\[ d(i*prime[j])=(d(i)/num(i)*(num(i)*prime[j])+1 \]
然后\(num(i*prime[j])\)依旧是\(prime[j]\)这一项,那么就是:
\[ num(i*prime[j])=num(i)*prime[j]+1 \]
这样,我们又可以开始愉快的写代码啦。。。

code:

#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;
}