題目是給出m，k。找到跟第k個跟m互素的數是多少。
構造肯定不行，再加上數據范圍，只能二分。思路是二分枚舉[1,2^64]范圍內所有的數x，找到1到x范圍內與m不互素的數的個數y（用容斥原理）。然后用x - y，如果等于k就是結果。
找到1到x范圍內與m不互素的數的個數y：這個過程可以先把m分解質因子，記錄m所有的質因子。f[i]表示含有i個質因子的數的個數。ans = m - f(1) + f(2) - f(3) ....
ps:這里二分要找滿足 == k最左邊的數，推了半天發現把二分寫錯了。。。T_T
?
poj1741、?
//#pragma comment(linker,"/STACK:327680000,327680000") #include <iostream> #include <cstdio> #include <cmath> #include <vector> #include <cstring> #include <algorithm> #include <string> #include <set> #include <functional> #include <numeric> #include <sstream> #include <stack> #include <map> #include <queue>#define CL(arr, val) memset(arr, val, sizeof(arr)) #define REP(i, n) for((i) = 0; (i) < (n); ++(i)) #define FOR(i, l, h) for((i) = (l); (i) <= (h); ++(i)) #define FORD(i, h, l) for((i) = (h); (i) >= (l); --(i)) #define L(x) (x) << 1 #define R(x) (x) << 1 | 1 #define MID(l, r) (l + r) >> 1 #define Min(x, y) (x) < (y) ? (x) : (y) #define Max(x, y) (x) < (y) ? (y) : (x) #define E(x) (1 << (x)) #define iabs(x) (x) < 0 ? -(x) : (x) #define OUT(x) printf("%I64d\n", x) #define Read() freopen("data.in", "r", stdin) #define Write() freopen("data.out", "w", stdout);typedef long long LL; const double eps = 1e-8; const double pi = acos(-1.0); const double inf = ~0u>>2;using namespace std;const int N = 1000010;int p[N], cnt;void init(int m) {cnt = 0;for(int i = 2; i*i <= m; ++i) {if(m%i == 0) {p[cnt++] = i;while(m%i == 0) {m /= i;}}}if(m != 1) p[cnt++] = m; }LL cal(LL n) {int i, j, bit;LL res = 0, sum;for(i = 1; i < 1<<cnt; ++i) {bit = 0; sum = 1;for(j = 0; j < cnt; ++j) {if(i&(1<<j)) {bit++;sum *= p[j];}}if(bit&1) res -= n/sum;else res += n/sum;}return n + res; }int main() {//Read();int m, k;while(cin >> m >> k, !cin.eof()) {init(m);LL l = 1, r = (1LL<<60), mid, tmp;while(r - l > 0) {mid = MID(l, r);tmp = cal(mid);if(tmp >= k) r = mid;else l = mid + 1;}printf("%lld\n", l);}return 0; }
