Coincidence

题目描述

给定整数 $L$ 和 $R$ 。求满足条件的整数对 $(x, y)$ 的数量（按 $10^9 + 7$ 取模），其中 $L \leq x \leq y \leq R$ ，并且 $y$ 除以 $x$ 的余数等于 $y \text{ XOR } x$ 。

什么是 $\text{ XOR }$？

整数 $A$ 和 $B$ 的 XOR， $A \text{ XOR } B$ ，定义如下：

当 $A \text{ XOR } B$ 用二进制表示时，第 $2^k$ 位（ $k \geq 0$ ）的位为 $1$ 当且仅当 $A$ 或 $B$ （但不是两者）在第 $2^k$ 位上有 $1$ ，否则为 $0$ 。

例如， $3 \text{ XOR } 5 = 6$ 。（用二进制表示： $011 \text{ XOR } 101 = 110$ 。）

标准输入的给定格式如下： $L$ $R$

输出满足条件的整数对 $(x, y)$ 的数量，按 $10^9 + 7$ 取模。

2 3

10 100

1 1000000000000000000

68038601

$1 \leq L \leq R \leq 10^{18}$ 有三对满足条件： $(2, 2)$ 、 $(2, 3)$ 、和 $(3, 3)$ 。
注意结果要对 $10^9 + 7$ 取模。

标签: AtCoder|abc138F

AtCoder|abc138F