样例1：

3 1

　　　样例2：

13 2

　　　样例3：

1000000 5

　　　样例1：

1

　　　样例2：

3

　　　样例3：

15808

依题意可得，每2^x个瓶子可以合成一个瓶子。

以样例13 5来说，

13=8+4+1.

也就是说13个瓶子可以合并成3个瓶子，但此时不满足“小于k个”条件，所以需要购买空瓶子。

买1个，14=8+4+2，没有什么卵用。

买2个，15=8+4+2+1，好像更糟。

买3个，16=16,搞定。

根据上述过程可以得出初步思路：算出n可以分成几个2^x相加，也就是可以合成几个瓶子。如果结果>k那么买一个空瓶重复上述过程。

但是这里需要一个小技巧，如果你分解数的时候暴力枚举，时间肯定爆炸。

由于是2^x，所以我们很容易地想到2进制。所有2的倍数的二进制都是100000……（好多好多的0）

观察样例13的二进制： 1101.相当于二进制1000+100+1即十进制8+4+1.

得出结论，要统计有多少个因子（好像不叫因子，反正就那意思），只需要数数当前瓶子数的2进制下有多少个1即可。

那么我们需要一位位比较。如果把整个数转成二进制时间不说了。

如何快速的获得此数二进制数下的某一位呢？

我们只需要构造一个数，这个的二进制数是0000000000000000000100000000（1<<N）

然后再把当前数与该数按位与，就可以得出当前数二进制下某一位。

交上去发现悲伤的超时了。

所以我们需要优化。其实每一次加1的目的就是为了让数中的0变少。就是需要进位。

此时我们把瓶子数量的二进制取反再加一，进位就变得容易多了

稍有常识的人都会知道，n的二进制取反再加一就是-n。

 1 #include<bits/stdc++.h>

 2 using namespace std;

 3 typedef long long ll;

 4 int main()

 5 {

 6     ll n,k;

 7     cin>>n>>k;

 8     ll ans=0;

 9     do

10     {

11         ll zs=0;

12         for(ll i=0;i<63;i++)

13         if((n&((ll)1<<i))>0) zs++;

14         if(zs<=k) break;

15         ans+=n&(-n);

16         n+=n&(-n);

17     }while(1==1);

18     cout<<ans<<endl;

19     return 0;

20 }