给定整数 m,k，求出正整数 n 使得 n+1,n+2,…,2n 中恰好有 m 个数 在二进制下恰好有 k 个 1。
解:
依题意
定义0~n中在二进制下恰有k个1的数的个数为f(n,k)
所以原式所求为f(2n,k)-f(n,k)
将1~n中所有数扩大一倍变为2,4,6,...2n
发现二进制下的1的个数不变
所以f(2n,k)-f(n,k)=0~2n中符合条件的奇数个数
因为奇数的末尾一定为1
所以f(2n,k)-f(n,k)=f(n-1,k-1)
显然这是一个随n单调不减的函数
就可以二分啦