fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define ull unsigned long long
  5. #define fast ios::sync_with_stdio(0), cin.tie(0);
  6. #define fi first
  7. #define se second
  8. const int MN = 1e5 + 67;
  9.  
  10. ll a[MN], b[MN];
  11. ll q;
  12.  
  13. bool check(ull mid, ull n, ull k) {
  14.     // ull p = mid / k;
  15.     // ull t = mid % k;
  16.     return k * (mid) * (mid + 1) / 2  <= n;
  17. }
  18. int main() {
  19.     fast
  20.     if (fopen("open.inp", "r")) {
  21.         freopen("open.inp", "r", stdin);
  22.         freopen("open.out", "w", stdout);
  23.     }
  24.     cin >> q;
  25.     while (q--) {
  26.         ull n,k;
  27.         cin >> n >> k;
  28.         ull l = 1, r = 2e10, res = 0;
  29.         while (l <= r) {
  30.             ull mid = (l + r) / 2;
  31.             if (check(mid, n, k)) {
  32.                 res = mid;
  33.                 res += ( (n - (k * (mid) * (mid + 1) / 2) ) / (mid + 1) );
  34.                 l = mid + 1;
  35.             }
  36.             else r = mid - 1;
  37.         }
  38.         cout << res << endl;
  39.     }
  40.     return 0;
  41. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
2
23 3
2 3
stdout
copy 
4
0
https://ideone.com/ZfVDB1
language:
C++14 (gcc 8.3)
created:
2 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!