fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using ll = long long;
  4. ll llcm(ll a, ll b, ll x){
  5.     if (a == 0 || b == 0) return 0;
  6.     ll g = __gcd(a, b);
  7.     __int128 t = a / g;
  8.     __int128 prod = t * b;
  9.     if (prod > x) return 0;
  10.     return (ll)prod;
  11. }
  12. ll tong(int n, ll a[], ll x){
  13. 	ll res = 0;
  14. 	for (int i = 1; i < (1LL << n); i++) {
  15. 		long long p = 1, cnt = 0;
  16. 		for (int j = 0; j < n; j++) {
  17. 			if (i & (1LL << j)) { 
  18. 				cnt++;
  19. 				p = llcm(p, a[j], x);
  20. 			}
  21. 		}
  22. 		if(!p) continue;
  23. 		if(cnt % 2 == 0) res -= x / p;
  24. 		else res += x / p;
  25. 	}
  26. 	return res;
  27. }
  28. int main(){
  29. 	//freopen("infarray.inp", "r", stdin);
  30. 	//freopen("infarray.out", "w", stdout);
  31.     ios::sync_with_stdio(false);
  32.     cin.tie(nullptr);
  33.     int t; cin >> t;
  34.     while(t--){
  35. 	    long long n, k;
  36. 	    cin >> n >> k;
  37. 	    ll a[n];
  38. 	    for(int i = 0; i < n; i++){
  39. 	    	cin >> a[i];
  40. 	    }
  41. 	    ll lo = 1, hi = 1e18;
  42. 	    while (lo < hi) {
  43. 	        ll mid = lo + (hi - lo) / 2;
  44. 	        ll tt = tong(n, a, mid);
  45. 	        //cout << t  << " " << mid<< " | ";
  46. 	        if (mid - tt >= k)
  47. 	            hi = mid;
  48. 	        else
  49. 	            lo = mid + 1;
  50. 	    }
  51. 	    cout << lo << endl;
  52.     }
  53.     return 0;
  54. }
  55.  
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
2
1 5
2
2 2
2 3
stdout
copy 
9
5
https://ideone.com/AuqFfo
language:
C++14 (gcc 8.3)
created:
18 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!