B4357 [GESP202506 二级] 幂和数

· · 题解

B4357 [GESP202506 二级] 幂和数

题目重述

给定正整数区间 [l, r]，求其中满足条件的整数 n 的数量，条件是 n 可以表示为两个 2 的幂次之和，即 n = 2? + 2?（x, y 为非负整数）。

解题思路

  1. 问题分析：

    • 需要判断区间内每个数是否能表示为两个 2 的幂次之和
    • 2 的幂次包括 1 (2?), 2 (21), 4 (22), 8 (23) 等
    • 由于 n ≤ 10?，最大幂次不超过 213 = 8192

  2. 预处理方法：

    • 枚举所有可能的幂次组合 (x, y)，其中 x ≤ y 以避免重复
    • 计算 2? + 2? 并标记所有 ≤10? 的结果

  3. 优化考虑：

    • 使用位运算快速计算 2 的幂次
    • 使用布尔数组存储结果，空间复杂度 O(10?)

代码实现

#include <iostream>
#include <vector>
using namespace std;

int main() {
    const int MAX = 10000;
    vector<bool> isPowerSum(MAX + 1, false);

    // 预处理所有可能的幂和数
    for (int x = 0; (1 << x) <= MAX; x++) {
        for (int y = x; (1 << y) <= MAX; y++) {
            int sum = (1 << x) + (1 << y);
            if (sum <= MAX) {
                isPowerSum[sum] = true;
            }
        }
    }

    int l, r;
    cin >> l >> r;
    int count = 0;

    // 统计区间内的幂和数
    for (int i = l; i <= r; i++) {
        if (isPowerSum[i]) count++;
    }

    cout << count << endl;
    return 0;
}

复杂度分析