2013 南京邀请赛 C count the carries

时间:2023-03-09 09:36:57
2013 南京邀请赛 C count the carries
 /**
大意: 给定区间(a,b), 将其转化为二进制 计算从a+(a+1)+(a+2)。。。。+(a+b-1),一共有多少次进位
思路: 将(a,b)区间内的数,转化为二进制后,看其每一位一共有多少个1
可知最低位循环为2,第二位循环为4
---〉 所以每一位的1的个数为 : 假设为第三位 (n-n%8)/8*8/2===>(n-n%8)/2
------> 如果n%8 大于8/2 那么应该再加上 n%8-8/2
**/
#include <iostream>
#include <cstring>
using namespace std; void cal(int num[],int n){
long long mod =;
n++;
for(int i=;i<;i++){
if(mod>n)
break;
mod = mod*;
num[i] += (n-n%mod)/;
if(n%mod > mod/) num[i] += n%mod-mod/;
}
}
int main()
{
long long a,b;
int anum[],bnum[];
while(cin>>a>>b){
memset(anum,,sizeof(anum));
memset(bnum,,sizeof(bnum));
cal(anum,a-);
cal(bnum,b);
for(int i=;i<;i++)
bnum[i]-=anum[i];
long long ans = ;
for(int i=;i<;i++){
ans += bnum[i]/;
bnum[i+] += bnum[i]/;
}
cout<<ans<<endl;
}
return ;
}