fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define el '\n'
  4. #define fi first
  5. #define sec second
  6. #define pb push_back
  7. #define int long long
  8. #define pii pair<int,int>
  9. #define sz(v) (int)(v).size()
  10. #define all(v) (v).begin(),(v).end()
  11. #define FOR(i, a, b) for(int i = (a), _b = (b); i <= _b; i++)
  12. #define REP(i, a, b) for(int i = (a), _b = (b); i >= _b; i--)
  13.  
  14. using namespace std;
  15.  
  16. const int INF = (int)1e18 + 462010;
  17. const int MAX_N = 15;
  18.  
  19. int dp[(1 << MAX_N) + 5];
  20. int a[MAX_N + 5];
  21. int n, k;
  22.  
  23. void Input(){
  24.     cin >> n >> k;
  25.     FOR(i, 0, n - 1) cin >> a[i];
  26. }
  27.  
  28. int lcm(int x, int y){
  29.     if(!x) return y;
  30.     if(!y) return x;
  31.     if(x >= INF) return INF;   
  32.     int g = __gcd(x, y);
  33.     int t = x / g;
  34.     if(t > INF / y) return INF;
  35.     return min(INF, t * y);
  36. }
  37.  
  38. void Prepare(){
  39.     FOR(mask, 1, (1 << n) - 1){
  40.         int k = __builtin_ctzll(mask);
  41.         dp[mask] = lcm(dp[(mask - 1) & mask], a[k]);
  42.     }
  43. }
  44.  
  45. int tinh(int mid){
  46.     int res = 0;
  47.     FOR(mask, 1, (1 << n) - 1){
  48.         if(__builtin_popcountll(mask) & 1) res += mid / dp[mask];
  49.         else res -= mid / dp[mask];
  50.     }
  51.  
  52.     res = mid - res;
  53.     return res;
  54. }
  55.  
  56. void Solve(){
  57.     int lo = 1, hi = 1e18, ans;
  58.     while(lo <= hi){
  59.         int mid = (lo + hi) / 2;
  60.  
  61.         if(tinh(mid) >= k){
  62.             ans = mid;
  63.             hi = mid - 1;
  64.         }
  65.         else lo = mid + 1;
  66.     }
  67.     cout << ans;
  68. }
  69.  
  70. signed main(){
  71.     ios_base::sync_with_stdio(0);
  72.     cin.tie(0);
  73.  
  74.     Input();
  75.     Prepare();
  76.     Solve();
  77.  
  78.     return 0;
  79. }
  80.  
Success #stdin #stdout 0s 5316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/Lsq5kG
language:
C++ (gcc 8.3)
created:
10 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!