博客

p-binary

Vasya will fancy any number as long as it is an integer power of two. Petya, on the other hand, is very conservative and only likes a single integer p (which may be positive, negative, or zero). To combine their tastes, they invented p-binary numbers of the form 2x+p, where x is a non-negative integer.

For example, some −9-binary (“minus nine” binary) numbers are: −8 (minus eight), 7 and 1015 (−8=20−9, 7=24−9, 1015=210−9).

The boys now use p-binary numbers to represent everything. They now face a problem: given a positive integer n, what’s the smallest number of p-binary numbers (not necessarily distinct) they need to represent n as their sum? It may be possible that representation is impossible altogether. Help them solve this problem.

For example, if p=0 we can represent 7 as 20+21+22.

And if p=−9 we can represent 7 as one number (24−9).

Note that negative p-binary numbers are allowed to be in the sum (see the Notes section for an example).

Input

The only line contains two integers n and p (1≤n≤109, −1000≤p≤1000).

Output

If it is impossible to represent n as the sum of any number of p-binary numbers, print a single integer −1. Otherwise, print the smallest possible number of summands.

思维 + 一点数学；

把一个数字ans转化为二进制可以知道，有多少个1，就代表有多少个2^x, 并且一个2^x还可以进行拆分；

最多可以拆成ans个2^0,就是ans个1；

所以直接暴力枚举个数i，算ans（ans=n-i*p）是否符合条件就行；

代码：

#include<bits/stdc++.h>
#define LL long long
#define pa pair<int,int>
#define lson k<<1
#define rson k<<1|1
//ios::sync_with_stdio(false);
using namespace std;
const int N=200100;
const int M=200100;
const LL mod=1e9+7;
int ans;
bool judge(int p){
	int mmax=ans;
	int mmin=0;
	int s;
	while(ans){
		s=ans%2;
		ans/=2;
		if(s==1) mmin++;
	}
	if(p>=mmin&&p<=mmax) return true;
	return false;
}
int main(){
	ios::sync_with_stdio(false);
	int n,p;
	cin>>n>>p;
	for(int i=1;i<=100000;i++){
		ans=n-i*p;
		if(judge(i)){
			cout<<i<<endl;
			return 0;
		}
	}
	cout<<-1<<endl;
	return 0;
}