比赛的时候思路马上出来了..但很多地方没考虑清楚..搞了好久才过....值得注意的...要用long long...再一个..a加到b的二进制数长度可能到达64位..... 此类问题..常规的把握是求0~a-1的..与0
比赛的时候思路马上出来了..但很多地方没考虑清楚..搞了好久才过....值得注意的...要用long long...再一个..a加到b的二进制数长度可能到达64位.....
此类问题..常规的把握是求0~a-1的..与0~b的.... 再用后者减去前者得到答案...
通过观察..问题可以转化为..求a加到b的不进位二进制数..然后再通过至右向左的进位统计二进制的进位次数...再转化..就是求从a~b这些数...每一位有多少个1.....
如从0~3...表示成不进位的二进制数位22...再对22进位成合法的二进制数...22 -> 30 , 30 -> 110...一共进位两次.....
那么如何统计每一位上1的个数呢？通过几次演算..不难发现..从0+1+2+....x...当x为2^p-1时...该二进制数为2^p 2^p 2^p...
如0加到3为22.....0加到7为444...0加到15为8888.....
那么如何求不是2^p-1的数呢？
比如说10....比10小的最大2^p-1数是7...所以可以先得到0加到7的情况...444...还剩下了8,9,10没有加..而8,9,10若是去掉最高位的1..不就是0加到2的情况...
444(0加到7)+300(8,9,10的高位)+011(0加到2)=755...
但注意...结果并不是数出0加到a-1的进位数s1...数出0到b的进位数s2...s2-s1....而是算出0加到a-1和0到b的不进位二进制数..用后者减去前者之后..再进行进位统计...
Program:
//http://icpc.njust.edu.cn/Local/1739#include<iostream>
#include<cstring>
#include<stdio.h>
#include<cmath>
#include<stack>
#include<queue>
#include<algorithm>
#include<string>
#define ll long long
using namespace std;
ll ss[80],s[80];
void getdata(ll x)
{
ll i,p;
memset(s,0,sizeof(s));
p=30;
while (x>0)
{
while (x<(1<<p)-1) p--;
for (i=0;i<p;i++) s[i]+=1<<(p-1);
s[p]+=x+1-(1<<p);
x-=1<<p;
}
return;
}
int main()
{
ll a,b,i,ans;
while (~scanf("%lld%lld",&a,&b))
{
getdata(a-1);
for (i=0;i<=70;i++) ss[i]=s[i];
getdata(b);
for (i=0;i<=70;i++) s[i]-=ss[i];
ans=0;
for (i=0;i<=70;i++)
{
ans+=s[i]/2;
s[i+1]+=s[i]/2;
}
printf("%lld\n",ans);
}
return 0;
}