問題一覧 > 通常問題

No.2849 Birthday Donuts

レベル : / AI推定難易度 : 2000 / 実行時間制限 : 1ケース 6.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （解説公開後に AC するまで非表示） / 解いたユーザー数 16
作問者 : 👑 AngrySadEight / テスター : ecottea torisasami4
お気に入りにしたユーザー ProblemId : 11025 / 自分の提出
問題文最終更新日: 2024-07-03 21:59:07
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 441 (順位表) の他の問題:

Problem Statement

For positive integers $x, y$ satisfying $x > y$, a plane figure consisting of $2$ circles with the same center, circle A of radius $x$ and circle B of radius $y$, is called an "$(x, y)$-donut".

As an example, the $(3, 2)$-donut is illustrated below.

As a birthday present, for each integer pair $(i, j)$ satisfying $L \leq i \leq R$ and $1 \leq j < i$, Bob received an $(i, j)$-donut, $1$ of each.

Donuts that can be made to coincide with each other by scaling up or down with a positive ratio are considered to be the same kind of donut, and donuts that cannot be made to coincide are considered to be different kinds of donuts. Find the number of kinds of donuts that Bob received.

You are given $T$ test cases; answer each of them.

Note that in each test case, $L, R$ are given in encrypted form as integers $\alpha, \beta$, respectively. In each test case, decrypt $L, R$ as follows before answering.

  • Let $\mathrm{ans}_0 = 0, \mathrm{ans}_i=$ (the answer to the $i$-th test case). Then, for the $i$-th test case, the values can be decrypted as $L = \alpha \oplus \mathrm{ans}_{i - 1}, R = \beta \oplus \mathrm{ans}_{i - 1}$.

Here, $x \oplus y$ denotes the bitwise XOR of $x$ and $y$.

What is bitwise XOR?

The bitwise XOR $x \oplus y$ of $2$ non-negative integers $x$ and $y$ is defined as follows.

  • The value of the $x \oplus y$ digit, written in base $2$, at the $2^k$ place is defined as follows: if exactly one of the digits of $x, y$, each written in base $2$, at the $2^k$ place is $1$, it is $1$; otherwise, it is $0$.
  • For example, $3 \oplus 5 = 6$. (In base $2$: $011 \oplus 101 = 110$)

Constraints

  • All input values are integers.
  • $1 \leq T \leq 10^5$
  • $0 \leq \alpha, \beta \leq 10^{18}$
  • $2 \leq L \leq R \leq 2 \times 10^5$

Input

The input is given from standard input in the following format, where $\mathrm{case}_i$ represents the $i$-th test case.

$T$
$\mathrm{case}_1$
$\mathrm{case}_2$
$\vdots$
$\mathrm{case}_T$

Each test case is given in the following format. 

$\alpha$ $\beta$

Output

Output $T$ lines. On the $i$-th line, output the answer to the $i$-th test case.

Sample

Sample 1
Input
5
2 3
1 7
15 15
11 200009
12158598942 12158743847
Output
3
5
9
12158598917
10159235125

For test case $1$, since $\mathrm{ans}_0 = 0$, we can decrypt $L = 2, R = 3$. Thus, Bob received the $(2, 1)$-donut, the $(3,1)$-donut, and the $(3, 2)$-donut, for a total of $3$ donuts. These are all different kinds of donuts, so the answer is $3$ kinds.

For test case $2$, since $\mathrm{ans}_1 = 3$, we can decrypt $L = 2, R = 4$. Bob received the $(2, 1)$-donut, the $(3, 1)$-donut, the $(3, 2)$-donut, the $(4, 1)$-donut, the $(4, 2)$-donut, and the $(4, 3)$-donut, for a total of $6$ donuts. The $(2, 1)$-donut can be scaled up to coincide with the $(4, 2)$-donut, and this is the only pair of donuts that can be made to coincide by scaling up or down, so there are $5$ kinds of donuts.

For test case $3$, since $\mathrm{ans}_2 = 5$, we can decrypt $L = 10, R = 10$.

For test case $4$, since $\mathrm{ans}_3 = 9$, we can decrypt $L = 2, R = 200000$.

For test case $5$, since $\mathrm{ans}_4 = 12158598917$, we can decrypt $L = 27, R = 182818$.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。