返回首页 返回题库

有趣的数字和

C++ 中等 GESP五级真题 #位运算#分治#递归

题目描述

题面描述

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

例如,7的二进制表示为,包含1的个数为3个,所以7是有趣的。但是包含2个1,所以9不是有趣的。

给定正整数,请你统计满足的有趣的整数之和。

输入格式

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

输出格式

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

样例1

输入:

3 8

输出:

19

样例2

输入:

65 36248

输出:

328505490

数据范围

对于40%的测试点,保证。

对于另外30%的测试点,保证并且,其中是大于1的正整数。

对于所有测试点,保证。

提示

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

时间限制

1.0 s

内存限制

512.0 MB

💡 查看提示(先自己想一想再看)
本题考察位运算、分治思想与递归实现。核心思路是先计算1到x的有趣数字之和,再通过前缀和思想得到l到r的结果。利用二进制最高位的性质,将问题拆分为最高位为0和最高位为1的两部分递归求解,避免逐个枚举数字以应对1e9的大数据范围。注意使用long long类型防止整数溢出。
⚙ 开始做这道题 0 人做过 · 0 收藏 · 3 浏览

讨论(0)