fork download
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. using i64 = long long;
  5.  
  6. int main() {
  7. cin.tie(0)->sync_with_stdio(0);
  8. int n, q; cin >> n >> q;
  9. vector<i64> v(n, 0LL), qs(q, 0LL);
  10. for (int i = 0; i < n; i++) cin >> v[i];
  11. for (int i = 0; i < q; i++) cin >> qs[i];
  12. sort(v.begin(), v.end());
  13.  
  14. vector<i64> nv(0, 0LL);
  15. for (int i = 0; i < n; i++) {
  16. int f = 1;
  17. for (int j = 0; j < i; j++) if (v[i] % v[j] == 0) f = 0;
  18. if (f) nv.push_back(v[i]);
  19. }
  20.  
  21. vector<i64> res(q, 0LL);
  22. auto rec = [&](const auto& self, i64 l, i64 r, auto buc) -> void {
  23. if (buc.empty()) return;
  24. if (l + 1 == r) {
  25. for (int i : buc) res[i] = r;
  26. return;
  27. }
  28. i64 mid = l + r >> 1, val = 0;
  29. for (int s = 1; s < 1 << nv.size(); s++) {
  30. i64 g = 1;
  31. for (int i = 0; i < nv.size(); i++) {
  32. if (~s >> i & 1) continue;
  33. g = g * nv[i] / __gcd(g, nv[i]);
  34. }
  35. val += mid / g * (__builtin_parity(s) ? 1 : -1);
  36. }
  37. vector<int> lbuc(0, 0), rbuc(0, 0);
  38. for (int i : buc) {
  39. if (val >= qs[i]) lbuc.push_back(i);
  40. else rbuc.push_back(i);
  41. }
  42. self(self, l, mid, lbuc);
  43. self(self, mid, r, rbuc);
  44. };
  45.  
  46. vector<int> buc(q, 0);
  47. iota(buc.begin(), buc.end(), 0);
  48. rec(rec, 0, 2.5e18, buc);
  49. for (int i = 0; i < q; i++) cout << res[i] << '\n';
  50. }
Time limit exceeded #stdin #stdout 15s 5292KB
stdin
15 50
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47
17200000000000000
34400000000000000
51600000000000000
68800000000000000
86000000000000000
103200000000000000
120400000000000000
137600000000000000
154800000000000000
172000000000000000
189200000000000000
206400000000000000
223600000000000000
240800000000000000
258000000000000000
275200000000000000
292400000000000000
309600000000000000
326800000000000000
344000000000000000
361200000000000000
378400000000000000
395600000000000000
412800000000000000
430000000000000000
447200000000000000
464400000000000000
481600000000000000
498800000000000000
516000000000000000
533200000000000000
550400000000000000
567600000000000000
584800000000000000
602000000000000000
619200000000000000
636400000000000000
653600000000000000
670800000000000000
688000000000000000
705200000000000000
722400000000000000
739600000000000000
756800000000000000
774000000000000000
791200000000000000
808400000000000000
825600000000000000
842800000000000000
860000000000000000
stdout
Standard output is empty