1 #include<stdio.h>
2 #include<string.h>
3 #define max(x, y) ((x)>(y)?(x):(y))
4 int C[32][32]; //C[n][k]表示小于2^n的所有的數(shù)含至少k個0的個數(shù)
5
6 void init(){
7 int i, j;
8
9 for(i = 0; i < 32; i++)
10 C[i][0] = C[i][i] = 1;
11
12 for(i = 1; i < 32; i++)
13 for(j = 1; j < i; j++)
14 C[i][j] = C[i-1][j-1] +C[i-1][j];
15
16 for(i = 0; i < 32; i++)
17 for(j = i-1; j >= 0; j--)
18 C[i][j] += C[i][j+1];
19 }
20
21 int gao(int u){
22 int value[32], n = 0;
23 while(u){
24 value[n++] = u%2;
25 u/=2;
26 }
27
28 int i, j, ans = 0;
29 for(i = 1; i < n-1; i++)
30 ans += C[i][ i/2 + 1 ];
31
32 int cnt = 1, least;
33 least = n % 2==0 ? n/2 : n/2+1;
34 for(i = n-2; i >= 0; i--)
35 if(value[i]){
36 j = max( 0, least-(n-i-cnt) );
37 if(j > i)return ans;
38 ans += C[i][j];
39 cnt++;
40 }
41
42 return ans;
43 }
44
45 int main(){
46 int a, b;
47 init();
48
49 while(scanf("%d %d", &a, &b)!=EOF)
50 printf("%d\n",gao(b+1) - gao(a) );
51 }
這類題目要寫的快
posted on 2009-09-01 10:57
wangzhihao 閱讀(262)
評論(0) 編輯 收藏 引用 所屬分類:
math