fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4.  
  5. void solve() {
  6.     ll k, l1, r1, l2, r2;
  7.     cin >> k >> l1 >> r1 >> l2 >> r2;
  8.     ll ans = 0;
  9.  
  10.     for (int n = 1; n <= 32; ++n) {
  11.         ll kn = 1;
  12.         bool overflow = false;
  13.  
  14.         // compute k^n safely
  15.         for (int i = 1; i <= n; ++i) {
  16.             if (kn > 1e18 / k) {
  17.                 overflow = true;
  18.                 break;
  19.             }
  20.             kn *= k;
  21.         }
  22.         if (overflow) break;
  23.  
  24.         // binary search for first x in [l1, r1] such that x * kn >= l2
  25.         ll low = l1, high = r1, left = -1;
  26.         while (low <= high) {
  27.             ll mid = (low + high) / 2;
  28.             if (mid > r2 / kn) {
  29.                 high = mid - 1;
  30.                 continue;
  31.             }
  32.             if (mid * kn >= l2) {
  33.                 left = mid;
  34.                 high = mid - 1;
  35.             } else {
  36.                 low = mid + 1;
  37.             }
  38.         }
  39.  
  40.         // binary search for last x in [l1, r1] such that x * kn <= r2
  41.         low = l1, high = r1;
  42.         ll right = -1;
  43.         while (low <= high) {
  44.             ll mid = (low + high) / 2;
  45.             if (mid > r2 / kn) {
  46.                 high = mid - 1;
  47.                 continue;
  48.             }
  49.             if (mid * kn <= r2) {
  50.                 right = mid;
  51.                 low = mid + 1;
  52.             } else {
  53.                 high = mid - 1;
  54.             }
  55.         }
  56.  
  57.         if (left != -1 && right != -1 && right >= left) {
  58.             ans += (right - left + 1);
  59.         }
  60.     }
  61.  
  62.     cout << ans << '\n';
  63. }
  64.  
  65. int main() {
  66.     ios::sync_with_stdio(false);
  67.     cin.tie(nullptr);
  68.  
  69.     int t;
  70.     cin >> t;
  71.     while (t--) solve();
  72.  
  73.     return 0;
  74. }
  75.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
5
2 2 6 2 12
2 1 1000000000 1 1000000000
3 5 7 15 63
1000000000 1 5 6 1000000000
15 17 78 2596 20914861
stdout
copy 
7
999999987
6
1
197
https://ideone.com/SNIqoy
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!