2020-2021:teams:legal_string:线性筛_lgwza
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:legal_string:线性筛_lgwza [2020/07/08 20:17] lgwza |
2020-2021:teams:legal_string:线性筛_lgwza [2020/07/08 20:21] (当前版本) lgwza |
||
|---|---|---|---|
| 行 1: | 行 1: | ||
| + | ====== 线性筛素数、欧拉函数、莫比乌斯函数、约数个数、约数和 ====== | ||
| + | |||
| <code cpp> | <code cpp> | ||
| #include<bits/stdc++.h> | #include<bits/stdc++.h> | ||
| using namespace std; | using namespace std; | ||
| const int N=1e7+5; | const int N=1e7+5; | ||
| - | int p[N];//ÖÊÊý±í | + | int p[N];//质数表 |
| - | int phi[N];//Å·Àº¯Êý | + | int phi[N];//欧拉函数 |
| - | int mu[N];//Ī±ÈÎÚ˹º¯Êý | + | int mu[N];//莫比乌斯函数 |
| - | int d[N];//Ô¼Êý¸öÊý | + | int d[N];//约数个数 |
| - | int mi[N];//×îСÖÊÒò×Ó´ÎÊý | + | int mi[N];//最小质因子次数 |
| - | int sigma[N];//Ô¼ÊýºÍ | + | int sigma[N];//约数和 |
| - | int mp[N];//ÓÉ×îСÖÊÒò×Ó×é³ÉµÄÊýµÄÔ¼ÊýºÍ | + | int mp[N];//由最小质因子组成的数的约数和 |
| - | bool b[N];//ÊÇ·ñΪÖÊÊý | + | bool b[N];//是否为质数 |
| int main(){ | int main(){ | ||
| - | // freopen("num.txt","w",stdout); | + | // freopen("num.txt","w",stdout); |
| - | b[0]=b[1]=phi[1]=mu[1]=d[1]=mi[1]=sigma[1]=mp[1]=1; | + | b[0]=b[1]=phi[1]=mu[1]=d[1]=mi[1]=sigma[1]=mp[1]=1; |
| - | for(int i=2;i<=N-5;i++){ | + | for(int i=2;i<=N-5;i++){ |
| - | if(!b[i]){ | + | if(!b[i]){ |
| - | p[++p[0]]=i;phi[i]=i-1;mu[i]=-1;d[i]=2; | + | p[++p[0]]=i;phi[i]=i-1;mu[i]=-1;d[i]=2; |
| - | mi[i]=1;sigma[i]=1+i;mp[i]=1+i; | + | mi[i]=1;sigma[i]=1+i;mp[i]=1+i; |
| - | } | + | } |
| - | for(int j=1;j<=p[0]&&i*p[j]<=N-5;j++){ | + | for(int j=1;j<=p[0]&&i*p[j]<=N-5;j++){ |
| - | b[i*p[j]]=1; | + | b[i*p[j]]=1; |
| - | if(i%p[j]==0){ | + | if(i%p[j]==0){ |
| - | phi[i*p[j]]=phi[i]*p[j]; | + | phi[i*p[j]]=phi[i]*p[j]; |
| - | mu[i*p[j]]=0; | + | mu[i*p[j]]=0; |
| - | d[i*p[j]]=d[i]/(mi[i]+1)*(mi[i]+2); | + | d[i*p[j]]=d[i]/(mi[i]+1)*(mi[i]+2); |
| - | mi[i*p[j]]=mi[i]+1; | + | mi[i*p[j]]=mi[i]+1; |
| - | sigma[i*p[j]]=sigma[i]/mp[i]*(mp[i]*p[j]+1); | + | sigma[i*p[j]]=sigma[i]/mp[i]*(mp[i]*p[j]+1); |
| - | mp[i*p[j]]=mp[i]*p[j]+1; | + | mp[i*p[j]]=mp[i]*p[j]+1; |
| - | break; | + | break; |
| - | } | + | } |
| - | else{ | + | else{ |
| - | phi[i*p[j]]=phi[i]*phi[p[j]]; | + | phi[i*p[j]]=phi[i]*phi[p[j]]; |
| - | mu[i*p[j]]=-mu[i]; | + | mu[i*p[j]]=-mu[i]; |
| - | d[i*p[j]]=d[i]*d[p[j]]; | + | d[i*p[j]]=d[i]*d[p[j]]; |
| - | mi[i*p[j]]=1; | + | mi[i*p[j]]=1; |
| - | sigma[i*p[j]]=sigma[i]*sigma[p[j]]; | + | sigma[i*p[j]]=sigma[i]*sigma[p[j]]; |
| - | mp[i*p[j]]=p[j]+1; | + | mp[i*p[j]]=p[j]+1; |
| - | } | + | } |
| - | } | + | } |
| - | } | + | } |
| - | /* | + | /* |
| - | int n; | + | int n; |
| - | scanf("%d",&n); | + | scanf("%d",&n); |
| - | for(int i=2;i<=n;i++){ | + | for(int i=2;i<=n;i++){ |
| - | printf("Êý£º%d ÊÇ·ñΪÖÊÊý£º%d phiÖµ£º%d muÖµ£º%d Ô¼Êý¸öÊý£º%d Ô¼ÊýºÍ£º%d\n",i,b[i]?0:1,phi[i],mu[i],d[i],sigma[i]); | + | printf("数：%d 是否为质数：%d phi值：%d mu值：%d 约数个数：%d 约数和：%d\n",i,b[i]?0:1,phi[i],mu[i],d[i],sigma[i]); |
| - | } | + | } |
| - | */ | + | */ |
| - | return 0; | + | return 0; |
| } | } | ||
| </code> | </code> | ||
| + | |||
| + | [[https://www.cnblogs.com/yyys-/p/11285342.html|参考链接]] | ||
2020-2021/teams/legal_string/线性筛_lgwza.1594210667.txt.gz · 最后更改: 2020/07/08 20:17 由 lgwza
