atcoder#ARC129A. [ARC129A] Smaller XOR

[ARC129A] Smaller XOR

配点 : 300300

問題文

整数 N,L,RN,L,R が与えられます. 以下の条件を両方満たす整数 xx の個数を数えてください.

  • LxRL \leq x \leq R
  • (xN)<N(x \oplus N) < N (ここで \oplus はビット単位 XOR\mathrm{XOR} 演算を表す)
ビット単位 $\mathrm{XOR}$ 演算とは

整数 $A, B$ のビット単位 $\mathrm{XOR}$$A \oplus B$ は、以下のように定義されます。

  • $A \oplus B$ を二進表記した際の $2^k$ ($k \geq 0$) の位の数は、$A, B$ を二進表記した際の $2^k$ の位の数のうち一方のみが $1$ であれば $1$、そうでなければ $0$ である。
例えば、3 \oplus 5 = 6 となります (二進表記すると: 011 \oplus 101 = 110)。

制約

  • 1N10181 \leq N \leq 10^{18}
  • 1LR10181 \leq L \leq R \leq 10^{18}
  • 入力される値はすべて整数である

入力

入力は以下の形式で標準入力から与えられる.

NN LL RR

出力

答えを出力せよ.

2 1 2
1

x=1x=1 の場合,LxRL \leq x \leq R は満たしますが,(xN)<N(x \oplus N) < N は満たしません. x=2x=2 の場合,両方の条件を満たします. 他に条件を満たす xx は存在しません.

10 2 19
10
1000000000000000000 1 1000000000000000000
847078495393153025