Advertisement
pb_jiang

week393 T3

Apr 13th, 2024
615
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.09 KB | None | 0 0
  1. using ll = long long;
  2. class Solution {
  3.     int lowbit(int x) { return x & -x; }
  4.     int log2(int x) {
  5.         int ret = 0;
  6.         while(x > 1)
  7.             x = x / 2, ret += 1;
  8.         return ret;
  9.     }
  10. public:
  11.     long long findKthSmallest(vector<int>& cs, int k) {
  12.         ll lb = 0, ub = 5e11;
  13.         auto check = [&](ll v) {
  14.             ll n = cs.size(), cnt = 0;
  15.             for (int i = (1 << n) - 1; i > 0; --i) {
  16.                 int j = i, lb = lowbit(j), idx = log2(lb), g = cs[idx], bit = 1;
  17.                 j = j - lb;
  18.                 while(j) {
  19.                     lb = lowbit(j), idx = log2(lb);
  20.                     assert(idx < n);
  21.                     g = lcm(g, cs[idx]);
  22.                     j -= lb, bit += 1;
  23.                 }
  24.                 cnt += (bit % 2 ? 1ll : -1ll) * v / g;
  25.             }
  26.             return cnt;
  27.         };
  28.        
  29.         while(lb + 1 < ub) {
  30.             ll mid = (lb + ub) / 2;
  31.             if (check(mid) < k) {
  32.                 lb = mid;
  33.             } else {
  34.                 ub = mid;
  35.             }
  36.         }
  37.         return ub;
  38.     }
  39. };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement