codeforces 596 div2 p-binary（数位复杂度压缩）

题目大意：

已知：

 同时 

  ，问k最少为多少。

解题思路：

首先，我们看到这里有2的n次方，我们考虑能不能从二进制表示下手，我们通过移位来表示：得到公式

 ，很直接的想法是我们让k从小到大进行枚举。那么我们怎么判断这条等式是否能够满足呢？

我们知道 xi在这里最小为0，所以n-kp最多可以拆减为n-kp个pow(2,0)相加，所以必须k<=(n-kp)，同时k还有一个边界k>=res，其中res为n-kp的二进制表示中1的个数。例如：已知二进制表示为1100的一个数，我们不可能找到少于两项的pow(2,xi)求和，所以我们得到k的一个边界后，我们的k在枚举的时候假如符合这个边界，我们就认为这个k可以输出。那么k枚举到什么地方为止呢？我们可以看到k=31之后就不用再枚举了，因为n<pow(2,31)，所以我们这里当k=31时，n-kp<pow(2,31)，一个数小于pow(2,x)，那么这个数肯定可以用x位来表示，所以走到k=31时，应该是能够表示的了。

废话：

这里我们使用了二进制复杂度压缩的思想，这种思想我们之前在树状数组也见过。这种思想非常重要！

另外这里也告诉我们要会一定的公式变形。

#include <bits/stdc++.h>
using namespace std;
int main(){
  int n,p;cin>>n>>p;
  for(int k=1;k<=31;k++){
    int no=n-k*p;
    if(no<0)continue;
    int tmp=no;
    int res=0;
    while(tmp){
      if(tmp&1)res++;
      tmp>>=1;
    }
    if(k<res)continue;
    if(k>n-k*p)continue;
    cout<<k<<endl;
    return 0;
  }
  cout<<-1<<endl;
  return 0;
}