2020-2021:teams:legal_string:线性筛_lgwza

差别

这里会显示出您选择的修订版和当前版本之间的差别。

到此差别页面的链接

--- 2020-2021:teams:legal_string:线性筛_lgwza [2020/07/08 20:16]
lgwza
+++ 2020-2021:teams:legal_string:线性筛_lgwza [2020/07/08 20:21] (当前版本)
lgwza
@@ 行 1: / 行 1: @@
-<cpp>
+====== 线性筛素数、欧拉函数、莫比乌斯函数、约数个数、约数和 ======
-</cpp>
+<code cpp>
+#include<bits/stdc++.h>
+using namespace std;
+const int N=1e7+5;
+int p[N];//质数表
+int phi[N];//欧拉函数
+int mu[N];//莫比乌斯函数
+int d[N];//约数个数
+int mi[N];//最小质因子次数
+int sigma[N];//约数和
+int mp[N];//由最小质因子组成的数的约数和
+bool b[N];//是否为质数
+int main(){
+//  freopen("num.txt","w",stdout);
+    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++){
+        if(!b[i]){
+            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;
+        }
+        for(int j=1;j<=p[0]&&i*p[j]<=N-5;j++){
+            b[i*p[j]]=1;
+            if(i%p[j]==0){
+                phi[i*p[j]]=phi[i]*p[j];
+                mu[i*p[j]]=0;
+                d[i*p[j]]=d[i]/(mi[i]+1)*(mi[i]+2);
+                mi[i*p[j]]=mi[i]+1;
+                sigma[i*p[j]]=sigma[i]/mp[i]*(mp[i]*p[j]+1);
+                mp[i*p[j]]=mp[i]*p[j]+1;
+                break;
+            }
+            else{
+                phi[i*p[j]]=phi[i]*phi[p[j]];
+                mu[i*p[j]]=-mu[i];
+                d[i*p[j]]=d[i]*d[p[j]];
+                mi[i*p[j]]=1;
+                sigma[i*p[j]]=sigma[i]*sigma[p[j]];
+                mp[i*p[j]]=p[j]+1;
+            }
+        }
+    }
+    /*
+    int n;
+    scanf("%d",&n);
+    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]);
+    }
+    */
+    return 0;
+}
+</code>
+[[https://www.cnblogs.com/yyys-/p/11285342.html|参考链接]]

2020-2021/teams/legal_string/线性筛_lgwza.1594210603.txt.gz · 最后更改: 2020/07/08 20:16 由 lgwza