专栏文章

B4357 [GESP202506 二级] 幂和数

FFishlinsihan
B4357题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miovkm6i
此快照首次捕获于
2025/12/03 01:51
3 个月前
此快照最后确认于
2025/12/03 01:51
3 个月前
查看原文

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?)

代码实现

CPP
#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;
}

复杂度分析

  • 时间复杂度：O(14×14 + r-l) ≈ O(200)（预处理+查询）
  • 空间复杂度：O(10?)（标记数组）
    这是我的第一篇题解，希望管理员大大通过QwQ。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...