题解 | #追求女神#

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