← 返回题目列表

Codeforces · 215/E

E. 期刊编号

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

如果非空字符串 s 仅由字符“0”和“1”组成,则该字符串 s 称为二进制字符串。让我们从 1 到字符串的长度对二进制字符串 s 的字符进行编号,并将字符串 s 中的第 i 个字符表示为 si。

长度为 n 的二进制串 s 是周期性的,如果有一个整数 1 ≤ k < n 使得:

- k 是数字 n 的除数
- 对于所有 1 ≤ i ≤ n - k,满足以下条件:si = si + k

例如,二进制字符串“101010”和“11”是周期性的,而“10”和“10010”则不是。

如果正整数 x 的二进制表示形式(不带前导零)是周期字符串,则该正整数 x 是周期的。

你的任务是计算,从l到r(包括两端)的区间内有多少个周期数。

输入

单个输入行包含两个整数 l 和 r (1 ≤ l ≤ r ≤ 1018)。数字之间用空格分隔。

请不要使用 %lld 说明符在 С++ 中读取或写入 64 位整数。最好使用 cin、cout 流或 %I64d 说明符。

输出

打印一个整数,显示从 l 到 r 的区间内有多少个周期数(包括两端)。

示例

输入 #1

1 10

输出 #1

3

输入 #2

25 38

输出 #2

2

注意

第一个样本中的周期数为 3、7 和 10。

在第二个样本中,周期数为 31 和 36。