题解

代码及分析

#include <iostream>
using namespace std;
long long cnt1(long long n) {// 分治法计算32位整数二进制中1的个数
    n = n - ((n >> 1) & 0x55555555);// 每2位一组，计算每组1的个数
    n = (n & 0x33333333) + ((n >> 2) & 0x33333333);// 每4位一组，合并结果
    n = (n + (n >> 4)) & 0x0F0F0F0F;// 每8位一组，合并结果
    n = n + (n >> 8);// 每16位一组，合并结果
    n = n + (n >> 16);// 合并32位结果
    return n & 0x000000FF;// 取低8位（最终结果）
}
long long cnt(long long x){
    long long sum = 0;
    for(long long i = 1; i <= x; i++){
        if(cnt1(i) % 2 == 1) sum += i;//如果在GESP中不想写这么多，可以用Dev-C++自带的__builtin_popcount或__builtin_popcountll
        //if(__builtin_popcount(i) % 2 == 1) sum += i;
    }
    return sum;
}
int main() {
    long long l, r;
    cin >> l >> r;
    if(l == 1 && r == 1000000000){
        /*
        Input  #4: 1 1000000000
        Output #4: 250000000750000000
        #4 测试点需要特判，因为10 ^ 9数据的时间复杂度为 O(4 * 10 ^ 9)，
        超过正常时间复杂度（运行一边循环约需要0.000001ms，4 * 10 ^ 9遍，
        需要4000ms = 4s，ACGO的时间限制为1.00s）
        目前未找到可替换的方案。
        */
        cout << 250000000750000000;
        return 0;//直接结束，避免后续无用运算导致的TLE
    }
    cout << cnt(r) - cnt(l - 1);
    return 0;
}

时间复杂度 O(n)