数学 线性筛约数个数和,约数和
2019-11-30

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

一,线性筛约数个数和

​ 根据唯一分解定理,可得:[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\um(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",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\um(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",i,sd[i]); return 0;}, 1, 0, 9);