幂和数：逆向构造与直接计数

对于正整数 $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]$ 区间内的每一个数字 $n$，然后再去判断 $n$ 能不能拆成两个 $2$ 的次幂之和。但这种“正向检查”不仅逻辑繁琐，效率也较低。

我们可以换个角度逆向思考：

• 题目要求的数具有特定的结构：$n = 2^x + 2^y$。
• 在数据范围 $r \le 10^4$ 下，$2$ 的次幂增长极快（$2^0=1, 2^1=2, \dots, 2^{13}=8192, 2^{14}=16384$），能用到的加数不超过 15 个！
• 结论：既然符合条件的加数少之又少，不如直接把所有可能的加数拼起来，构造出所有的幂和数，再看它们是否落在 $[l, r]$ 区间内。

核心思想

如何生成所有 $2$ 的次幂？

定义第一个加数为 $a = 2^x$，第二个加数为 $b = 2^y$。

我们可以让变量从 $1$ 开始，每次通过 *= 2 递推：

• $a$ 的变化轨迹：$1 \to 2 \to 4 \to 8 \to 16 \dots$
• $b$ 的变化轨迹：$1 \to 2 \to 4 \to 8 \to 16 \dots$

如何优雅地“去重”？

如果无脑双重循环枚举 $a$ 和 $b$，算出来的 $2^1 + 2^3 = 10$ 和 $2^3 + 2^1 = 10$ 会造成重复计数。

为了避免这种顺序上的重复，我们强制规定 $x \le y$（即 $a \le b$）：

• 让内层循环的 $b$ 直接从 $a$ 的当前值开始递增枚举（b = a）。
• 数学性质保证：对于任意两个不相等的次幂组合，二进制下的 $1$ 出现的位置不同，因此只要限定 $a \le b$，每一个唯一的二进制幂和数就只会被构造出来恰好一次。

算法步骤拆解

1. 输入区间边界 $l$ 和 $r$，初始化答案计数器 ans = 0。
2. 外层循环：枚举第一个加数 $a = 2^x$，从 $a = 1$ 开始，只要 $a \le r$，每次循环后 $a$ 乘以 $2$。
3. 内层循环：枚举第二个加数 $b = 2^y$，从 $b = a$ 开始（限定 $a \le b$ 防重），只要 $b \le r$，每次循环后 $b$ 乘以 $2$。
4. 计算与判断：
   • 计算构造出的幂和数 $n = a + b$。
   • 如果 $l \le n \le r$，说明这个数落在目标区间内，让 ans++。
5. 循环结束，输出 ans。

参考代码

#include <iostream>

using namespace std;

int main() {
    // 优化输入输出流
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

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

    int ans = 0;

    // 1. 枚举第一个加数 a = 2^x
    for (int a = 1; a <= r; a *= 2) {
        // 2. 枚举第二个加数 b = 2^y
        // 注意：令 b 从 a 开始，即限定 b >= a (x <= y)，彻底解决顺序重复问题
        for (int b = a; b <= r; b *= 2) {
            int n = a + b;

            // 3. 判断构造出的幂和数是否落在目标区间内
            if (n >= l && n <= r) {
                ans++;
            }
        }
    }

    cout << ans << "\n";

    return 0;
}

复杂度分析

• 时间复杂度：
  • 外层循环次数约等于 $\log_2(r)$（当 $r = 10^4$ 时约为 14 次）。
  • 内层循环次数更少。
  • 总循环次数小于 $\frac{14 \times 15}{2} = 105$ 次，时间复杂度为 $O(\log^2 r)$，在任何评测机上都是 0 毫秒秒杀。
• 空间复杂度：
  • 只用到了几个基础整型变量，空间复杂度为 $O(1)$，极度节省内存。