No.2849 Birthday Donuts
タグ : / 解いたユーザー数 14
作問者 : 👑
![AngrySadEight](https://pbs.twimg.com/profile_images/1774819988135927808/f4w6hc33.jpg)
![torisasami4](https://pbs.twimg.com/profile_images/1102585635137679360/edE9JNpl.png)
問題文
$x > y$ を満たす正整数 $x, y$ に対し,中心が等しい半径 $x$ の円 A と半径 $y$ の円 B の $2$ つの円からなる平面図形を,「$(x, y)$-ドーナツ」と呼びます.
例として,$(3, 2)$-ドーナツを図示すると,以下のようになります.
Bob は,誕生日のプレゼントとして,$L \leq i \leq R$ かつ $1 \leq j < i$ を満たす整数組 $(i, j)$ のそれぞれについて,$(i, j)$-ドーナツを $1$ 個ずつ貰いました.
正の倍率の拡大・縮小によって互いに一致させられるドーナツを同一の種類のドーナツとみなし,互いに一致させられないドーナツを別の種類のドーナツとみなすとき,Bob が貰ったドーナツの種類数を求めてください.
$T$ 個のテストケースが与えられるので,それぞれについて答えてください.
なお,各テストケースにおいて,$L, R$ は暗号化された状態でそれぞれ整数 $\alpha, \beta$ として与えられます.各テストケースでは,以下のようにして $L, R$ を復号してから解答してください.
- $\mathrm{ans}_0 = 0, \mathrm{ans}_i=$($i$ 番目のテストケースの答え)とする.このとき,$i$ 番目のテストケースに対して,$L = \alpha \oplus \mathrm{ans}_{i - 1}, R = \beta \oplus \mathrm{ans}_{i - 1}$ のように復号できる.
ただし,$x \oplus y$ で $x$ と $y$ のビット単位 XOR を表します.
ビット単位 XOR とは
$2$ 個の非負整数 $x$ と $y$ のビット単位 XOR $x \oplus y$ は,以下のように定義されます.
- $x \oplus y$ を $2$ 進表記した際の $2^k$ の位の値は,$x, y$ それぞれを $2$ 進表記した際の $2^k$ の位の一方のみが $1$ であれば $1$,そうでなければ $0$ であるとする.
- 例えば,$3 \oplus 5 = 6$ となる.($2$ 進表記すると $011 \oplus 101 = 110$)
制約
- 入力はすべて整数である.
- $1 \leq T \leq 10^5$
- $0 \leq \alpha, \beta \leq 10^{18}$
- $2 \leq L \leq R \leq 2 \times 10^5$
入力
入力は以下の形式で標準入力から与えられる.ここで,$\mathrm{case}_i$ は $i$ 番目のテストケースを表す.
$T$ $\mathrm{case}_1$ $\mathrm{case}_2$ $\vdots$ $\mathrm{case}_T$
各テストケースは以下の形式で与えられる.
$\alpha$ $\beta$
出力
$T$ 行出力せよ.$i$ 行目には,$i$ 番目のテストケースについての答えを出力せよ.
サンプル
サンプル1
入力
5 2 3 1 7 15 15 11 200009 12158598942 12158743847
出力
3 5 9 12158598917 10159235125
$1$ つ目のテストケースについて,$\mathrm{ans}_0 = 0$ であるため,$L = 2, R = 3$ と復号できます.よって,Bob は $(2, 1)$-ドーナツ,$(3,1)$-ドーナツ,$(3, 2)$-ドーナツの $3$ 個のドーナツを貰いました.これらはすべて異なる種類のドーナツなので,答えは $3$ 種類です.
$2$ つ目のテストケースについて,$\mathrm{ans}_1 = 3$ であるため,$L = 2, R = 4$ と復号できます.Bob は $(2, 1)$-ドーナツ,$(3, 1)$-ドーナツ,$(3, 2)$-ドーナツ,$(4, 1)$-ドーナツ,$(4, 2)$-ドーナツ,$(4, 3)$-ドーナツの $6$ 個のドーナツを貰いました.$(2, 1)$-ドーナツは拡大すると $(4, 2)$-ドーナツと一致させられ,拡大・縮小により互いに一致させられるドーナツの組はこれのみであるため,ドーナツの種類は $5$ 種類となります.
$3$ つ目のテストケースについて,$\mathrm{ans}_2 = 5$ であるため,$L = 10, R = 10$ と復号できます.
$4$ つ目のテストケースについて,$\mathrm{ans}_3 = 9$ であるため,$L = 2, R = 200000$ と復号できます.
$5$ つ目のテストケースについて,$\mathrm{ans}_4 = 12158598917$ であるため,$L = 27, R = 182818$ と復号できます.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。