题意:若一个数的二进制形式中0的个数不少于1的个数,那么就称这个数为round number,现在输入两个整数start,finish求在这两个数之间有多少个round number。
#include<cstdio> #include<algorithm> #define lint __int64 using namespace std; lint C ( int m, int n ) { if ( m < n ) return 0; lint ret = 1; for ( int i = 1, j = m; i <= n; i++, j-- ) ret = ret * j / i; return ret; } lint cal ( int x ) { lint count = 0; int i, j, len = 0; if ( x == 0 || x == 1 ) return 0; while ( ((lint)1<<len) <= x ) len++; //先求出二进制的长度 for ( i = 2; i < len; i++ ) //长度小于len的可以用排列组合公式先求出来 { j = i / 2; if ( i & 1 ) j++; for ( ; j < i; j++ ) count += C(i-1,j); } //对于长度等于len的,二进制中的所以1有两种情况, //第一种是保持不变,第二种是将0该成1,然后再统计. //0不作处理,因为如0变成1,那么同时一定有一个更高位的1变成了0. //这样才能使数不超出[start,finish]的范围. int zero = 0, limit = len / 2; //zero统计0的个数 if ( len & 1 ) limit++; //;limit表示至少需要的0的个数 for ( i = len - 2; i >= 0; i-- ) { if ( ((1<<i) & x) ) { for ( j = max(limit-zero-1,0); j <= i; j++ ) count += C(i,j); } else zero++; } if ( zero >= limit ) count++; return count; } int main() { int start, finish; scanf("%d%d",&start,&finish); printf("%I64d\n",cal(finish)-cal(start-1)); return 0; }