「CF1225C」p-binary

题意：给两个数 $n$ 和 $p$，定义 p-binary 数为 $2$ 的幂加上 $p$ 的数，例如：$2 ^{0} +p,2 ^{1} +p,2 ^{2} +p$，将 $n$ 拆分成若干个 p-binary 数，求出拆分得到的最少 p-binary 数，如果无解输出 $-1$。

假设 $n$ 被拆成 $m$ 个 p-binary 数，那么有如下式子：

$$n-mp={ 2^ {x _1} }+{ 2^ {x _2} }+···+{ 2^ {x _m} }$$

很明显，我们可以从小到大枚举 $n-mp$，对于每一个枚举的数用二进制表示，把其中 $1$ 的个数记为 $q$。

如果 $q\leq m$ ，并且 $n-mp\geq m$，那么此时 $m$ 就是答案。

证明：如果 $q=m$ ，那么正好可以拆分成 $m$ 个数，显然满足，如果 $q<m$ ，那么我们可以将较大的 $2$ 的幂分成两个较小的 $2$ 的幂，例如 $2^ {x}={2^ {x-1} }+{2^ {x-1} }$，可以凑成 $m$ 个数，其次由 $n-mp={2^ {x _1 } }+{2^ {x _2 } }···+{2^ {x _m } }$ 可知，右边的式子肯定大于等于 $m$，所以左边的式子也要满足大于等于 $m$。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
int n,p,ans=1;
int clac(int x)
{
	int sum=0;
	while(x)
	{
		if(x&1)
			sum++;
		x>>=1;
	}
	return sum;
}
int main()
{
	scanf("%d%d",&n,&p);
	while(n-ans*p>=ans)
	{
		int x=n-ans*p;
		int num=clac(x);
		if(num<=ans)
		{
			printf("%d",ans);
			return 0;
		}
		ans++;
	}
	printf("-1");
	return 0;
}