首页 > 移动平台 > 详细

【欧几里德算法】POJ2773-HAPPY 2006

时间:2016-05-31 23:50:32      阅读:333      评论:0      收藏:0      [点我收藏+]

【题目大意】

求与n互质的第k个数。

【思路】

先求出小于k且与n互质的数,再利用gcd(bt+a,b)=gcd(a,b)的性质求解,效率低。枚举与n互质的数的效率是O(nlogn),求解第k个数的效率是O(1)。

据说0ms做法是容斥+二分?

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 const int MAXN= 1000001;
 7 int n,k;
 8 int phi,p[MAXN];//与n互质的phi个数的表,其中第phi个放在下标0的位置。
 9 
10 int gcd(int a,int b)
11 {
12     if (a%b==0) return b;
13         else return gcd(b,a%b);
14 }
15 
16 void getp()
17 {
18     phi=0;
19     for (int i=1;i<n;i++)
20         if (gcd(n,i)==1) p[++phi]=i;
21 }
22 
23 int main()
24 {
25     while (~scanf("%d%d",&n,&k))
26     {
27         if (n!=1)
28         {
29             getp();
30             printf("%d\n",k%phi==0? (k-1)/phi*n+p[phi]:k/phi*n+p[(k%phi)]);
31         }
32         else cout<<k<<endl;
33     }
34     return 0;
35 }

 

【欧几里德算法】POJ2773-HAPPY 2006

原文:http://www.cnblogs.com/iiyiyi/p/5547921.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!