Codeforces Round #596 (Div. 2)C. p-binary

7360 ワード

Codeforces Round #596 (Div. 2)C. p-binary
http://codeforces.com/contest/1247/problem/C
标题:n,pを与えて、(2 a 1+p)+(2 a 2+p)+…(2 a m+p)=n(2^{a_1}+p)+(2^{a_2}+p)+…(2^{a_m}+p)=n(2 a 1+p)+…(2 am+p)=n(2 a 2+p)+…(2 am+p)=n
作り方:mを小さいものから大きいものまで列挙すると、mが小さいほど良いし、大きな数字を超えないという問題は、2 a 1+2 a 2+......2 a m=n−m p 2^{a_1}+2^{a_2}+......2^{a_m}=n−mp 2 a 1+2 a 2+......2 am=n−mp、n−m p n−mp n−mp 2進制に変換すると、それぞれ1のビットが2 a i 2^{a_i}2 aiに対応し、複数に対応してもよく、例えば、4は(1~4)個の数字の和、すなわち4,2+2,2+1,1+1,1+1+1に変換できるので、バイナリの中の1の個数<=mとすれば、m>バイナリの中の1の個数を逆算することはできない
ACコード:
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define ll long long
#define pb push_back
#define rep(x,a,b) for (int x=a;x<=b;x++)
#define repp(x,a,b) for (int x=a;x
#define W(x) printf("%d
",x)
#define WW(x) printf("%lld
",x)
#define pi 3.14159265358979323846 #define mem(a,x) memset(a,x,sizeof a) #define lson rt<<1,l,mid #define rson rt<<1|1,mid+1,r using namespace std; const int maxn=2e6+7; const int INF=1e9; const ll INFF=1e18; ll f(ll x){return __builtin_popcount(x);} int main() { ll n,p; cin>>n>>p; for (int i=1;i<=10000;i++) { ll x=n-i*p; if (f(x)<=i&&x>=i) { cout<<i<<endl; return 0; } } cout<<-1<<endl; return 0; }