约数定理（two）

筛约数个数和

理论基础：

1、对n质因数分解，n=p1^k1 * p2^k2 * p3^k3 ……

则n的约数个数为(k1+1)*(k2+1)*(k3+1)……

2、线性筛素数时，用i和素数pj来筛掉 i*pj，

其中pj一定是i*pj的最小素因子

如果i是pj的倍数，pj也是i的最小素因子

设t[i] 表示i的约数个数，e[i] 表示i的最小素因子的个数

A、如果i是质数，t[i]=2,e[i]=1

B、如果i不是质数，枚举已有的质数pj

i*pj的最小素因子是pj

1、如果i是pj的倍数那么e[i]即为i中包含的pj的个数，所以i*pj中包含的pj的个数为e[i]+1

所以e[i*pj]=e[i]+1,t[i*pj]=t[i]/(e[i]+1)*(e[i]+2)

2、如果i不是pj的倍数，e[i*pj]=1,t[i*pj]=t[i]*t[pj]（积性函数的性质）=t[i]*2（素数的约数个数=2）

 #include<cstdio>

 using namespace std;

 #define N 1000001

 bool vis[N];

 int prime[N];

 int t[N],e[N];

 int main()

 {

     int n;

     scanf("%d",&n);

     int cnt=;

     t[]=;

     for(int i=;i<=n;++i)

     {

         if(!vis[i])

         {

             prime[++cnt]=i;

             t[i]=;

             e[i]=;

         }

         for(int j=;j<=cnt;++j)

         {

             if(i*prime[j]>n) break;

             vis[i*prime[j]]=true;

             if(i%prime[j]==)

             {

                 t[i*prime[j]]=t[i]/(e[i]+)*(e[i]+);

                 e[i*prime[j]]=e[i]+;

                 break;

             }

             else

             {

                 t[i*prime[j]]=t[i]*;

                 e[i*prime[j]]=;

             }

         }

     }

     long long ans=;

     for(int i=;i<=n;++i) ans+=t[i];

     printf("%lld",ans);

 }

筛约数和

t[i] 表示i的约数和

e[i] 表示i的约数中，不能被i的最小素因子整除的约数和

A、i是质数，t[i]=i+1,e[i]=1

B、i不是质数

i*pj的最小素因子是pj

1、如果i不是pj的倍数，那么i的所有约数中，必然没有pj的倍数

可以用反证法证明这个：设x是i的约数，且x是pj的倍数，

那么 x=pj*b，i=x*a=pj*b*a

即i是pj的b*a倍，与i不是pj的倍数相矛盾

令S表示i的约数集，S’表示i的约数翻pj倍后的数的集合

则S∩S’=∅，则S和S’中无重复元素

所以t[i*pj]=S+S'=t[i]+t[i]*pj=t[i]*(pj+1)

S’中的所有元素都能整除pj，所以e[i*pj]=t[i]

2、如果i是pj的倍数，那么S和S’必有交集T

T=S中pj的倍数

所以i*pj的约数和要去除交集T

那么t[i*pj]=S+S'-T=S'+S-T=t[i]*pj+e[i]

因为pj既是i的最小素因子，有事i*pj的最小素因子

所以e[i*pj]=e[i]

 #include<cstdio>

 typedef long long LL;

 #define N 100001

 int prime[N];

 bool vis[N];

 LL t[N],e[N];

 int main()

 {

     int n;

     scanf("%d",&n);

     int cnt=;

     for(int i=;i<=n;++i)

     {

         if(!vis[i])

         {

             prime[++cnt]=i;

             t[i]=i+;

             e[i]=;

         }

         for(int j=;j<=cnt;++j)

         {

             if(prime[j]*i>n) break;

             vis[prime[j]*i]=true;

             if(i%prime[j]==)

             {

                 t[i*prime[j]]=t[i]*prime[j]+e[i];

                 e[i*prime[j]]=e[i];

                 break;

             }

             t[i*prime[j]]=t[i]*(prime[j]+);

             e[i*prime[j]]=t[i];

         }

     }

     LL ans=;

     for(int i=;i<=n;++i) ans+=t[i];

     printf("%lld",ans);

 }

参考博客：

百度百科

https://blog.csdn.net/Anxdada/article/details/76691441

http://www.cnblogs.com/TheRoadToTheGold/

巴特西

约数定理（two）

筛约数个数和

筛约数和

最新文章

热门文章