ABC121 D-XOR World

問題概要

入力A,Bに対して，$A xor (A + 1) xor \dots xor B$を求めよ

制約

• 入力はすべて整数
• $0 \le A \le B \le 10^{12}$

排他的論理和とは

解法

入力の制約からして，すべてのA ~ Bまでの排他的論理和を取ることはできない。排他的論理和の性質を利用する必要がある。 ある連続した偶数$a$と奇数$a + 1$を2進数で表現すると，2つの値の差異は$2^0$の箇所のみであり，$a\ xor \ (a + 1) = 1$となることがわかる。 したがって，$N = B - A + 1$として，偶数・奇数の組合せを作っていけば1の排他的論理和が$N / 2$だけ繰り返せば答えが求まる。 A,Bの偶奇によって，答えの出し方は以下の4通りになる。

A,Bともに偶数

最後の値であるBが余るので，答えは$(N - 1)\ /\ 2\ \%\ 2 \ xor \ B$となる

Aが偶数，Bが奇数

すべての値がペアを持つので，答えは$(N\ /\ 2) \% 2$となる

Aが奇数，Bが偶数

AとBがペアを持たず余るので，答えは $A\ xor \ B\ xor \ ((N - 2)\ /\ 2) \% \ 2$ となる

A,Bともに奇数

Aのみがペアを持たず余るので，答えは$(A\ xor \ (N - 1)\ /\ 2 \% \ 2$となる

A, B = map(int, input().split())
num = B - A + 1
if A % 2 == 0:
    if B % 2 == 0:
        ans = ((num - 1) // 2) % 2 ^ B
    else:
        ans = (num // 2) % 2
else:
    if B % 2 == 0:
        ans = A ^ B ^ ((num - 2) // 2) % 2
    else:
        ans = A ^ ((num - 1) // 2) % 2
print(ans)