poj2773 Happy 2006

题目链接：http://poj.org/problem?id=2773

题意：

给出n和k，求出第k个与n互素的数

分析：

如果知道欧几里德算法的话就应该知道gcd（b×t+a，b）=gcd（a，b）（t为任意整数）

则如果a与b互素，则b×t+a与b也一定互素，如果a与b不互素，则b×t+a与b也一定不互素

故与m互素的数对m取模具有周期性，则根据这个方法我们就可以很快的求出第k个与m互素的数

假设小于m的数且与m互素的数有k个，其中第i个是ai，则第m×k+i与m互素的数是k×m+ai

代码：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cmath>
 4 #include<cstring>
 5 
 6 using namespace std;
 7 const int maxn=1000010;
 8 
 9 int num[maxn];
10 int prime[maxn];
11 int vis[maxn];
12 int cnt;
13 
14 void init()
15 {
16     memset(vis,0,sizeof(vis));
17     cnt=0;
18     for(int i=2;i<maxn;i++)
19     {
20         if(!vis[i])
21         {
22             prime[cnt++]=i;
23             for(int j=1;i*j<maxn;j++)
24                 vis[i*j]=1;
25         }
26     }
27 }
28 
29 int phi(int x)
30 {
31     int ans=x;
32     for(int i=0;i<cnt&&prime[i]*prime[i]<=x;i++)
33     {
34         if(x%prime[i]==0)
35         {
36             ans=ans/prime[i]*(prime[i]-1);
37             while(x%prime[i]==0)
38                 x/=prime[i];
39             for(int j=1;j*prime[i]<maxn;j++)
40                 vis[j*prime[i]]=1;
41         }
42     }
43     if(x>1)
44     {
45         ans=ans/x*(x-1);
46         for(int j=1;j*x<maxn;j++)
47             vis[j*x]=1;
48     }
49     return ans;
50 }
51 
52 
53 int main()
54 {
55     init();
56     int m,k;
57     while(~scanf("%d%d",&m,&k))
58     {
59         int tot=0;
60         memset(vis,0,sizeof(vis));
61         phi(m);
62         for(int i=1;i<=m;i++)
63             if(vis[i]==0)
64                 num[++tot]=i;
65         if(k%tot!=0)
66             printf("%lld
",(long long)k/tot*m+num[k%tot]);
67         else
68             printf("%lld
",(long long)(k/tot-1)*m+num[tot]);
69     }
70     return 0;
71 }