# ABC121 D - XOR World (opens new window)

# 概要

$f(A,B)$ を $A, A+1, ..., B$ の排他的論理和(XOR)とする
$f(A,B)$ を求めよ

# 思考

問題を見て $f(0,B) - f(0,A-1)$ な気がする
制約を見ると $O(logN)$ か $O(1)$ らしい
手元で実験する
桁ごとで見ていくと良さそう
実装する
入力例1の時点で詰まる

ここで30分終了, 時間をあけてもう一度書き直す

書き直しても入力例1が通らない

さらに1時間経過してもわからないので, 解説を見る

$f(0,B) - f(0,A-1)$ ではない
$f(0,B)$ $f (0, B)$ xor $f(0,A-1)$ $f (0, A - 1)$
- a xor b = cからc xor b = aが求められる
1桁ごとに1がいくつ出るかを求めれば良い
- 1が出た数の偶奇で判定できる

# 他の解法(editorial)

隣り合う数字のxorをとると1になることがわかる。これは実験すればわかる。

例えばn=5の時は

$1 xor 2 xor 3 xor 4 xor 5$
$= (0 xor 1) xor (2 xor 3) xor (4 xor 5)$
$= 1 xor 1 xor 1$
$= 1$

のように求められる。

従って, この性質を用いれば $O(1)$ で解ける。

# 提出

$O(logN)$ $O (l o g N)$ 解法
- 提出 #7467018 (opens new window)
$O(1)$ $O (1)$ 解法
- 提出 #7467185 (opens new window)

# 気づいたこと

同じ処理が生まれる時は関数化すると綺麗に書ける
- 今回のように関数で書ける場合はまさにそれ
上限をギリギリにしなくても良い場合は余裕を持ってやると楽