GESP2025年6月认证C++二级( 第三部分编程题 2、幂和数）

《幂和数王国的秘密》

📖 一、故事背景：幂和数王国 🏰

1、在数字大陆上，有一种特别神奇的数字，叫做——

✨ 幂和数

2、国王规定：

如果一个数 N
可以写成
两个 2 的幂相加

比如：
N = 2^a + 2^b

那么，N 就是幂和数！

3、你的任务是：

🎯 在一个范围 [L, R] 里，找出一共有多少个幂和数

🧠 二、先把“幂”讲明白（超级关键）

1、什么是 2 的幂？

就是一直乘 2：

2、📌 记住一句话：

从 1 开始，一直 ×2

🧩 三、幂和数到底长什么样？

🌟 举几个例子

• 3 = 1 + 2 → ✔ 幂和数

• 5 = 1 + 4 → ✔

• 6 = 2 + 4 → ✔

• 7 ❌（不是两个 2 的幂相加）

🧠 四、题目真正让你干什么？

1、题目输入：

L R

2、意思是：

👉 从 L 到 R
👉 数一数
👉 有多少个数
👉 可以写成 2^a + 2^b

🧩 五、千万不要用“笨方法”！

❌ 错误思路（同学们最容易想到）

对每个数 N
再去试所有 a、b
看能不能拼出来

❌ 太慢！
❌ 太乱！
❌ 容易写炸！

🌟 六、聪明魔法师的思路

🎯 换个角度想！

👉 不是去猜 N
👉 而是：

先生成所有的 2^a + 2^b

再看看它落不落在 [L, R] 里

🧠 七、怎么生成所有的 2^a + 2^b？

魔法规则

• a 从 1 开始，一直 ×2 （外循环）

• b 从 a 开始，一直 ×2 （内循环）

• 只要和 <= R，就继续

🧮 八、用小例子走一遍（方便理解）

1、假设输入：

L = 2, R = 10

2、所有 2 的幂：

1, 2, 4, 8

3、组成幂和数：

4、👉 在 [2,10] 里的有：
2,3,4,5,6,8,9,10

👉 一共 8 个

💻 九、参考程序

#include <iostream>
using namespace std;

int main() {
int L, R;
cin >> L >> R;

int cnt = 0;

// 第一个 2 的幂
for (int a = 1; a <= R; a *= 2) {
// 第二个 2 的幂（从 a 开始，防止重复）
for (int b = a; b <= R; b *= 2) {
int sum = a + b;

// 如果在范围内，就计数
if (sum >= L && sum <= R) {
cnt++;
}
}
}

cout << cnt << endl;
return 0;
}

🧩 十、逐句拆解

1、🔹 为什么 a *= 2？

for (int a = 1; a <= R; a *= 2)

👉 表示：
1 → 2 → 4 → 8 → 16 …

2、🔹 为什么 b = a 开始？

for (int b = a; b <= R; b *= 2)

👉 防止：

• 1 + 2

• 2 + 1

被算两次 ❗

🚨 十一、考场最容易扣分的 4 个坑

❌ 写成 a++（直接错）
❌ b 从 1 开始（会重复）
❌ 忘了判断 sum <= R
❌ 用 pow()（浮点数，危险）

🏆 十二、本题总结

📌

• 幂 = 从 1 开始 ×2

• 幂和数 = 两个幂相加

• 思路：先造，再筛

• 防重复：第二个从第一个开始