GESP2025年9月认证C++五级真题与解析（编程题2（有趣的数字和））

🎯 一、题目理解：《谁是“有趣的数字”？》

1、🧸 小故事

小 A 很喜欢玩二进制游戏🎮
他规定了一条奇怪的规则：

👉 如果一个数字的二进制表示中
👉1 的个数是奇数
👉 那这个数字就是 ——
🌟有趣的数字

2、🌰 举例

3、老师现在给你一个区间：

[l, r]

问你：

🎯从 l 到 r 之间，所有“有趣数字”的总和是多少？

📘 二、把题目翻译成“人话”

原题（简化）：

给定两个整数 l 和 r
对区间 [l, r]
找出所有二进制中 1 的个数为奇数的数
把这些数加起来

⚠️ 三、第一反应 & 大坑

1、🧠 同学们的第一想法（很自然！）

for (int i = l; i <= r; i++) { if (二进制中1的个数是奇数) ans += i; }

2、❌ 但是！

题目里：

• l、r非常大

• r 可以到10⁹ 甚至更大

👉 这样循环：
💥直接超时！不能满分！

🌟 四、真正的挑战是什么？

这道题不是考你会不会数 1
而是考你：

🧠能不能“整体思考一大堆数字”

🧠 五、关键魔法概念 ①：奇偶性

1、✨ 重要发现

我们不关心：

• 有多少个 1

我们只关心：

• 是奇数个？还是偶数个？

2、🎈 举例

• 3 个 1 → 奇数 ✅

• 4 个 1 → 偶数 ❌

👉只分两类！

🧠 六、关键魔法概念 ②：从 0 到 n 统一算

1、🎯 超重要技巧

👉 不直接算[l, r]
👉 而是算：

sum(0 ~ r) − sum(0 ~ (l − 1))

就像：

• 从 0 数到 100

• 减去 0 数到 49

• 剩下的就是 50～100

2、🧩 伪代码 Part 1：主流程

输入 L, R 答案 = 计算(0 ~ R 的有趣数字之和) - 计算(0 ~ L-1 的有趣数字之和) 输出 答案

3、🧠 伪代码 Part 2：核心函数 calculate(n)

calculate(n) 表示：
👉 计算 0 ~ n 中
👉 所有“有趣数字”的【总和】

函数 calculate(n): 如果 n 很小（n ≤ 1）: 直接算，返回结果 找到最大的 2 的幂 x，使得 x ≤ n （例如 n=13，x=8） 第一部分： 0 ~ x-1 （最高位是 0，不影响奇偶性） 第二部分： x ~ n （最高位是 1，奇偶性会翻转） 返回： 第一部分结果 + 第二部分结果 + 第二部分中每个数都多出来的 x

4、🧠 伪代码 Part 3：小范围快速计算 small(n)

当范围非常小时，直接用数学规律算

函数 small(n): 如果 n == 0: 如果 0 是有趣的: 返回 (数量=1, 总和=0) 否则: 返回 (数量=0, 总和=0) 如果 n == 1: 判断 1 是不是有趣的 返回对应的数量和总和 如果 n ≥ 2: 有趣数字大约占一半 用公式直接算数量和总和

🧠 七、用“翻转”的方式讲给大家

我们可以这样说👇

🌟 把 0~n 的数字
🌟 从中间“一刀切开”

左边：最高位是 0
👉 不改变“有趣 / 没趣”

右边：最高位是 1
👉奇数变偶数，偶数变奇数

就像：

戴了一顶“翻转帽子” 🎩

🧠 八、使用分治递归这种方法为何很快？

1、第一层：直观想象

（1）🐌 慢方法（暴力）

想象你要数：

1 ~ 1 000 000 000

每个数字都要：

• 转成二进制

• 数 1 的个数

• 判断奇偶

• 再加到答案里

👉 就像：

数一座山的每一粒沙子
🐌🐌🐌

（2）🚀 快方法（分治递归）

这道题做了什么？

把一座山

直接切成：

• 二整块石头

• 分别再去计算着两块大石头

不用数每一粒沙

2、第二层：代码思想

我们对比两种算法 👇

（1）❌ 方法 1：暴力枚举

for i = L to R: 如果 i 是“有趣数字”: ans += i

⏱ 时间复杂度：

超时❌ 直接凉了

（2）✅ 方法 2：分治递归的算法

核心操作只有两件：

1. 找最大的 2 的幂

2. 把区间一分为二（递归）

（3）关键点来了 ❗❗❗

每一层递归，n 都在做什么？

n → n / 2

就像：

1 000 000 000 → 500 000 000 → 250 000 000 → ...

你知道这意味着什么吗？👇

3、第三层：真正“省时间”的数学原因 🔥

⚡ 时间复杂度对比

👉差了 3 千万倍！

4、🧠 为什么“2 的幂”这么神？

（1）因为在二进制中：

0 ~ (2^k - 1)

👉 每一位的 0 和 1
👉 出现次数完全对称

（2）所以：

• 有趣数字 ≈ 一半

• 总和可以用公式算

• 不用枚举

5、🎩 “翻转奇偶性”也在省时间

最高位是 1 时：

原来是奇数 → 变偶数 原来是偶数 → 变奇数

👉不用重新算二进制
👉 只用一个p变量记录就可以

🌟 九、参考程序：

#include <algorithm> #include <cstdio> using namespace std; int l, r; int ans; // 最终答案：有趣数字的总和 /* cal2(n, p) 的作用： 在【0 ~ n】这个小范围内： - 统计“有趣数字”的个数 - 统计这些有趣数字的“和” 参数说明： n：当前范围的最大值 p：表示当前“奇偶状态” p = 1：表示“1 的个数是奇数”为有趣 p = 0：表示“1 的个数是偶数”为有趣 返回值： first ：有趣数字的数量 second ：有趣数字的总和 */ pair<int, int> cal2(int n, int p) { // 只有 0 这个数 if (n == 0) { // 0 的二进制没有 1 // 如果 p = 0（偶数个 1 才算有趣），那 0 是有趣的 return {1 - p, 0}; } // 范围是 0 和 1 if (n == 1) { // 1 的二进制是 1（一个 1） // 如果 p = 1（奇数个 1 才算有趣），那 1 是有趣的 return {1, p}; } // 对于 n >= 2 的情况： // 在 0 ~ n 中，有一半左右的数满足条件 // (n + 1) / 2 ：有趣数字的数量 // n * (n + 1) / 4 ：这些数字的总和（数学公式） return {(n + 1) / 2, 1ll * n * (n + 1) / 4}; } /* cal(n, p) 的作用： 计算【0 ~ n】之间所有“有趣数字”的： - 个数 - 总和 这是一个【递归 + 分治】的函数 */ pair<int, int> cal(int n, int p) { // 小范围，直接用 cal2 解决 if (n <= 1) { return cal2(n, p); } // 找到不超过 n 的最大 2 的幂 // 例如：n = 13，x = 8（二进制 1000） int x = 1ll << (31 - __builtin_clz(n)); // 第一部分：0 ~ x-1（最高位是 0） auto left = cal2(x - 1, p); // 第二部分：x ~ n（最高位是 1） // 因为多了一个 1，奇偶性会翻转，所以 p 变成 1 - p auto right = cal(n - x, 1 - p); // 合并两部分的结果 return { left.first + right.first, // 有趣数字的总个数 left.second + right.second + x * right.first // 有趣数字的总和 }; } int main() { // 输入区间 [l, r] scanf("%d%d", &l, &r); // 先减去 [0 ~ l-1] 的有趣数字之和 ans -= cal(l - 1, 1).second; // 再加上 [0 ~ r] 的有趣数字之和 ans += cal(r, 1).second; // 输出 [l ~ r] 区间内有趣数字的总和 printf("%lld\n", ans); return 0; }

🧠 十、两个函数在干嘛？

1、参考代码里有两个函数：

1️⃣cal2(n, p)

👉 用来算：

• 数量

• 总和
  （在非常小的范围里）

2️⃣cal(n, p)

👉 用来递归拆分：

• 一半最高位是 0

• 一半最高位是 1（奇偶翻转）

2、那为什么不把cal2写进cal里？

原因 1：逻辑更清楚 🧠

cal 负责：拆问题（递归） cal2负责：算结果（公式）

分工明确，比一坨 if 好讲 👍

原因 2：减少递归层数 🚀

如果什么都递归：

• 会调用很多次

• 效率慢

• 容易爆栈

现在：

小范围 →一步到位

原因 3：这是“竞赛常见写法” 🏁

在 CCF / NOI / ICPC 里非常常见：

这是高阶程序员的习惯

3、🎈 本题特点：

👉这是“分治 + 二进制 + 奇偶性”的综合应用

🎁 十一、从五级考试层面看这道题

🌟 这题明显是一道限高题，对于五级考生挑战很大！

它在考：

🧠十二、 记忆口诀

数字太大别硬算

二进制里看奇偶

区间问题变前缀

一刀一半分着走 ✨