fork download
copy 
  1. /*
  2.  ███████  ██   ██████  ██     ██  ██  ███████   █████
  3.  ██           ██       ███   ███  ██       ██  ██   ██
  4.  ███████  ██  ██  ███  ██ ███ ██  ██       ██  ███████
  5.       ██  ██  ██   ██  ██  █  ██  ██       ██  ██   ██
  6.  ███████  ██   ██████  ██     ██  ██       ██  ██   ██
  7. */
  8. #include <bits/stdc++.h>
  9. #include <string.h>
  10. #include <cmath>
  11. #include <iostream>
  12. #include <set>
  13. #include <iterator>
  14. using namespace std;
  15. #define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
  16. #define ld long double
  17. #define ll long long
  18. #define int ll
  19. #define int128 __int128
  20. const ll MOD = 998244353 ;
  21. const ll INF = 1e18 ;
  22. #define rep(i,x,y) for(int i=(x);i<(y);i++)
  23. inline ll mul(ll a1, ll a2) { return (((a1 * a2) % MOD + MOD ) % MOD ) ; }
  24. inline ll add(ll a1, ll a2) { return (((a1 + a2) % MOD + MOD ) % MOD ); }
  25. inline ll sub(ll a1, ll a2) { return  ((a1 - a2 + MOD) % MOD); }
  26. ll binpow(ll a,ll b) {
  27.     if(b==0) {
  28.         return 1;
  29.     }
  30.     if(b%2){
  31.         return (a*binpow(a,b-1))%MOD;
  32.     }
  33.     return binpow((a*a)%MOD,b/2);
  34. }
  35. const int MAX = 1e6 + 100 ;
  36. vector<ll> smallestDiv;
  37. void sieve() {
  38.     for(ll i =  0 ; i < MAX ; i ++) smallestDiv.push_back(i);
  39.     for (ll i = 2; i*i < MAX; i++) {
  40.         if (smallestDiv[i] != i) continue;
  41.         for (ll j = i*i; j < MAX; j+=i)
  42.             if (smallestDiv[j] == j) smallestDiv[j] = i;
  43.     }
  44. }
  45. map<int, int> dpf , dpcf;
  46.  
  47. int ah(int n) {
  48.     int k = 0;
  49.     while (n > 1) {
  50.         n /= 2 ;
  51.         k++;
  52.     }
  53.     return k;
  54. }
  55.  
  56. int cf(int n) {
  57.     if (n == 0) return 0;
  58.     if (n == 1) return 1;
  59.     if (n == 2) return 3;
  60.     if (n == 3) return 2;
  61.     if (dpcf.count(n)) return dpcf[n];
  62.     int k = ah(n) ;
  63.     int x = n - (1LL << k);
  64.     int res = min(k + (1LL << k) - x, k + 1 + cf(x + 2));
  65.     dpcf[n] = res;
  66.     return res ;
  67. }
  68. int f(int n ) {
  69.     if (n < 0) return 0;
  70.     if (n == 0) return 0;
  71.     if (n == 1) return 1;
  72.     if (n == 2) return 4;
  73.     if (n == 3) return 6;
  74.     if (dpf.count(n)) return dpf[n];
  75.     int k = ah(n);
  76.     int x = n - (1LL << k) , p2 = 1LL << k;
  77.     int change = p2 ,l = 0, r = p2 - 1;
  78.     while (l <= r) {
  79.         int m = l + (r-l) / 2;
  80.         if (cf(m+2)+m >= p2-1) {
  81.             change = m;
  82.             r = m-1;
  83.         } else {
  84.             l = m+1;
  85.         }
  86.     }
  87.     int ans = f(p2 - 1);
  88.     if (x < change) {
  89.         int z = add ( mul(x+1,k+1) , sub(f(x+2),1) )  ;
  90.         ans = add(ans , z) ;
  91.     }else {
  92.         int z = add ( mul(change,k+1) , sub(f(change+1),1) )  ;
  93.         ans = add(ans , z) ;
  94.         int cnt = add(sub(x,change),1) ;
  95.         z = mul ( mul( add(change,x) , cnt) , mul ( add(MOD,1) , binpow(2,MOD-2) ) ) ;
  96.         int d = mul(cnt,add(k,p2)) ;
  97.         ans = add(ans,sub(d,z)) ;
  98.     }
  99.     dpf[n] = ans;
  100.     return ans ;
  101. }
  102.  
  103.  
  104.  
  105. int32_t main() {
  106.     IOS ;
  107.     int test = 1 ;
  108.     cin >> test ;
  109.     while (test--) {
  110.         int l , r ; cin >> l >> r ;
  111.         int ans = sub(f(r),f(l-1)) ;
  112.         cout << ans << endl ;
  113.     }
  114.     return 0;
  115. }
Success #stdin #stdout 0.01s 5316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
322911289
https://ideone.com/sLGqYB
language:
C++ (gcc 8.3)
created:
1 day 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!