← 返回题目列表

AtCoder · toyota2023spring_final_c

C. 统计能整除异或的数

中文机器翻译题面 查看原题

配点 : 500 点

問題文

整数 L,R 。 满足下列条件的一组整数 请数一下 (A,B) 的数量。

  • L \leq A < B \leq R
  • A 是 给出了 A \oplus B 整除。
  • B 是 给出了 A \oplus B 整除。

然而,这里 \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 。
例如,3 \oplus 5 = 6 (二进制表示法: 011 \oplus 101 = 110)。
一般情况 k 非负整数 p_1, p_2, p_3, \dots, p_k 按位 \mathrm{XOR} 是 给出了 (\dots ((p_1 \oplus p_2) \oplus p_3) \oplus \dots \oplus p_k) ,即 可以证明 p_1, p_2, p_3, \dots, p_k 不依赖于顺序。

制約

  • 1 \leq L < R \leq 10^{18}
  • R-L \leq 10^6
  • 所有输入值均为整数

入力

输入是按以下格式从标准输入给出的。

L R

出力

输出答案。


入力例 1

3 6

出力例 1

2

(A,B)=(4,5) 和 在 (A,B)=(4,6) 满足条件。 给出了


入力例 2

1 100

出力例 2

124

入力例 3

999000000 1000000000

出力例 3

1726239