/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 300 点
問題文
整数 N,L,R が与えられます． 以下の条件を両方満たす整数 x の個数を数えてください．
- L \leq x \leq R
- (x \oplus N) < N （ここで \oplus はビット単位 \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 である。
制約
- 1 \leq N \leq 10^{18}
- 1 \leq L \leq R \leq 10^{18}
- 入力される値はすべて整数である
入力
入力は以下の形式で標準入力から与えられる．
N L R
出力
答えを出力せよ．
入力例 1
2 1 2
出力例 1
1
x=1 の場合，L \leq x \leq R は満たしますが，(x \oplus N) < N は満たしません． x=2 の場合，両方の条件を満たします． 他に条件を満たす x は存在しません．
入力例 2
10 2 19
出力例 2
10
入力例 3
1000000000000000000 1 1000000000000000000
出力例 3
847078495393153025
Score : 300 points
Problem Statement
Given are integers N, L, and R. Count the number of integers x that satisfy both of the following conditions.
- L \leq x \leq R
- (x \oplus N) < N (Here, \oplus denotes the bitwise \mathrm{XOR}.）
What is the bitwise \mathrm{XOR}?
The bitwise \mathrm{XOR} of integers A and B, A\oplus B, is defined as follows:
- When A\oplus B is written in base two, the digit in the 2^k's place (k \geq 0) is 1 if exactly one of A and B is 1, and 0 otherwise.
Constraints
- 1 \leq N \leq 10^{18}
- 1 \leq L \leq R \leq 10^{18}
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N L R
Output
Print the answer.
Sample Input 1
2 1 2
Sample Output 1
1
For x=1, L \leq x \leq R is satisfied, but (x \oplus N) < N is not. For x=2, both conditions are satisfied. There is no other x that satisfies the conditions.
Sample Input 2
10 2 19
Sample Output 2
10
Sample Input 3
1000000000000000000 1 1000000000000000000
Sample Output 3
847078495393153025