jzoj3084

时间:2022-09-26 12:25:02

發現題目函數本質是:

1.將某一數x的末尾1去掉

2.不斷將這個數/2,直到遇到新的1

我們發現一個數z可以用y步到達數x,記x二進制長度為c,分2種情況討論:

1.x是奇數,則z的前c個二進制數必須與x相等

2.x是偶數,則z的第c位可以任意選,所以只要c-1位相等即可

我們弄出答案區間再統計答案即可

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll k,a,b;
ll ct(ll x){
	ll c=1,kk=k,rr=0;
	while(1){
		ll l=kk,r=kk+c-1;
		if(r<=x)rr+=r-l+1;
		if(x<l)break;
		if(l<=x&&x<=r){
			rr+=x-l+1;
			break;
		}
		kk<<=1;
		c<<=1;
	}
	if(k%2==0)rr*=2;
	return rr;
}
int main(){
	scanf("%lld%lld%lld",&k,&a,&b);
	if(!k){
		printf("%lld",b-a+1);
		return 0;
	}
	printf("%lld",ct(b)-ct(a-1));
}

相关文章