UVALive 6918 And Or 数学二进制+枚举

1<=L<=R<=1e18

求L & （L+1） &  （L+2）  & （L+3） ……  &  R

和L | （L+1） |  （L+2） | （L+3） …… |  R

这个题呢，让我自己做，肯定就是弃疗了，学习了一份二进制枚举的代码其实还是蛮简单的

拿第x位的二进制位置距离，要想在x上，&运算有值，那么就需要【L，R】的每一位二进制x都有值

就是说，【1，R】上二进制x位置上的个数 - 【1，L-1】 的x位置上的个数 = R-L+1

同理，|  运算，需要的是至少有一个，【1，R】上二进制x位置上的个数 - 【1，L-1】 的x位置上的个数 >=1

所以，枚举每一个二进制位，然后暴力统计就好了

#include<bits/stdc++.h>
using namespace std;

#define LL long long
LL cnt[70],ans1,ans2;

void calc(LL x,int f){
	for(int i=63;i>=0;i--)
		if ((x>>i)&1){
			cnt[i]+=f*(x%(1LL<<i)+1);
			for(int j=i-1;j>=0;j--)
				cnt[j]+=f*(1LL<<(i-1));
		}
}

void solve(LL a,LL b){
	memset(cnt,0,sizeof(cnt));
	calc(b,1);
	if (a>1) calc(a-1,-1);
	ans1=ans2=0;
	int t1,t2;
	for(int i=63;i>=0;i--){
		t1=t2=0;
		ans1<<=1;
		ans2<<=1;
		if (cnt[i]) ans1++;
		if (cnt[i]==b-a+1) ans2++;
	}
}

int main(){
	//freopen("input.txt","r",stdin);
	LL a,b;
	int T;
	scanf("%d",&T);
	for(int Case=1;Case<=T;Case++){
		scanf("%lld%lld",&a,&b);
		solve(a,b);
		printf("Case %d: %lld %lld\n",Case,ans1,ans2);
	}
	return 0;
}