Number Operating (Easy Version)AI (CI翻译)
This is the easy version of the problem. The difference between the versions is that in this version, the sum of $r - l + 1$ over all test cases does not exceed $2 \cdot 10^5$.
You have a variable $x$, initially equal to $0$. In one operation, you can do one of the following:
- Operation
$1$: add$2^k$to$x$, where$k$is the number of times Operation$1$has been performed in a row immediately before this one (in particular,$k = 0$if this is the first operation or the previous operation was Operation$2$); - Operation
$2$: subtract$1$from$x$(the result may be negative).
For a non-negative integer $n$, let $f(n)$ be the minimum number of operations needed to make $x$ equal to $n$. It can be shown that this is always possible.
You are given two integers $l$ and $r$. Find $\sum\limits_{n = l}^{r} f(n)$. Since the answer can be very large, output it modulo $998\,244\,353$.
Input
Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.
The only line of each test case contains two integers $l$ and $r$ ($0 \le l \le r \le 10^{18}$).
It is guaranteed that the sum of $r - l + 1$ over all test cases does not exceed $2 \cdot 10^5$.
Output
For each test case, output a single integer — the value of $\sum\limits_{n = l}^{r} f(n)$ modulo $998\,244\,353$.
Note
In the first test case, $l = r = 4$. Initially, $x = 0$. One optimal sequence of $6$ operations is as follows:
- Perform Operation
$1$with$k = 0$, so$x$becomes$0 + 2^0 = 1$. - Perform Operation
$1$with$k = 1$, so$x$becomes$1 + 2^1 = 3$. - Perform Operation
$1$with$k = 2$, so$x$becomes$3 + 2^2 = 7$. - Perform Operation
$2$, so$x$becomes$7 - 1 = 6$. - Perform Operation
$2$, so$x$becomes$6 - 1 = 5$. - Perform Operation
$2$, so$x$becomes$5 - 1 = 4$.
It can be shown that $x = 4$ cannot be reached in $5$ or fewer operations. Thus, $f(4) = 6$, and the answer is $6$.
In the second test case, $l = 1$ and $r = 3$. We have $f(1) = 1$, $f(2) = 3$, and $f(3) = 2$. Thus, the answer is $1 + 3 + 2 = 6$.
In the third test case, $l = r = 127$. We can perform Operation $1$ seven times in a row to reach $x = 2^7 - 1 = 127$. It can be shown that $x = 127$ cannot be reached in $6$ or fewer operations. Thus, $f(127) = 7$, and the answer is $7$.
{"titleZh":"数字操作（简单版）","bodyZh":"Ariana Grande - stay\n\n这是本题的简单版本。与其他版本的区别在于，本版本中所有测试用例的 $r - l + 1$ 之和不超过 $2 \\cdot 10^5$。\n\n有一个变量 $x$，初始值为 $0$。每次操作可以执行以下操作之一：\n\n- 操作 $1$：将 $2^k$ 加到 $x$ 上，其中 $k$ 是紧接在本次操作之前连续执行操作 $1$ 的次数（特别地，如果这是第一次操作，或者上一次操作是操作 $2$，则 $k = 0$）；\n- 操作 $2$：将 $1$ 从 $x$ 中减去（结果可以为负数）。\n\n对于非负整数 $n$，令 $f(n)$ 表示使 $x$ 等于 $n$ 所需的最少操作次数。可以证明，这总是可行的。\n\n给定两个整数 $l$ 和 $r$。求 $\sum\\limits_{n = l}^{r} f(n)$。由于答案可能很大，请将其对 $998\\,244\\,353$ 取模后输出。\n\n## 输入格式\n\n每个输入包含多组测试用例。第一行包含测试用例数量 $t$（$1 \\le t \\le 10^4$）。接下来是各测试用例的描述。\n\n每个测试用例仅一行，包含两个整数 $l$ 和 $r$（$0 \\le l \\le r \\le 10^{18}$）。\n\n保证所有测试用例的 $r - l + 1$ 之和不超过 $2 \\cdot 10^5$。\n\n## 输出格式\n\n对于每个测试用例，输出一个整数，即 $\sum\\limits_{n = l}^{r} f(n)$ 对 $998\\,244\\,353$ 取模后的结果。\n\n## 说明\n\n在第一个测试用例中，$l = r = 4$。初始时，$x = 0$。一种最优的操作方案需要 $6$ 次操作，过程如下：\n\n1. 执行操作 $1$，此时 $k = 0$，因此 $x$ 变为 $0 + 2^0 = 1$。\n2. 执行操作 $1$，此时 $k = 1$，因此 $x$ 变为 $1 + 2^1 = 3$。\n3. 执行操作 $1$，此时 $k = 2$，因此 $x$ 变为 $3 + 2^2 = 7$。\n4. 执行操作 $2$，因此 $x$ 变为 $7 - 1 = 6$。\n5. 执行操作 $2$，因此 $x$ 变为 $6 - 1 = 5$。\n6. 执行操作 $2$，因此 $x$ 变为 $5 - 1 = 4$。\n\n可以证明，无法在 $5$ 次或更少的操作内得到 $x = 4$。因此，$f(4) = 6$，答案为 $6$。\n\n在第二个测试用例中，$l = 1$ 且 $r = 3$。我们有 $f(1) = 1$、$f(2) = 3$ 和 $f(3) = 2$。因此，答案为 $1 + 3 + 2 = 6$。\n\n在第三个测试用例中，$l = r = 127$。连续执行七次操作 $1$，即可得到 $x = 2^7 - 1 = 127$。可以证明，无法在 $6$ 次或更少的操作内得到 $x = 127$。因此，$f(127) = 7$，答案为 $7$。"}AI (CI翻译)
样例
5
4 4
1 3
127 127
0 1000
999999999999900001 1000000000000000000
6
6
7
25383
102936941
题面与样例版权归 Codeforces 及出题人所有；中文翻译由 AI 生成（gpt-6.1-sol），如有出入请以原文为准。