week393 T3

using ll = long long;
class Solution {
    int lowbit(int x) { return x & -x; }
    int log2(int x) {
        int ret = 0;
        while(x > 1)
            x = x / 2, ret += 1;
        return ret;
    }
public:
    long long findKthSmallest(vector<int>& cs, int k) {
        ll lb = 0, ub = 5e11;
        auto check = [&](ll v) {
            ll n = cs.size(), cnt = 0;
            for (int i = (1 << n) - 1; i > 0; --i) {
                int j = i, lb = lowbit(j), idx = log2(lb), g = cs[idx], bit = 1;
                j = j - lb;
                while(j) {
                    lb = lowbit(j), idx = log2(lb);
                    assert(idx < n);
                    g = lcm(g, cs[idx]);
                    j -= lb, bit += 1;
                }
                cnt += (bit % 2 ? 1ll : -1ll) * v / g;
            }
            return cnt;
        };

        while(lb + 1 < ub) {
            ll mid = (lb + ub) / 2;
            if (check(mid) < k) {
                lb = mid;
            } else {
                ub = mid;
            }
        }
        return ub;
    }
};