题解

题目解析

• 输入输出：输入两个正整数 $l, r$（表示区间左右端点）；输出一个整数，表示区间 $[l, r]$ 内可以表示为两个 $2$ 的次幂之和（$n = 2^x + 2^y$，其中 $x, y$ 为非负整数）的整数 $n$ 的个数。
• 数据范围：$1 \leq l \leq r \leq 10^4$，区间长度不超过 $10^4$，数值范围较小。
• 复杂度要求：时间复杂度 $O((r-l+1) \cdot \log_2 r)$，由于 $r \leq 10^4$，双重循环枚举 $2$ 的幂次（最多约 $14$ 层）完全满足 $1$s 时限；空间复杂度 $O(1)$。
• 算法知识点：枚举、暴力验证、位运算思想（虽然实现未使用位运算，但本质是判断二进制表示中 $1$ 的个数是否不超过 $2$ 个）

思路解析

1. 幂和数的判定：一个数 $n$ 是幂和数，当且仅当存在非负整数 $x, y$ 使得 $2^x + 2^y = n$。注意 $x$ 可以等于 $y$（此时 $n = 2 \cdot 2^x = 2^{x+1}$，即 $n$ 本身也是 $2$ 的幂）。
2. 枚举验证：对于每个待验证的数 $x$，枚举所有可能的 $2^i$（$i$ 从 $0$ 开始，直到 $2^i \leq x$），再枚举所有可能的 $2^j$，检查是否存在 $2^i + 2^j = x$。由于 $2^{14} = 16384 > 10^4$，内层循环最多执行约 $14 \times 14 = 196$ 次，效率足够。
3. 区间统计：遍历区间 $[l, r]$ 中的每个整数，调用判定函数，累加符合条件的数的个数。

完整代码

#include <bits/stdc++.h>

using namespace std;

// 判定函数：检查x是否可以表示为两个2的次幂之和
bool check(int x) {
    // 枚举第一个幂次2^i，上限为x（实际当2^i > x时可停止）
    for (int i = 0; pow(2, i) <= x; i++) {
        // 枚举第二个幂次2^j
        for (int j = 0; pow(2, j) <= x; j++) {
            // 关键：若两幂次之和等于x，则x是幂和数
            // 注意：此实现允许i=j（即x为2的幂时也算作幂和数，如2=2^0+2^0不成立，但2=2^1+2^0=2+1不... 
            // 实际上2 = 2^1 + 2^0 = 2+1=3≠2，但2 = 2^0 + 2^0 = 1+1=2，所以2是幂和数）
            if (pow(2, i) + pow(2, j) == x) return true;
        }
    }
    return false;
}

int main() {
    int l, r;
    cin >> l >> r;
    int ans = 0;
    
    // 遍历区间[l, r]内的每个数
    for (int i = l; i <= r; i++) {
        if (check(i)) ans++;  // 若是幂和数则统计
    }
    cout << ans << endl;
    return 0;
}