CF1225C p-binary

CF1225C P-binary

更好的阅读体验请戳这里

题意：给定 (n,p,且n leqslant 10^9,pin [-1000,1000])
请你构造出(m)个非负整数(a_i)(可以重复)
满足(sum_{i=1}^m 2^{a_i}+p = n)，求(m)的最小值

用(cnt(x))表示(x)的二进制位上为(1)的个数,
发现对(cnt(x)leqslant y leqslant x，)
都能构造出 (x = sum_{i=1}^y 2^{a_i},a_igeqslant 0)

那么 从小到大枚举(i)，看 (cnt(n-i*p) leqslant i leqslant n-k*i) 是否成立即可

int m,n,p;
il int cnt(int x) 
{ 
    int ret=0; 
    while(x) x-=x&-x,++ret; return ret; 
}
int main()
{
    n=read(); p=read();
    for(int i=1;i<=n-i*p;++i)
        if(i>=cnt(n-i*p))
            printf("%d
",i),exit(0); 
    puts("-1");
    return 0;
}