匿名用户·2026/5/16本题要求统计区间 ([l,r]) 内所有“有趣整数”的和。有趣整数的定义为：正整数的二进制表示中包含奇数个 (1)。
数据范围 (1 \le l \le r \le 10^9)，直接枚举会超时。我们需要一种与数的二进制表示相关的快速统计方法。这类问题通常可以利用前缀和思想：令 (f(n)) 表示 ([0,n]) 内所有有趣整数的和，则答案为 (f(r) - f(l-1))。接下来只需集中精力实现 (f(n)) 即可。
设一个整数 (x) 的二进制中 (1) 的个数的奇偶性为 (p(x))（(p(x)=1) 表示奇数，(0) 表示偶数）。(f(n)) 就是求
[
\sum_{x=0}^{n} [p(x)=1] \cdot x
]
我们可以利用二进制最高位递归地拆分区间。令 (x_{\max} = 2^k) 为不超过 (n) 的最大 (2) 的幂，那么 ([0,n]) 可以拆成两部分：
接下来分析这两块的性质。
对于所有 (k) 位二进制数（包括前导零），其中一半的数含有奇数个 (1)，一半含有偶数个 (1)，且两者的总和相等（均为总数总和的一半）。 为什么呢？
考虑“按位取反”的配对：(x) 与 (2^k - 1 - x) 互为按位取反。若 (k) 为奇数，一个数 (1) 的个数为奇数时，它的取反一定是偶数个 (1)，两者一一配对，和为 (2^k-1)；若 (k) 为偶数，奇数个 (1) 的数之间也能两两配对（除了中间一个自配对的数，但它的补数是自己，不影响总和一半的结论）。因此，无论 (k) 是多少，[0, 2^k-1] 内奇数个 (1) 的数恰好有一半，且它们的总和等于全体总和的一半。
设 (S = 0 + 1 + 2 + \dots + (2^k-1) = \frac{(2^k-1) \cdot 2^k}{2})，则奇数个 (1) 的数的和为 (S/2 = \frac{(2^k-1) \cdot 2^{k-1}}{2} = \frac{(2^k-1) \cdot 2^k}{4})，个数为 (2^{k-1})。
对于 (x = x_{\max} + y)，其中 (x_{\max} = 2^k)（二进制中仅第 (k) 位为 (1)）。此时
[
\operatorname{popcount}(x) = 1 + \operatorname{popcount}(y)
]
因此奇偶性 (p(x) = 1 - p(y))。换句话说，在剩余部分里找有趣整数，等价于在 ([0, n-x_{\max}]) 中找 (1-p) 的数，再给每个数加上偏移 (x_{\max})。设递归计算函数 (\text{cal}(n, p)) 返回 ([0,n]) 中奇偶性等于 (p) 的数的个数与总和，那么就有：
[
\text{cal}(n, p) = \text{cal_block}(x_{\max}-1, p) + \text{offset}\big(\text{cal}(n - x_{\max}, 1-p),; x_{\max}\big)
]
其中 (\text{cal_block}) 利用上面完整块的公式直接 (O(1)) 得到，而 (\text{offset}) 是将每个选中的 (y) 加上 (x_{\max})：总和增加 (x_{\max} \times \text{个数})，个数不变。
递归边界是 (n \le 1) 时直接手算返回。
利用前缀和性质：
[
\text{ans} = \text{cal}(r, 1).\text{sum} - \text{cal}(l-1, 1).\text{sum}
]
因为 (l) 可能为 (1)，所以计算 (l-1) 时需考虑 (0) 的情况。
实现函数 (\text{cal}(n, p))，返回一个 pair<long long, long long>，表示个数和总和。参数 (p) 表示要找的奇偶性（(1) 为奇数，(0) 为偶数）。
若 (n \le 1)，直接判断：
否则，求 (x = 2^{\lfloor \log_2 n \rfloor})，即 (n) 的最高位权重。
C++ 中可以用 31 - __builtin_clz(n) 得到指数，再 1 << k。
完整块：([0, x-1])
设 (m = x - 1 = 2^k - 1)，则
剩余块：递归调用 (\text{cal}(n - x, 1-p))，得到 ((cnt_R, sum_R))
返回合并后的结果。
题目要求统计的是正整数，但我们的前缀和从 (0) 开始。注意 (0) 不是正整数，但其二进制有 (0) 个 (1)（偶数），所以对结果无影响。当 (l=1) 时 (l-1=0)，(\text{cal}(0, 1)) 返回的个数为 (0)，和为 (0)，答案正确。
每次递归将问题规模 (n) 减少最高位的一层，即新的 (n' = n - 2^{\lfloor \log_2 n \rfloor} < 2^{\lfloor \log_2 n \rfloor})，规模至少减半。因此递归深度为 (O(\log n))。每次递归内部仅进行若干 (O(1)) 运算，总时间复杂度为 (O(\log n))，对于 (n \le 10^9) 绰绰有余。空间复杂度为递归所需的栈空间，同样 (O(\log n))。
下面是完整的 C++ 实现，附有详细注释：
cpp1#include <cstdio> 2#include <algorithm> 3using namespace std; 4 5typedef long long ll; 6 7// 快速计算完整块 [0, n] 其中 n = 2^k - 1 的情况 8// 参数 p 表示要找的奇偶性 (1:奇数个1, 0:偶数个1) 9// 返回值：{个数, 总和} 10pair<ll, ll> cal2(int n, int p) { 11 if (n == 0) return {1 - p, 0}; // 只有0，它是偶数 12 if (n == 1) return {1, p}; // 0和1，奇数个1的数就是p本身的值 13 // 完整块公式：个数 = (n+1)/2，总和 = n*(n+1)/4 14 return {(n + 1) / 2, 1LL * n * (n + 1) / 4}; 15} 16 17// 递归计算 [0, n] 中奇偶性为 p 的数的个数与总和 18pair<ll, ll> cal(int n, int p) { 19 if (n <= 1) return cal2(n, p); // 边界直接计算 20 int x = 1 << (31 - __builtin_clz(n)); // 不超过 n 的最大 2 的幂 21 auto L = cal2(x - 1, p); // 低位完整块 22 auto R = cal(n - x, 1 - p); // 高位剩余块，奇偶性翻转 23 // 合并：个数相加；总和 = 左边总和 + 右边总和 + 偏移 x * 右边的个数 24 return {L.first + R.first, L.second + R.second + x * R.first}; 25} 26 27int main() { 28 int l, r; 29 scanf("%d%d", &l, &r); 30 ll ans = 0; 31 // 前缀和相减得到区间 [l, r] 的答案 32 ans -= cal(l - 1, 1).second; 33 ans += cal(r, 1).second; 34 printf("%lld\n", ans); 35 return 0; 36}
__builtin_clz(n)：GCC 内置函数，返回 (n) 的二进制前导零个数。对于正整数 (n)，31 - __builtin_clz(n) 得到最高位所在的索引（0‑based）。例如 (n=6)（110₂），前导零 29 个，31-29=2，1<<2=4 正是最高位。cal2 专门处理 (n = 2^k - 1) 形式的完整块。当 (n > 1) 时直接套公式，这个公式对奇数个 (1) 和偶数个 (1) 同样适用。cal 通过不断“剥掉”最高位，将问题转化为规模更小的子问题，代码非常简洁。ans = cal(r,1).second - cal(l-1,1).second 利用前缀和求出区间和，别忘记使用 long long 存储。本题利用二进制最高位进行分治，结合完整区间内的对称性公式，实现了 (O(\log n)) 的极优解法。这种“按位拆分”的思想在数位统计问题中非常常见，值得熟练掌握。