A23751. 有趣的数字和
填空题
困难
知识点
题目描述
有趣的数字和
题目描述
如果一个正整数的二进制表示包含奇数个1 ，那么小 A 就会认为这个正整数是有趣的。
例如， 7的二进制表示为（111）2 ，包含1 的个数为 3个，所以 7是有趣的。但是9=（1001）2 包含2 个1 ，所以9 不是有趣的。
给定正整数l,r ，请你统计满足l≤n≤r 的有趣的整数n之和。
输入格式
一行，两个正整数l,r ，表示给定的正整数。
输出格式
一行，一个正整数，表示 l,r之间有趣的整数之和。
样例
输入样例 1
3 8输出样例 1
19输入样例 2
65 36248输出样例 2
328505490数据范围
对于40 % 的测试点，保证1≤l≤r≤104 。
对于另外30 % 的测试点，保证l=1 并且r=2k-1 ，其中 k是大于1 的正整数。
对于所有测试点，保证1≤l≤r≤109 。
参考答案
#include <algorithm>
#include <cstdio>
using namespace std;
int l, r;
long long ans;
pair<int, long long> cal2(int n, int p) {
if (n == 0) { return {1 - p, 0}; }
if (n == 1) { return {1, p}; }
return {(n + 1) / 2, 1LL * n * (n + 1) / 4};
}
pair<int, long long> cal(int n, int p) {
if (n <= 1) { return cal2(n, p); }
long long x = 1LL << (31 - __builtin_clz(n));
auto l = cal2(x - 1, p);
auto r = cal(n - x, 1 - p);
return {l.first + r.first, l.second + r.second + x * r.first};
}
int main() {
scanf("%d%d", &l, &r);
ans -= cal(l - 1, 1).second;
ans += cal(r, 1).second;
printf("%lld\n", ans);
return 0;
}
上一题
下一题