POJ 2773 Happy 2006(求第k个和m互素的数/欧拉函数)

题目链接：
POJ 2773 Happy 2006
题意：
求第$k$个和$m$互素的数。$m<=10^6,k<=10^8$
分析：

• 如果$gcd(a,m)=1$,那么$gcd(a+k*m,m)=1,k\in Z$

证明:只需要证明$gcd(a+m, m)=1$.令$d=gcd(a+m,m)$，设$a+m=d*p_1,m=d*p_2且p_1>p_2,$,移项可得:$a=d*(p_1-p_2)$,如果$d!=1$，那么$gcd(a,m)!=1$，与原条件不符，故$gcd(a,m)=1$，同理可证$gcd(a+k*m,m)=1,k\in Z$.

所以先求个欧拉函数，再暴力搞一下就好了。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
#include <bitset>
using namespace std;
typedef long long ll;
const int MAX_N = 1000010;int prime_cnt, prime[MAX_N], phi[MAX_N];
bitset<MAX_N> bs;void GetPhi()
{bs.set();prime_cnt = 0;phi[1] = 1;for(int i = 2; i < MAX_N; ++i) {if(bs[i]) {prime[prime_cnt++] = i;phi[i] = i - 1;}for(int j = 0; j < prime_cnt && i * prime[j] < MAX_N; ++j) {bs[i * prime[j]] = 0;if(i % prime[j]) {phi[i * prime[j]] = phi[i] * (prime[j]  - 1);} else {phi[i * prime[j]] = phi[i] * prime[j];break;}}}
}int  gcd(int a, int b)
{return b == 0 ? a : gcd(b, a % b);
}int main()
{GetPhi();int m, k;while(~scanf("%d%d", &m, &k)){if(m == 1){printf("%d\n", k);continue;}int t = k / phi[m];k %= phi[m];if(k == 0) {k = phi[m];t--;}int st = 0;while(k--) {while(gcd(st, m) != 1) st++;st++;}printf("%lld\n", (ll)t * m + st - 1);}return 0;
}