Ccmmutty logo
Commutty IT
0 pv2 min read

ABC121 D-XOR World

https://cdn.magicode.io/media/notebox/blob_w6hoUoB

問題概要

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

制約

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

排他的論理和とは

解法

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

A,Bともに偶数

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

Aが偶数,Bが奇数

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

Aが奇数,Bが偶数

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

A,Bともに奇数

Aのみがペアを持たず余るので,答えは(A xor (N1) / 2% 2(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)

Discussion

コメントにはログインが必要です。