题意：
找到第k个与m互质的数
题解：
容斥原理求区间(1到r)里面跟n互质的个数时间复杂度O(sqrt(n))…
二分复杂度也是O(log(n))
容斥原理+二分这个r
代码：
1 #include<stdio.h>
2 #include<string.h>
3 #include<iostream>
4 #include<algorithm>
5 #include<math.h>
6 #include<queue>
7 using namespace std;
8 typedef long long ll;
9 const int maxn=100000;
10 int v[maxn],index;
11 void oula(int n) //获取n的所有质因数
12 {
13 index=0;
14 for(int i=2; i<=sqrt(n); ++i)
15 {
16 if(n%i==0)
17 {
18 v[index++]=i;
19 n/=i;
20 while(n%i==0)
21 n/=i;
22 }
23 }
24 if(n>1)
25 v[index++]=n;
26 }
27 int get_result(int n)//容斥原理
28 {
29 int ans=0;
30 for(int i=1; i< (1<<index) ; i++)
31 {
32 int ones=0,mult=1;
33 for(int j=0; j<index; j++)
34 {
35 if(i & (1<<j))
36 {
37 ones++;
38 mult*=v[j];
39 }
40 }
41 if(ones&1)//奇数加，偶数减
42 ans+= n/mult;
43 else
44 ans-= n/mult;
45 }
46 return n-ans;
47 }
48 int main()
49 {
50 int m,k;
51 while(~scanf("%d%d",&m,&k))
52 {
53 oula(m);
54 int l=1,mid,r=1000000000,ans=-1;
55 while(l<=r)
56 {
57 mid=(l+r)>>1;
58 if(get_result(mid)>=k)
59 {
60 ans=mid;
61 r=mid-1;
62 }
63 else l=mid+1;
64 }
65 printf("%d\n",ans);
66 }
67 return 0;
68 }