首页 > 代码库 > poj 2773 Happy 2006
poj 2773 Happy 2006
Happy 2006
http://poj.org/problem?id=2773
| Time Limit: 3000MS | Memory Limit: 65536K | |
Description
Two positive integers are said to be relatively prime to each other if the Great Common Divisor (GCD) is 1. For instance, 1, 3, 5, 7, 9...are all relatively prime to 2006.
Now your job is easy: for the given integer m, find the K-th element which is relatively prime to m when these elements are sorted in ascending order.
Now your job is easy: for the given integer m, find the K-th element which is relatively prime to m when these elements are sorted in ascending order.
Input
The input contains multiple test cases. For each test case, it contains two integers m (1 <= m <= 1000000), K (1 <= K <= 100000000).
Output
Output the K-th element in a single line.
Sample Input
2006 12006 22006 3
Sample Output
135
Source
POJ Monthly--2006.03.26,static
题意：求与n互质的第k个数
性质：若a，b互质，则a+b，b互质；若a，b不互质，则a+b，b不互质
由此可以推出，与n互质的数具有周期性：
即[1,n]与n互质的数，每个+n即可得到[n+1,2n]与n互质的数，可继续推广
所以我们只需要求出第一个周期内与n互质的数
然后ans=n*周期数+第k%φ（n）个与n互质的数
所以要求出[1,n]内与n互质的所有数
有一个小处理：如果k恰好为周期数的倍数，那么取余后为0，
所以，特殊处理，将周期数-1，再在本周期内求第φ（n）个
法一：
从n*周期数+1开始枚举，判断gcd（）是否等于1，直至=1的个数达到k%φ（n）个
周期数=k/φ（n），
由于多组数据，可以欧拉筛先筛出数据范围内所有的欧拉函数值，然后O（1）使用
也可以一个一个算
我只写了第一种，Memory：5380K，Time：1579ms
#include<cstdio>#define N 1000001using namespace std;int n,k,cnt,prime[N],phi[N],t,m;bool v[N],ok;void get_euler(){ phi[1]=1; for(int i=2;i<=N;i++) { if(!v[i]) { v[i]=true; prime[++cnt]=i; phi[i]=i-1; } for(int j=1;j<=cnt;j++) { if(i*prime[j]>N) break; v[i*prime[j]]=true; if(i%prime[j]==0) { phi[i*prime[j]]=phi[i]*prime[j]; break; } phi[i*prime[j]]=phi[i]*(prime[j]-1); } }}int gcd(int a,int b){ return !b ? a:gcd(b,a%b);}int main(){ get_euler(); while(scanf("%d%d",&n,&k)!=EOF) { if(n==1) { printf("%d\n",k); continue; } ok=false; m=k/phi[n]; t=k-phi[n]*m; if(!t) m--,t=phi[n]; for(int i=n*m+1;;i++) { if(gcd(n,i)==1) t--; if(!t) { printf("%d\n",i); break; } } }}
法二：
埃氏筛法可以保留每个数是否与n互质，
所以对于每一组数据，都做一次埃氏筛法
然后从1开始枚举，枚举到第k%φ（n）个与n互质的数i，
ans=i+周期数*n
Memory:1156K，Time：16ms
它比法一快，因为可以O（1）判断是否与n互质，法一要gcd（）判断
#include<cstdio>#include<cmath>#include<cstring>using namespace std;bool check[1000001];int euler(int n)//埃式筛法模板 { int m=int(sqrt(n+0.5)); int ans=n,k=n; memset(check,0,sizeof(check)); for(int i=2;i<=m;i++) if(n%i==0) { ans=ans/i*(i-1); for(int j=1;i*j<=k;j++) check[i*j]=true; while(n%i==0) n/=i; } if(n>1) { ans=ans/n*(n-1); for(int j=1;n*j<=k;j++) check[n*j]=true; } return ans;}int main(){ int m,k,ans,cnt,t,i; while(scanf("%d%d",&m,&k)!=EOF) { ans=euler(m); cnt=0; if(k%ans==0) t=k/ans-1; else t=k/ans; k=k-ans*t; for(i=1;i<=m;i++) { if(!check[i]) cnt++; if(cnt==k) break; } printf("%d\n",i+m*t); }}
poj 2773 Happy 2006
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。