【JZOJ AB组】超级变变变

JZOJ AB组】超级变变变"/>

【JZOJ AB组】超级变变变

Description

经过一系列的游戏之后，你终于迎来了今天的作业，第一个作业是预习一个超级美好的函数f(x),描述如下。

为了研究这个函数的性质，你决定定义一次变化为x=f(x)。

若x就经过若干次变化为k，则你就会觉得这是一个k变变数。

现在既然你已经这么觉得了，那就只好给定A,B,求有多少个A<=x<=B是k变变数了。

Input

输入包含三行。

第一行为一个整数k。

第二行为一个整数A。

第三行为一个整数B。

Output

输出仅一行，表示答案。

Sample Input

Sample Input 1
13
12345
67890123

Sample Input2
1
234567
1234567

Sample Output

Sample Output1
8387584

Sample Output2
1000001

Hint

对于50%的数据，0<=k,A,B<=10^6

对于100%的数据，0<=k,A,B<=10^18 A<=B

思路

设g(x)为0–x k变变数的数量，则答案为g(b)-g(a-1)
那么怎么求g(x)呢？

其实一个数满足是k的变变数，一定满足这个数右移若干位之后等于k。
知道这个答案就很显然了。

注意如果k为偶数要稍微特判一下（详见代码）

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#define ll long long
using namespace std;
ll k,a,b;
ll solve(ll x,ll t)
{if(x<0||x<t) return 0;if(t==0) return x+1;if(x==t) return 1;ll p=t,ans=0,bz=1;while(t<=x){t<<=1; bz<<=1;}t>>=1; bz>>=1;while(t>=p){ans+=min(bz,x-t);t>>=1; bz>>=1;}return ans;
}
int main()
{scanf("%lld%lld%lld",&k,&a,&b);if(k==0){printf("%lld",b-a+1); return 0;}if(k&1) printf("%lld",solve(b,k)-solve(a-1,k));else printf("%lld",solve(b,k)+solve(b,k+1)-solve(a-1,k)-solve(a-1,k+1));
}