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コード:
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;
}