幂和数 题解

题目分析

我们定义这样一个数：如果正整数 ( n ) 可以表示为两个 ( 2 ) 的次幂之和，即存在非负整数 ( x, y ) 使得
[ n = 2^x + 2^y ]
那么 ( n ) 就被称为幂和数。注意，这里的 ( x ) 和 ( y ) 可以相等（例如 ( 2^0 + 2^0 = 2 )）。

现给定一个区间 ([l, r])，需要求出该区间内有多少个幂和数。

解题思路

思路一：直接枚举 ( x, y ) 生成幂和数

由于 ( x, y ) 是非负整数，极限情况下 ( 2^x + 2^y \le r )。
不妨设 ( x \le y )，令 ( a = 2^x )， ( b = 2^y )，则有 ( a \le b ) 且 ( n = a + b )。

• 外层循环枚举 ( a = 1, 2, 4, 8, \dots ) 直到 ( a > r )；
• 内层循环从 ( b = a ) 开始，每次乘以 2，直到 ( a + b > r )；
• 每次得到的 ( n = a + b )，只要满足 ( l \le n \le r )，计数器就加一。

这种方法能够不重不漏地生成所有不超过 ( r ) 的幂和数，并且仅需在生成时判断是否落在 ([l, r]) 内。

优点：时间复杂度只与 (\log r) 有关，效率极高，即使在 ( r ) 很大时也能快速运行。
缺点：需要手动推导循环边界，稍微需要对二进制有一定理解。

思路二：枚举区间内每一个数

另一种朴素想法是：遍历 ( n ) 从 ( l ) 到 ( r )，对每一个 ( n ) 判断是否存在非负整数 ( x, y ) 满足 ( n = 2^x + 2^y )。

• 外层循环遍历 ( n )；
• 对内层，枚举 ( x )，并检查 ( n - 2^x ) 是否是 ( 2 ) 的次幂。

这种方式实现简单直观，但复杂度依赖于区间长度 ((r - l + 1))。当区间较大（例如 ( l=1, r=10^9 )）时，运行时间会非常长。因此这种思路只适用于 ( r - l ) 较小的情况。

算法说明与代码解释

这里我们推荐并详细解释第一种思路的代码实现。

C++ 实现

参考代码：

cpp
复制
1#include <iostream>
2using namespace std;
3int main()
4{
5    int l, r, a, b, n, cnt = 0;
6    cin >> l >> r;
7    a = 1;
8    while (a <= r)
9    {
10        b = a;
11        while (b <= r)
12        {
13            n = a + b;
14            if (n >= l && n <= r) cnt++;
15            b *= 2;
16        }
17        a *= 2;
18    }
19    cout << cnt << endl;
20    return 0;
21}

代码解释：

1. a = 1 对应 ( 2^0 )，每次 a *= 2 对应移到下一个 2 的次幂。
2. 内层循环 b = a，表示从 ( y = x ) 开始（允许 ( x = y )）。
3. n = a + b 计算出当前的幂和数。
4. 若 n >= l && n <= r，则说明该幂和数在目标区间内，计数器加一。
5. b *= 2 将 ( b ) 变为下一个 2 的次幂，直到 a + b > r（因为 b 单增，a+b 也会超过 r）。
6. 外层循环继续，直到 a > r（此时即使最小的 ( a+b ) 也大于 ( r )，不可能再产生新区间内的数）。

Python 实现

我们可以将上方的思想直接用 Python 表达：

python
复制
1l, r = map(int, input().split())
2cnt = 0
3
4a = 1
5while a <= r:
6    b = a
7    while b <= r:
8        n = a + b
9        if l <= n <= r:
10            cnt += 1
11        b *= 2
12    a *= 2
13
14print(cnt)

相较于题目附带的 Python 参考代码（逐个数遍历判断），这个版本直接生成幂和数，避免了巨大的循环开销，能轻松通过大数据范围。

时间复杂度分析

• 对于思路一：
  外层循环 ( a ) 取遍 ( 1, 2, 4, \dots, 2^k )，其中 ( k = \lfloor \log_2 r \rfloor )，共约 (\log r) 次。
  内层循环从 ( b = a ) 开始，一直增加到不超过 ( r )，每次迭代次数也不超过 (\log r)。
  总体复杂度为 ( O(\log^2 r) )。
  当 ( r \le 2^{30} \approx 10^9 ) 时，循环次数不超过约 ( 30 \times 30 = 900 ) 次，可以瞬间完成。

• 对于思路二（逐个数判断）：
  需要遍历区间内每个数，对每个数进行 ( O(\log n) ) 的检查，总复杂度为 ( O((r - l) \log r) )，在 ( r - l ) 很大时会超时。

因此强烈推荐使用思路一完成本题。

小结

本题的核心在于利用 2 的次幂的特性，直接生成所有幂和数并计数，而不是对区间内每个数进行检验。这种方法效率极高，且代码简洁易懂。理解本方法后，类似“由有限个幂次组合而成的数”的题目都可以用类似的枚举技巧解决。