fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. const int Mod = 998244353;
  5.  
  6. void solve() {
  7.     ll k, l1, r1, l2, r2;
  8.     cin >> k >> l1 >> r1 >> l2 >> r2;
  9.     ll ans = 0;
  10.  
  11.     // Handle case n=0 where y = x
  12.     ll lower_n0 = max(l1, l2);
  13.     ll upper_n0 = min(r1, r2);
  14.     ans += max(0LL, upper_n0 - lower_n0 + 1);
  15.  
  16.     // Handle cases where n >= 1, y = x * k^m
  17.     ll test_k = k;
  18.     while (test_k <= r2) {
  19.         // x must be in [l1, r1] and y = x*test_k must be in [l2, r2]
  20.         // So x must be >= ceil(l2 / test_k) and <= floor(r2 / test_k)
  21.         ll lower_x = (l2 + test_k - 1) / test_k; // ceil division
  22.         ll upper_x = r2 / test_k;
  23.         // x also must be in [l1, r1]
  24.         ll lower = max(l1, lower_x);
  25.         ll upper = min(r1, upper_x);
  26.         if (upper >= lower) {
  27.             ans += upper - lower + 1;
  28.         }
  29.         // Check if multiplying by k again would overflow
  30.         if (test_k > r2 / k) {
  31.             break;
  32.         }
  33.         test_k *= k;
  34.     }
  35.  
  36.     cout << ans << '\n';
  37. }
  38.  
  39. int main() {
  40.     ios::sync_with_stdio(false);
  41.     cin.tie(nullptr);
  42.  
  43.     int t;
  44.     cin >> t;
  45.     while (t--) solve();
  46.  
  47.     return 0;
  48. }
Success #stdin #stdout 0.01s 5316KB
comments (?)
stdin 
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 
12
1999999987
6
1
197
https://ideone.com/HUlisx
language:
C++ (gcc 8.3)
created:
9 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!