fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. const ll MOD = (ll)1e9 + 7;
  5.  
  6. ll even = 0L, odd = 0L;
  7.  
  8. ll solve(ll lrc)
  9. {
  10.     ll p, n;
  11.     for(p = 1L, n = 0L; p - 1 < lrc; p *= 2, n++) ;
  12.     n--;
  13.     // cout << n << "v" << p << endl;
  14.     if(p - 1 != lrc) n--, p /= 2;
  15.     // cout << n << endl;
  16.     if(n % 2){
  17.         ll rest = (lrc - p + 1);
  18.  
  19.         p /= 2;
  20.         ll tmp = p * 4;
  21.         even = tmp - 2;
  22.         even /= 3;
  23.         //  cout << even << endl;
  24.         tmp = even;
  25.         even = (tmp * tmp) % MOD + tmp;
  26.         even %= MOD;
  27.         p /= 2;
  28.         tmp = (p * 4) % MOD;
  29.         odd = tmp - 1;
  30.         odd /= 3;
  31.         odd += rest;
  32.         odd %= MOD;
  33.         odd *= odd;
  34.         odd %= MOD;
  35.     }
  36.     else{
  37.         ll rest = (lrc - p + 1);
  38.         p /= 2;
  39.         ll tmp = p * 4;
  40.         odd = tmp  - 1;
  41.         odd /= 3;
  42.         odd *= odd;
  43.         odd %= MOD;
  44.         p /= 2;
  45.         tmp =(p * 4) % MOD;
  46.         even = tmp - 2;
  47.         even /= 3;
  48.         even += rest;
  49.         tmp = even;
  50.         even = ((tmp * tmp) % MOD + tmp) % MOD;
  51.  
  52.     }
  53.     //  cout << even << " " << odd << endl;
  54.     return (odd + even) % MOD;
  55. }
  56.  
  57.  
  58.  
  59. int main()
  60. {
  61.     ll l, r;
  62.     cin >> l >> r;
  63.  
  64.     ll res = (solve(r) - solve(l - 1)) % MOD;
  65.     if(res < 0) res += MOD;
  66.     cout << res << endl;
  67.  
  68.     return 0;
  69. }
  70.  
Success #stdin #stdout 0s 15232KB
comments (?)
stdin 
Standard input is empty
stdout 
790228091
https://ideone.com/i9lFJ1
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
secret

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!