P14074 [GESP202509 五级] 有趣的数字和

题目背景

为保证只有时间复杂度合理的算法通过本题，本题时限下调。

题目描述

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

例如，$7$ 的二进制表示为 $(111{)}_2$，包含 $1$ 的个数为 $3$ 个，所以 $7$ 是有趣的。但是 $9=(1001{)}_2$ 包含 $2$ 个 $1$，所以 $9$ 不是有趣的。

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

输入格式

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

输出格式

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

输入输出样例 #1

输入 #1

3 8

输出 #1

19

输入输出样例 #2

输入 #2

65 36248

输出 #2

328505490

说明/提示

【数据范围】

对于 $40\%$ 的测试点，保证 $1\le l\le r\le 10^4$。

对于另外 $30\%$ 的测试点，保证 $l=1$ 并且 $r=2^k-1$，其中 $k$ 是大于 $1$ 的正整数。

对于所有测试点，保证 $1\le l\le r\le 10^9$。

【提示】

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

题解链接

https://www.luogu.com.cn/article/zqw5xs13

解题思路

需要计算区间 [l, r] 内所有“有趣的数”的和。根据题目描述：

一个数是“有趣的”，当且仅当其二进制表示中 1 的个数是奇数。

每四个连续的数 4n, 4n+1, 4n+2, 4n+3 中，有趣的数的和固定为 8n + 3。 方法思路 前缀和优化： 定义 func(k) 为 1 到 k 的所有有趣的数的和。

区间 [l, r] 的和可以通过 func(r ) - func(l - 1) 计算。 分组处理： 将数字按 4 分组，每组 4n 到 4n+3 的和为 8n + 3。 完整组的和可以直接用公式计算，剩余不足 4 的数单独判断。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
bool func1(ll x){	//判断当前数的位数 
	ll cnt = 0;
	for(ll i = 0; i <= 32; i++){
		if((x >> i) & 1 && x >= 0) cnt++;		//cnt是1的数量 
	}
	
	if(cnt % 2 != 0) return true;
	return false;
}
ll func(ll x){		//求 1 ~ x的和  
	ll sum = 0, a = x / 4;	//a代表一共有几个四块
	
	//整数块 
	for(ll i = 0; i <= a - 1; i++){	//从0块开始 
		sum += 8 * i + 3;	//推导每四块的和是 8 * 块编号 + 3 
	}
	
	//剩下的块
	for(ll i = 4 * a; i <= x; i++){
		if(func1(i)){
			sum += i;
		} 
	} 
	return sum; 
}
int main() {
    long long l, r;
    cin >> l >> r; 
    cout << func(r) - func(l - 1) << endl;
    return 0;
}