洛谷 P14074：[GESP202509 五级] 有趣的数字和 ← 前缀和

【题目来源】https://www.luogu.com.cn/problem/P14074【题目描述】如果一个正整数的二进制表示包含奇数个 1那么小 A 就会认为这个正整数是有趣的。例如7 的二进制表示为 111包含 1 的个数为 3 个所以 7 是有趣的。但是9 的二进制表示为 1001包含 2 个 1所以 9 不是有趣的。给定正整数 lr请你统计满足 l≤n≤r 的有趣的整数 n 之和。【输入格式】一行两个正整数 l,r表示给定的正整数。​​​​​​​【输出格式】一行一个正整数表示 l,r 之间有趣的整数之和。【输入样例】65 36248​​​​​​​【输出样例】328505490​​​​​​​【数据范围】对于 40% 的测试点保证 1≤l≤r≤10^4。对于另外 30% 的测试点保证 l1 并且 r2^k−1其中 k 是大于 1 的正整数。对于所有测试点保证 1≤l≤r≤10^9。【算法分析】● 规律每连续四个数 4n、4n1、4n2、4n3 构成一组每组内有趣数之和恒为 8n3。​​​​​​​证明一组连续四个数 4n、4n1、4n2、4n3 的二进制表示如下4nxxxx004n1xxxx014n2xxxx104n3xxxx11可见这四个数后两位中 1 的个数依次为 0、1、1、2。设这四个数 4n、4n1、4n2、4n3 高位部分 4n 的二进制表示 xxxx 有 p 个 1。若 p 为偶数则有趣数为 4n1、4n2它们的和(4n1)(4n2)8n3。若 p 为奇数则有趣数为 4n、4n3它们的和4n(4n3)8n3。因此无论高位如何每组 4 个数的有趣数和恒为 8n3。● 在上述基础上利用前缀和可以高效求解。否则直接枚举必然 TLE。【算法代码】#includebits/stdc.h using namespace std; typedef long long LL; bool cal(LL x) { LL cnt0; while(x) { if(x1) cnt; x1; } if(cnt1) return true; return false; } LL preSum(LL x) { LL sum0,nx/4; for(LL i0; in-1; i) { sum8*i3; } for(LL i4*n; ix; i) { if(cal(i)) sumi; } return sum; } int main() { LL le,ri; cinleri; coutpreSum(ri)-preSum(le-1)endl; return 0; } /* in:3 8 out:19 */【参考文献】https://www.luogu.com.cn/problem/solution/P14074https://aiot.csdn.net/69df646354b52172bc6a17af.html