C. p-binary_牛客博客

原题地址
题意：给一个数n，和数p。询问你是否可以找到n == $2^{x}$ +p时，需要最少的 $2^{x}$ 的数量，如果找不到就输出-1
思路：因为要找的是 $2^{x}$ 的数量，所以可以把思路换成n -xp == $\sum_{i = 1}^{x} 2^{x}$ ,即换成了二进制的思路。
这个思路主要要点在于
1.n -xp >0（最小是 $2^{0}$ ==1）
2.n -xp 的二进制中1的个数要<=x（大于的话，就是还没找到最接近n的x）
3.当n -xp>=x输出，很显然如果<的话n -x*p的数连 $2^{x}$ 中的x都小于肯定是不符合的
代码如下

#include<bits/stdc++.h>
using namespace std;
#define ll long long
/*struct Node { char data; Node *left,*right; }; Node *buildTree(Node *bt) { char x; cin>>x; if(x=='#') bt=NULL;//建立树的时候如果碰到0就代表空的节点 ，根据题意 else { bt=new Node;//分配空间 bt->data=x; bt->left=buildTree(bt->left); bt->right=buildTree(bt->right); } return bt; } void mi(Node *b) { if(b==NULL) return ; mi(b->left); cout<<b->data; mi(b->right); } void change(Node *b) { if(b==NULL) return ; change(b->right); cout<<b->data; change(b->left); } double arr[1000000]= {0}; int brr[1000000]= {0}; ll mod = 1000000; ll f_pow(ll x,ll p) { ll ans=1; while(p) { if(p%2==1) { ans*=x; ans%=mod; } x*=x; x%=mod; p/=2; } return ans; } vector<ll >v; ll button(ll n ) { ll x,flag=0; if(n>10000) { x = round((double)sqrt(n)); } else x = n; while(x/3) { if(x%3==2) { flag= 1; break; } x/=3; } if(x%3==2) { flag=1; } if(flag) return 0; else return 1; } void admit() { v.push_back(1); for(int i=2; i<=100000; i++) { if(button(i)) v.push_back(i); } }*/
int main()
{
    int n,p,ans=1;
    cin >>n>>p;
    while(n-ans*p>0){
        if(__builtin_popcountll(n-ans*p)<=ans){
            if((n-ans*p)>=ans){
                return cout<<ans<<endl,0;
            }
        }
        ans++;
    }
    cout<<-1<<endl;

    return 0;
}