2013南京招待試合C題/njustOJ 1739-Count The Carries

試合の時、考えがすぐに出てきた.しかし、多くの場所はよく考えていません.久しぶりに...注意すべき...long longを使うには...もう一つ...a bに加算されたバイナリ数の長さは64ビットに達する可能性があります.....
このような問題..通常の把握は0~a-1を求める..0~bの....後者で前者を減算して答えを得る...
観察により..問題は...aプラスbの不進位のバイナリ数を求めます..次に右から左へのキャリーでバイナリのキャリー回数を統計します...再変換..a~bの数から...一人一人に何個あるか1.....
0~3から...不進位を表すバイナリビット22...さらに22進位を合法的なバイナリ数に...22 -> 30 , 30 -> 110...全部で2回...
では、各上位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に加算した場合ではありません...
したがって、0を10に加算する非進位バイナリ数は444(0を7に加算)+300(8,9,10の高位)+011(0を2に加算)=755...
でも注意...結果は0をa-1に加算した進位数s 1ではない...0からbの進位数s 2を数えて...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
",ans);
      }
      return 0;
}