#G1133. [GESP202509 五级] 有趣的数字和

[GESP202509 五级] 有趣的数字和

[GESP202509 五级] 有趣的数字和

题目描述

如果一个正整数的二进制表示包含奇数个 11,那么小 A 就会认为这个正整数是有趣的。

例如,77 的二进制表示为 (111)2(111)_2,包含 11 的个数为 33 个,所以 77 是有趣的。但是 9=(1001)29 = (1001)_2 包含 22 个 11,所以 99 不是有趣的。

给定正整数 l,rl, r,请你统计满足 l≤n≤rl \le n \le r 的有趣的整数 nn 之和。

输入格式

一行,两个正整数 l,rl, r,表示给定的正整数。

输出格式

一行,一个正整数,表示 l,rl, r 之间有趣的整数之和。

样例 #1

样例输入 #1

3 8

样例输出 #1

19

样例 #2

样例输入 #2

65 36248

样例输出 #2

328505490

数据范围

测试点占比 约束
40% 1≤l≤r≤1041 \le l \le r \le 10^4
30% l=1l = 1 并且 r=2k−1r = 2^k - 1,其中 kk 是大于 11 的正整数
100% 1≤l≤r≤1091 \le l \le r \le 10^9

提示

由于本题的数据范围较大,整数类型请使用 long long。