Untitled

mail@pastecode.io avatar
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() ;
	}
}