题解 P2431 【正妹吃月饼】
与原题题解相对地，我们考虑倒序减。
用一个k位全为1的整数val表示初始的月饼集合，根据进制知识易知，这个整数的值就是这些月饼的重量和。
这个整数应当是第一个恰好不小于B的二进制全1数字。
此后，我们从这个数的最高位(恰好是2^(k-1))开始向低位考虑，算法流程如下：
- 减去这个数（2^(k-1)）后，月饼的重量和小于A,则不考虑这一位；
- 否则，使这一位变成0，也即减去2^(k-1)；
- 如果月饼集合恰好不大于B，跳出。
下面说明算法的正确性：
对于初始的月饼集合取值来说：
-
最优解一定能表示为一个若干位为1的二进制数。初始值取全1二进制数不会导致更差的解，因为在集合的角度，最优解是val的一个子集；
-
同上，初始值如果取小于B的全1二进制数，可能不包含最优解集合，而val不会带来错误的解，故初始值不应当小于B；
-
如果我们取了大于题设val的全1二进制数（设为S）作初始值，易知，S的最高位表示(val+1)*2，删去后仍然大于B，在算法流程中，我们会将其删去，它一定不会为解带来贡献，故不选大于val的值作初始值。
综上，我们通过全1二进制数作初始值的 正确性、决策（答案）包容性、不冗余性说明了恰好不小于B的全1二进制数作初始值的正确性。
对于算法流程本身来说
-
如果当前只需按照算法流程再减去1位（a=2^k）即求得最优解，设当前的值为num,应当有num-a∈[A,B]。
-
不妨设num-a'∈[A,B]。可以发现，a'!=a时，不存在花费不超过1的转移方法，故a取2^k时是“临界”状态的最优解。
-
对于上述可以导致最优解的num，设从num+b转移而来（num=num+b-b）。
-
显然，num+b->num的转移以1为代价时，解最优，所以，b是2的幂次。
-
根据归纳法，一个能导致最优解的状态，一定是从初态val不断减去2的一个幂次转移来的。
-
初态val(全1二进制数)包含正解的正确性我们已经证明。
论毕
代码
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ULL;
ULL A,B;
int main(){
cin>>A>>B;
ULL val=1;
while(val<B) val=(val<<1)+1;
ULL Bit=(val+1)>>1;
for(;val>B;Bit>>=1){
val=val-Bit<A?val:val-Bit;
}
int cnt=0;
for(;val;val>>=1) if(val&1) ++cnt;
cout<<cnt;
return 0;
}