B4356 [GESP202506 二级] 幂和数

chen_zhe · 2025-06-29 13:16:41 · 题解

欢迎报名洛谷网校，报名课程可以获得对应组别的知识点讲解与答疑服务，期待和大家一起进步！点击图片即可报名。

:::align{center} :::

本题介绍三种做法，每一种做法都可以通过本题。第二种做法和第三种做法都有优秀之处。

最直接的做法（足以通过本题）

知识点：循环嵌套、数学库 pow 函数。

这是最直观的思路。题目要求我们找出在 l\leq n\leq r 区间内的幂和数，那么我们可以遍历这个区间中的每一个整数 i，然后判断 i 是否为一个幂和数。

如何判断一个数 i 是不是幂和数呢？根据定义，我们需要检查是否存在非负整数 x, y 使得 2^x + 2^y = i。因此，我们可以再次使用枚举法，枚举所有可能的 x 和 y 的组合，计算出 2^x + 2^y 的值，并与当前的数 i 进行比较。计算 2^x，可以使用 pow 函数，即 pow(2.0, x) 完成。

那么 x 和 y 的枚举范围是多少呢？由于题目中 r 的最大值为 10^4，而 2^{13} = 8192，2^{14} = 16384，所以 2^x 和 2^y 都不可能超过 10^4。这意味着 x 和 y 的取值范围不会超过 14。我们可以安全地将 x 和 y 的枚举范围设定为 0 到 14。如果让 x,y 的枚举范围大很多（比如说枚举到 n），那么 pow(2.0, x)，pow(2.0, y) 的结果就会超过 int 类型能容纳的范围而产生错误。

参考代码：

for (________) { // 枚举 l~r 的每一个数
    bool flag = false;
    for (________) { // 枚举 x
        int px = ________; // 计算 2 的 x 次方
        for (________) { // 枚举 y
            int py = ________; // 计算 2 的 y 次方
            if (________) // 判断是否是幂和数
                ________;
        }
    }
    ________; // 更新答案
}

优化一重循环

第一种方法是对每一个数进行“分解”尝试，效率较低。我们可以逆向思考：与其判断一个数能否被凑成，不如我们主动去“凑”出所有的幂和数，然后看它们中有多少个落在了 [l, r] 区间内。

我们知道，所有的幂和数都由 2^x + 2^y 生成。根据上一种方法的分析，x 和 y 的取值范围很小（0 到 14 即可覆盖所有 10^4 以内的幂和数）。因此，我们可以直接枚举所有可能的 (x, y) 组合，生成对应的幂和数。

为了避免重复计数（例如 2^3+2^5 和 2^5+2^3 是同一个数），我们可以规定 x \le y。

有的同学可能会觉得，这需要数组（GESP 三级）标记一个数是否会被多次产生。实际上并不需要。重要结论是：一个幂和数，在规定了 x \le y 的情况下，产生的方式是唯一的。因此，直接使用循环计数即可。

for (________) { // 枚举 x
    int px = ________; // 计算 2 的 x 次方
    for (________) { // 枚举 y
        int py = ________; // 计算 2 的 y 次方
        if (________) // 判断生成的幂和数是否在 l~r 区间
            ________
    }
}

二进制

知识点：进制（GESP 三级）。

我们来观察一个幂和数 n = 2^x + 2^y 的二进制形式：

• 如果 x \neq y，不妨设 x > y。那么 2^x 的二进制表示是在第 x 位为 1，其余位为 0；2^y 的二进制表示是在第 y 位为 1，其余位为 0。由于 x \neq y，这两个数相加时不会产生进位，所以 n 的二进制表示中恰好有两位是 1（分别在第 x 位和第 y 位）。例如，10 = 2^3 + 2^1，其二进制为 1010，有两个 1。
• 如果 x = y，那么 n = 2^x + 2^x = 2^{x+1}。此时 n 本身就是一个 2 的幂，它的二进制表示中恰好只有一位是 1。例如，8 = 2^2 + 2^2 = 2^3，其二进制为 1000，只有一个 1。

综上所述，一个正整数 n 是幂和数，当且仅当它的二进制表示中 1 的个数小于或等于 2。同时，我们知道最小的幂和数是 2，所以我们需要排除 n=1 的情况。

因此，问题被转化为：统计在 [l, r] 区间内，有多少个数 i(i \geq 2) 满足其二进制中 1 的个数不多于 2 个。

在 C++（仅限 GCC 编译器）中，判断一个整数 x 中，二进制表示有多少个 1，可以使用内置函数 __builtin_popcount(i) 来高效地完成这个操作。在 C++20（比赛不支持）中，可以使用 std::popcount(i) 函数高效完成这个操作（需要头文件 #include <bit>）。

参考代码：

for (________) {
    int p = ________; // 计算二进制表示有多少个 1
    if (________)
        ________; // 统计答案
}