Codeforces #596 Div1 A. p-binary

えらく順調でレートを稼いだ回。
http://codeforces.com/contest/1246/problem/A

問題

整数pが与えられる。p-binaryとは、非負整数xを用いて(2^x+p)の形で表現できる整数を示す。
整数Nが与えられる。Nをp-binaryの和で表すとき、最長何個の数が必要か。

解法

解kを小さい順に総当たりしよう。
解がkの場合、k個の(2^x)の形の数の和がN-kPになればよい。
これはN-kpがkより大きく、かつN-kpの立っているbitがk個以下ならよい。

ll N,P;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>P;
	
	for(i=1;i<=100000;i++) {
		ll t=N-P*i;
		if(i<=t && __builtin_popcount(t)<=i) return _P("%d\n",i);
	}
	cout<<-1<<endl;
}

まとめ

さっきの問題に比べると書くのがラクだ…。