首页 > 代码库 > 欧拉函数phi值的计算模板
欧拉函数phi值的计算模板
求小于n且与n互质的整数的个数。告诉你n的唯一分解式
我们可以运用容斥原理，先分别减去是p1,p2,p3..pn的倍数，再加上同时是他们素因子的个数，再减去3个……以此类推即可。
我们可以化简一下公式：f(x)=x*(1-1/p1)*(1-1/p2).....,其中p1，p2.....是n的素因子。
这就是大名鼎鼎的欧拉函数，然后我们可以用编程轻松的解决这个问题
运用求质数的方法，每次找到一个素因子，然后将它除净，就可以保证找到的因子都是素数
#include<bits/stdc++.h>using namespace std;int ans,ans2;int n;void Find(){ int m=int(sqrt(n)+0.5); ans=n; for(int i=2;i<=m;i++) if(n%i==0) { ans=ans/i*(i-1);//注意运算的顺序,不然有可能超出int的范围 while(n%i==0) n/=i; } if(n>1) ans=ans/n*(n-1); }int main(){ cin>>n; Find(); cout<<ans<<endl; return 0;} 我们还可以利用类似筛素数的方法求出1-n所有欧拉函数的phi值~
#include<bits/stdc++.h>using namespace std;int ans,ans2;int n;int phi[1000];void Find(){ phi[1]=1; for(int i=2;i<=n;i++)if(!phi[i]) { for(int j=i;j<=n;j+=i) { if(!phi[j]) phi[j]=j; phi[j]=phi[j]/i*(i-1); } }}int main(){ cin>>n; Find(); return 0;}
欧拉函数phi值的计算模板
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。