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.  
  8.   ll k,l1,r1,l2,r2;
  9.   cin >> k >> l1 >> r1 >> l2 >> r2;
  10.   ll ans =0;
  11.   ll new_k=1;
  12.   for(int i=1;i<32 && new_k<=r2;i++){
  13.     new_k=(ll)pow(k,i);
  14.     ll low=l1,high=r1;
  15.     ll con1,con2;
  16.     con1 = con2 =-1;
  17.     while(low<=high){
  18.         ll mid=(low+high)/2;
  19.         if(mid <= r2 / new_k && mid >= (l2 + new_k - 1) / new_k){
  20.             con1=mid;
  21.             high=mid-1;
  22.         }
  23.         else 
  24.           low=mid+1;
  25.     }
  26.     low=l1,high=r1;
  27.     while(low<=high){
  28.         ll mid=(low+high)/2;
  29.         if(mid <= r2 / new_k && mid >= (l2 + new_k - 1) / new_k){
  30.             con2=mid;
  31.             low=mid+1;
  32.         }
  33.         else 
  34.           high=mid-1;
  35.     }
  36.     if(con1!=-1 && con2!=-1)
  37.     ans+=con2-con1+1;
  38.   }
  39.   cout << ans << '\n';
  40.  
  41. }
  42.  
  43. int main(){ 
  44.     ios::sync_with_stdio(false);
  45.     cin.tie(nullptr);
  46.  
  47.     int t;
  48.     cin >> t;
  49.     while (t--) solve();
  50.  
  51.  
  52.     return 0;
  53. }
  54.  
Success #stdin #stdout 0.01s 5288KB
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 
5
500000000
6
0
186
https://ideone.com/IJE2hA
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!