幂和数：正向枚举与集合去重

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

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

输入格式

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

输出格式

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

样例

输入样例 1

2 8

输出样例 1

6

输入样例 2

10 100

输出样例 2

20

数据范围

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

这道题要求我们在区间 $[l, r]$ 内找出所有能够表示为两个 2 的非负整数次幂之和的数（即 $n = 2^x + 2^y$，$x, y \ge 0$）。

结合数据范围（$1 \le l \le r \le 10^4$），我们可以发现问题规模非常小，完全可以用枚举 + 预处理的方法轻松解决。

核心思路

明确变量范围

因为 $2^{13} = 8192 < 10^4$ 且 $2^{14} = 16384 > 10^4$，所以 $x$ 和 $y$ 的取值范围只需要从 $0$ 枚举到 $14$ 即可。

生成所有“幂和数”

• 使用双重循环分别枚举 $x$ 和 $y$（$0 \le x, y \le 14$）。
• 计算 $n = 2^x + 2^y$。
• 考虑到 $2^x + 2^y$ 和 $2^y + 2^x$ 是等价的，且不同的 $(x, y)$ 组合可能会算出相同的 $n$（例如 $2^0 + 2^2 = 5$ 与 $2^2 + 2^0 = 5$），我们需要去重。
• 可以使用 std::set 或一个标记数组 bool vis[20005] 来记录哪些数是幂和数。

统计答案

遍历区间 $[l, r]$ 中的每一个整数 $i$，如果 $i$ 是幂和数，答案计数器 ans 加 1。

参考代码

#include <iostream>
#include <set>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int l, r;
    if (!(cin >> l >> r)) return 0;

    // 用 set 存储所有不重复的幂和数
    set<int> st;

    // 枚举 x 和 y (2^14 = 16384，已覆盖 10^4)
    for (int x = 0; x <= 14; ++x) {
        for (int y = 0; y <= 14; ++y) {
            int val = (1 << x) + (1 << y);
            st.insert(val);
        }
    }

    // 统计在 [l, r] 范围内的个数
    int ans = 0;
    for (int i = l; i <= r; ++i) {
        if (st.count(i)) {
            ans++;
        }
    }

    cout << ans << "\n";

    return 0;
}

复杂度分析

• 时间复杂度：
  • 生成幂和数：双重循环次数为 $15 \times 15 = 225$ 次，每次插入 set 的时间为 $O(\log k)$，耗时极短（微秒级）。
  • 统计答案：循环 $r - l + 1$ 次，每次在 set 中查找时间复杂度为 $O(\log k)$。
  • 总体时间复杂度：$O((r - l) \log k)$，远低于 1 秒限制。
• 空间复杂度：
  • set 中最多存入 100 多个不重复的数，空间复杂度为 $O(1)$。