C. p-binary(codeforces)

  • 时间:
  • 来源:互联网
  • 文章标签:

C. p-binary

问题:重新定义二进制,二进制加一个常数 p 作为一个新的权值,看是否可以组成给定的数n。
例如:p = -9,n = 7(7 = 2^4 - 9),不多说,解释代码。

#include<iostream>
#include<cstdio>
using namespace std;

//找到x二进制表示有多少个1
int come(int x) {
	if(x <= 0) return 0;
	int ans = 0;
	while(x) {
		if(x&1) ans++;
		x >>= 1;
	}
	return ans;
}
int main() {
	int n, p, temp, flag = 0;
	scanf("%d%d", &n, &p);
	
	for(int i=1; i<=1000000; i++) {
	//1.因为二进制的高位可以拆成多个低位come(n-p*i) <= i。
	//2.因为n-p*i最多分成n-p*i个2^0,所以i <= n-p*i。
		if(come(n-p*i) <= i && i<=n-p*i) {
			printf("%d", i);
			flag = 1;
			break;
		}
	}
	if(!flag) printf("-1");
	return 0;
}

本文链接http://www.taodudu.cc/news/show-83036.html