首页 > 代码库 > 欧拉函数线性筛法
欧拉函数线性筛法
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 #define lli long long int 6 using namespace std; 7 const int MAXN=10000001; 8 void read(int &n) 9 {10 char c=‘+‘;int x=0;bool flag=0;11 while(c<‘0‘||c>‘9‘){c=getchar();if(c==‘-‘)flag=1;}12 while(c>=‘0‘&&c<=‘9‘)13 x=(x<<1)+(x<<3)+c-48,c=getchar();14 flag==1?n=-x:n=x;15 }16 int n,m;17 bool check[MAXN];18 int prime[MAXN];19 int phi[MAXN];20 int tot=0;21 int main()22 {23 cin>>n;24 phi[1]=1;25 for(int i=2;i<=n;i++)26 {27 if(!check[i])28 prime[++tot]=i,phi[i]=i-1;// 只有i与它互质 29 for(int j=1;j<=tot;j++)30 {31 if(i*prime[j]>n)32 break;33 check[i*prime[j]]=1;34 if(i%prime[j]==0)35 {36 phi[i*prime[j]]=phi[i]*prime[j]; 37 break;38 }39 else40 phi[i*prime[j]]=phi[i]*(prime[j]-1);41 }42 }43 printf("%d\n",phi[n]);44 return 0;45 }
注意 if(i%prime[j]==0)
不要写成if(!i%prime[j])
欧拉函数线性筛法
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。