题解：P14074 [GESP202509 五级] 有趣的数字和

第一种做法

直接拆分，但每次除 2 不现实，也就是while(x>>=1)的做法会超时，那么，考虑

lowbit

。

lowbit(x)

即返回

x

的离末尾最近的 1 所代表的值。得出代码：

CPP

#include<bits/stdc++.h>
using namespace std;
int lowbit(int x){return x&(-x)}
int chai(int x)
{
    int num=0;
    while(x-=lowbit(x))
    {
        num++;
    }
    return num;
}
int main(  )
{
    int l,r;
    cin>>l>>r;
    long long sum=0;
    for(int i=l;i<=r;i++) if(chai(i)%2==0) sum+=i;
    cout<<sum;
    return 0;
}

但是任然不对。

第二种做法

这里介绍一个可以在

O(1)

时间复杂度直接返回一个数二进制一的个数的函数：

\_\_builtin\_popcount(x)

那么，很容易得出代码：

CPP

#include<bits/stdc++.h>
using namespace std;
int main(  )
{
    int l,r;
    cin>>l>>r;
    long long sum=0;
    for(int i=l;i<=r;i++) if(__builtin_popcount(i)%2==1) sum+=i;
    cout<<sum;
    return 0;
}

感谢观看！

题解：P14074 [GESP202509 五级] 有趣的数字和

文章操作

第一种做法

第二种做法

相关推荐

评论

题解：P14074 [GESP202509 五级] 有趣的数字和