http://acm.pku.edu.cn/JudgeOnline/problem?id=2773题目输入m和k，让你求从小到大排列，第k个与m互素的正整数。方法就是先求出m以内的所有素数（预处理），然后对m因式分解，m=p1^a1 * p2^a2 * ... * pt^at，然后分别记录下p1, p2, ..., pt。接着是二分k，对于每次二分，用容斥原理去求答案，比如与2不互素的有m / 2个，与3不互素的有m / 3个，与2 * 3 = 6不互素的有m / 6个，因此就是m / 2 + m / 3 - m / 6，显然，这个过程就是个DFS。
1 #include <cstdio>
2 #include <vector>
3
4 using namespace std;
5
6 const int MAX_N = 1000001;
7 const __int64 INF = 9223372036854775807;
8
9 bool isnPrime[MAX_N];
10 vector<int> prime;
11 vector<int> fac;
12 int m, k;
13
14 void CalcPrime() {
15 prime.clear();
16 prime.push_back(2);
17 int t = 1;
18 for (int i = 3; i < MAX_N; i += 2) {
19 if (!isnPrime[i]) {
20 prime.push_back(i);
21 for (int j = i + i; j < MAX_N; j += i) isnPrime[j] = 1;
22 }
23 }
24 }
25
26 void DFS(int now, int mul, int depth, int num, __int64 m, __int64 &cnt) {
27 if (depth == num) {
28 cnt += m / mul;
29 return;
30 }
31 for (int i = now; i < fac.size(); ++i) {
32 if (mul * fac[i] > m) break;
33 DFS(i + 1, mul * fac[i], depth + 1, num, m, cnt);
34 }
35 }
36
37 __int64 cnt(__int64 m) {
38 __int64 cnt = m, tmp;
39 for (int i = 1; i <= fac.size(); ++i) {
40 tmp = 0;
41 DFS(0, 1, 0, i, m, tmp);
42 if (i % 2) cnt -= tmp;
43 else cnt += tmp;
44 }
45 return cnt;
46 }
47
48 int main() {
49 CalcPrime();
50 while (scanf("%d%d", &m, &k) != EOF) {
51 fac.clear();
52 for (int i = 0; prime[i] <= m; ++i) {
53 if (m % prime[i] == 0) {
54 while (m % prime[i] == 0) m /= prime[i];
55 fac.push_back(prime[i]);
56 }
57 }
58 __int64 l = 1, r = INF, t, mid, ret;
59 while (l <= r) {
60 mid = l + (r - l) / 2;
61 t = cnt(mid);
62 if (t >= k) {
63 if (t == k) ret = mid;
64 r = mid - 1;
65 } else l = mid + 1;
66 }
67 printf("%d\n", ret);
68 }
69 return 0;
70 }
71