【GESP】C++二级真题 luogu-B4357 [GESP202506 二级] 幂和数

GESP C++二级，2025年6月真题，多重循环，难度★✮☆☆☆。个人认为，对于低年级的2级考生来说，相对较难。

luogu-B4357 [GESP202506 二级] 幂和数

题目要求

题目描述

对于正整数 $n$，如果 $n$ 可以表为两个 $2$ 的次幂之和，即 $n = 2^x + 2^y$（$x, y$ 均为非负整数），那么称 $n$ 为幂和数。

给定正整数 $l, r$，请你求出满足 $l \leq n \leq r$ 的整数 $n$ 中有多少个幂和数。

输入格式

一行，两个正整数 $l, r$，含义如上。

输出格式

输出一行，一个整数，表示 $l, r$ 之间幂和数的数量。

输入输出样例 #1

输入 #1

2 8

输出 #1

6

输入输出样例 #2

输入 #2

10 100

输出 #2

20

说明/提示

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

---

题目分析

解题思路

本题的解题思路如下：

1. 问题本质：
   • 输入两个正整数 $l,r$，表示一个整数范围
   • 需要计算范围内有多少个数可以表示为两个2的幂之和
2. 解题关键：
   • 核心思路 - 枚举与判断：
     1. 遍历范围内的每个数 $n$：
        • 对于每个数，尝试用两个2的幂之和表示
        • 枚举两个幂次 $x,y$，计算 $2^x + 2^y$ 是否等于 $n$
     2. 优化方案：
        • 由于 $2^{14} > 10^4$，幂次最大只需要枚举到14
        • 可以预先计算所有可能的幂和，再判断是否在范围内
3. 复杂度分析：
   • 方法一（暴力）：$O((r-l+1) \times \log^2{r})$，需要遍历每个数并尝试所有幂次组合
   • 方法二（预计算）：$O(\log^2{r})$，只需要枚举所有可能的幂次组合
   • 空间复杂度：$O(1)$，只需要存储几个计数变量

---

示例代码

方法一、纯暴力

#include <cmath>
#include <iostream>


int main() {
    // 定义输入的范围边界
    int l, r;
    // 从标准输入读取 l, r
    std::cin >> l >> r;
    // 计数器，记录幂和数的个数
    int count = 0;
    // 遍历范围内的每个数
    for (int i = l; i <= r; i++) {
        // 标记是否找到符合条件的幂和
        bool flag = false;
        // 第一个2的幂次数
        int x = 0;
        // 枚举第一个2的幂，直到超过范围上限
        while (std::pow(2, x) <= r) {
            // 第二个2的幂次数
            int y = 0;
            // 枚举第二个2的幂，直到超过范围上限
            while (std::pow(2, y) <= r) {
                // 判断当前两个2的幂之和是否等于目标数i
                if (std::pow(2, x) + std::pow(2, y) == i) {
                    flag = true;
                    count++;
                } else {
                    // 不相等时增加第二个幂次数
                    y++;
                }
                // 如果找到符合条件的组合，跳出内层循环
                if (flag) {
                    break;
                }
            }
            // 如果找到符合条件的组合，跳出外层循环
            if (flag) {
                break;
            } else {
                // 未找到时增加第一个幂次数
                x++;
            }
        }
    }
    // 输出结果
    std::cout << count << std::endl;
    return 0;
}       

方法二、范围内检索（实际上$2^{14} = 16384$，已经超过了$10^4$）

#include <iostream>
#include <cmath>

int main() {
    // 定义输入的范围边界
    int l,r;
    // 从标准输入读取 l, r
    std::cin >> l >> r;
    // 计数器，记录幂和数的个数
    int count = 0;
    // 外层循环遍历第一个2的幂次数，最大不超过31（2^31已经超过10^4）
    for (int i = 0; i<=31; i++) {
        // 内层循环从i开始遍历第二个2的幂次数，避免重复计数
        for (int j = i; j<=31; j++) {
            // 计算当前两个2的幂之和
            int num = std::pow(2,i) + std::pow(2,j);
            // 判断和是否在给定范围内
            if (num >= l && num <= r) {
                // 如果在范围内，计数器加1
                count++;
            }
        }
    }
    // 输出结果
    std::cout << count << std::endl;
    return 0;
}

---

所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code

GESP各级别考纲、真题讲解、知识拓展和练习清单等详见【置顶】【GESP】C++ 认证学习资源汇总

“luogu-”系列题目已加入洛谷Java、C++初学团队，作业清单，可在线评测，团队名额有限。

“bcqm-”系列题目可在编程启蒙题库进行在线评测。

欢迎加入：Java、C++、Python技术交流QQ群(982860385)，大佬免费带队，有问必答

欢迎加入：C++ GESP/CSP认证学习QQ频道，考试资源总结汇总

欢迎加入：C++ GESP/CSP学习交流QQ群(688906745)，考试认证学员交流，互帮互助

GESP/CSP 认证学习微信公众号