G2020 [GESP202506 二级] 幂和数 题解

知识点：枚举、幂、去重。

解题思路

枚举不超过r的全部2的幂，两两相加，只把落在[l,r]内的和加入集合。

为什么正确

任何幂和数都对应一对已枚举幂；集合将不同表示得到的同一数字合并。

易错点

允许两个幂相同；统计不同数字，不统计表示方法数。

复杂度

时间O(log²r·log log r)，空间O(log²r)上界。

参考代码（C++17）

#include<bits/stdc++.h>

using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int l,r;
    cin>>l>>r;
    set<int>s;
    for(int a=1;a<=r;a*=2)for(int b=1;b<=r;b*=2)if(a+b>=l&&a+b<=r)s.insert(a+b);
    cout<<s.size();
}

说明

本题解为配套教学整理，非官方题解。复杂度按本页参考实现计算，题库使用8个自行生成的测试点。