# Untitled

unknown
c_cpp
8 months ago
1.4 kB
20
Indexable
Never
```#include<iostream>
#include<vector>
#include<set>
#include<stack>
#include<algorithm>
#include<unordered_map>
#include<map>
#include<numeric>
#include<queue>
#include<cstring>
#include<cmath>
#define ll long long
#define all(a) begin(a) ,end(a)
#define nline "\n"
#define ff first
#define ss second
#define pb push_back
using namespace std ;

const ll MOD = 1e9 + 7  ;

int f(ll m) {
// RETURN G(X)
return (log(m) / log((int)log2(m)))  ;
}

ll binSearch(ll L , ll R) {

// FUNCTION TO CALCULATE WHERE THE POINT IS WHEN G(X) CHANGES BY 1 IN L-R
// ANS = (PT-L)*ANSL + (R-PT + 1) * ANSR

int ansL = f(L);
int ansR = f(R);
if (ansR == ansL) {
return ((R - L + 1) * (ansR)) % MOD ;
}
ll pt = R + 1;
ll l =  L , r = R;
while ( l <= r) {
ll  mid = (l + r) / 2;
if (f(mid) == ansR) {
pt = mid ;
r = mid - 1;
}
else l = mid + 1;
}

ll ans = (pt - L) * ansL ;
ans %= MOD;
ans += (R - pt + 1) * ansR ;
ans %= MOD;
return ans ;
}

ll solve(ll &l , ll &r) {
ll low = (1LL << (int)log2(l));
ll ans = 0 ;
while (low  <= r) {
ans += binSearch(l , min(r, 2 * low - 1));
ans %= MOD;
low *= 2;
l = low;
}

return ans ;
}

void solve() {
int q ;
cin >> q ;
while (q -- ) {
ll l , r  ;
cin >> l >> r;
ll ans = solve(l , r) ;
ans %= MOD ;
cout << ans << nline ;
}
}

int main() {

int t ;
// cin >> t ;
t = 1;
for (int i = 0 ; i < t ; ++i ) {
solve() ;
}
}```