首页 > 代码库 > [POJ 2407]Relatives(欧拉函数)
[POJ 2407]Relatives(欧拉函数)
Description
Given n, a positive integer, how many positive integers less than n are relatively prime to n? Two integers a and b are relatively prime if there are no integers x > 1, y > 0, z > 0 such that a = xy and b = xz.
Input
There are several test cases. For each test case, standard input contains a line with n <= 1,000,000,000. A line containing 0 follows the last case.
Output
For each test case there should be single line of output answering the question posed above.
Sample Input
7 12 0
Sample Output
6 4
Source
Waterloo local 2002.07.01
刚开始我傻X了,本着蒟蒻的思维,照着欧拉函数的公式写了如下的代码,先筛素数然后分解质因数最后再算公式
//欧拉函数h(n)=n*(1-1/p1)*(1-1/p2)*'''''*(1-1/pk); #include <iostream> #include <cstring> #include <cstdio> #include <algorithm> #define MAXN 1010 using namespace std; bool isPrime[MAXN]; int Prime[MAXN],PriNum[MAXN],cnt=0,tot=0; void GetPrime() { cnt=0; for(int i=1;i<MAXN;i++) isPrime[i]=true; for(int i=2;i<MAXN;i++) { if(isPrime[i]) { Prime[++cnt]=i; for(int j=2*i;j<MAXN;j+=i) isPrime[j]=false; } } } void DecQualityFactor(int n) //分解质因数 { tot=0; for(int i=1;Prime[i]*Prime[i]<=n;i++) { if(n%Prime[i]==0) { PriNum[++tot]=Prime[i]; while(!(n%Prime[i])) n/=Prime[i]; } } if(n!=1) PriNum[++tot]=n; } int h(int n) { double ans=n; for(int i=1;i<=tot;i++) { ans*=(1.0-1.0/(double)PriNum[i]); } return (int)ans; } int main() { GetPrime(); while(1) { cnt=0,tot=0; memset(PriNum,0,sizeof(PriNum)); int N; cin>>N; if(!N) break; DecQualityFactor(N); cout<<h(N)<<endl; } return 0; }好吧这个代码根本没办法过,因为题目给的n的范围太大了,数组完爆内存,也就是说这题根本就不能用数组保存什么质因数和素数的。
下面才是真正的AC代码,又短又快神神哒
//欧拉函数h(n)=n*(1-1/p1)*(1-1/p2)*'''''*(1-1/pk); #include <iostream> #include <cstring> #include <cstdio> #include <algorithm> #define MAXN 1000 using namespace std; int h(int n) { int ans=n; for(int i=2;i<=n;i++) { if(n%i==0) { ans=ans/i*(i-1); n/=i; while(n%i==0) n/=i; } } return ans; } int main() { while(1) { int N; cin>>N; if(!N) break; cout<<h(N)<<endl; } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。