B题题解
思路:
自定义一个函数 sum(n) 求得 [1,n]范围内满足要求的数 的个数
sum(r)-sum(l-1) 就是最后的结果
问题在于sum(n) 函数的构造:
通过手推:我们会发现 因此我们可以自定义出sum(n)函数,快速求出[1,n]范围内满足要求的数 的个数
ps:注意使用long long
代码如下:
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
// 返回最低位的1
ll lowbit(ll x){
return x & -x;
}
// 判断是否 n在二进制下有奇数个1
bool check(ll n){
int res=0;
while(n) res++,n-=lowbit(n);
if(res&1) return true;
return false;
}
// 求1到n 满足要求的数 个数
ll sum(ll n){
ll ans=0;
while(n){
if((n+1)%4==0) return ans+(n+1)/2;
if(check(n)) ans++;
n--;
}
return ans;
}
int main(){
int T;
cin>>T;
while(T--){
ll l,r;
cin>>l>>r;
cout<<sum(r)-sum(l-1)<<endl;
}
return 0;
}