小蓝的二进制询问

#include <bits/stdc++.h>
#define inf 0x3f3f3f3f3f
using namespace std;
using ll = long long;
const int N = 4e5 + 7;
const int mod = 998244353;
ll f(ll x, ll k)
{
ll y =pow(2,(k + 1));
ll ok = y / 2;
x++;
ll res = x / y * ok; // 循环节内部分
ll r = x % y;
r -= ok;
if (r > 0)
res += r; // 计算循环节多余部分
return res;
}
void solve()
{
ll l, r;
cin >> l >> r;
ll ans = 0;
for (ll i = 61; i >= 0; i--)
{
ll p = (f(r, i) % mod - f(l - 1, i) % mod ) % mod;
ans = (ans + p) % mod;
}
cout << ans << endl;
}
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int _;
cin >> _;
while (_--)
solve();
return 0;
}
// //f(ll x, ll k) 函数计算了在第 k 位上，区间 [1, x] 中所有数的二进制表示中1的个数的总和。
// y = 1ll << (k + 1);：计算 2^(k+1)，即第 k 位的循环节长度。
// ok = y / 2;：循环节内半段的长度。
// x++;：因为要计算 [1, x] 的范围，所以 x 需要加1。
// res = x / y * ok;：计算完整循环节内1的个数。
// r = x % y; r -= ok; if (r > 0) res += r;：计算循环节多余部分的1的个数。
// 返回 res，即 [1, x] 区间内第 k 位的1的个数总和。//

链接：登录—专业IT笔试面试备考平台_牛客网牛客网是互联网求职神器，C++、Java、前端、产品、运营技能学习/备考/求职题库，在线进行百度阿里腾讯网易等互联网名企笔试面试模拟考试练习,和牛人一起讨论经典试题,全面提升你的技术能力https://ac.nowcoder.com/acm/contest/86639/D
来源：牛客网
 

小蓝有 ttt 组询问，每次给定两个数字 lll,rrr 你需要计算出区间 [l,r]\left [ l,r \right ][l,r] 中所有整数在二进制下1的个数之和。由于结果特别大，你只需要计算出结果模998244353之后的值即可。

输入描述:

第一行输入一个正整数 ttt 表示询问组数。

接下来每行两个整数 l,rl,rl,r 。

(1≤t≤105)\left ( 1\leq t\leq 10^{5} \right )(1≤t≤105)

(1≤l≤r≤1018)\left ( 1\leq l\leq r\leq 10^{18} \right )(1≤l≤r≤1018)

输出描述:

每行输出一个整数表示答案。

示例1

输入

复制1 1 5

1
1 5

输出

复制7

7

说明

1~5的二进制下分别是1 10 11 100 101共有7个1