fork download
copy 
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <cmath>
  4.  
  5. using namespace std;
  6.  
  7. typedef long long ll;
  8.  
  9. ll gcd(ll a, ll b) {
  10.     while (b) {
  11.         a %= b;
  12.         swap(a, b);
  13.     }
  14.     return a;
  15. }
  16.  
  17. ll lcm(ll a, ll b) {
  18.     if (a == 0 || b == 0) return 0;
  19.     return (a / gcd(a, b)) * b;
  20. }
  21.  
  22. ll count_remaining(ll N, ll x, ll y, ll l) {
  23.     ll removed = 0;
  24.     removed += N / x;
  25.     removed += N / y;
  26.     removed -= N / l;
  27.     return N - removed;
  28. }
  29.  
  30. void solve() {
  31.     ll x, y, k;
  32.     if (!(cin >> x >> y >> k)) return;
  33.  
  34.     ll l = lcm(x, y);
  35.  
  36.     ll low = 1;
  37.     ll high = 2e14;
  38.     ll ans = -1;
  39.  
  40.     while (low <= high) {
  41.         ll mid = low + (high - low) / 2;
  42.         if (mid <= 0) { 
  43.             low = 1; 
  44.             continue; 
  45.         } 
  46.  
  47.         ll remaining = count_remaining(mid, x, y, l);
  48.  
  49.         if (remaining >= k) {
  50.             ans = mid;
  51.             high = mid - 1;
  52.         } else {
  53.             low = mid + 1;
  54.         }
  55.     }
  56.  
  57.     if (ans != -1 && count_remaining(ans, x, y, l) < k) {
  58.         cout << -1 << endl;
  59.     } else {
  60.         cout << ans << endl;
  61.     }
  62. }
  63.  
  64. int main() {
  65.     ios_base::sync_with_stdio(false);
  66.     cin.tie(NULL);
  67.  
  68.     int t;
  69.     if (!(cin >> t)) return 0;
  70.     while (t--) {
  71.         solve();
  72.     }
  73.  
  74.     return 0;
  75. }
Success #stdin #stdout 0.01s 5292KB
comments (?)
stdin
copy 
6
2 3 5
2 5 1
20 2 1000000000000
175 10 28
100000 998244353 1999999999
1 1 1
stdout
copy 
13
1
1999999999999
31
2000020001
-1
https://ideone.com/n4P67X
language:
C++14 (gcc 8.3)
created:
10 days 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!