1.cf思维训练篇（11）.div2(萌新向）

cf思维训练篇（11）.div2(萌新向）

       问题 - C - Codeforces

       Jellyfish 拥有公式个青苹果。模块每个青苹果重公式。源码游戏源码水母计划把这些青苹果平均分配给公式个人。模块

       为此，源码游戏源码Jellyfish 利用一把魔法刀，模块他每次可以选择一个青苹果，源码游戏源码保龄 源码将其切成两半，模块每块的源码游戏源码重量为原重量的一半。

       现在，模块他想知道最少需要多少次操作才能使得每个人得到的源码游戏源码青苹果重量相等。

       输入：

       每组测试包含多个测试用例。模块

       首行包含测试用例的源码游戏源码数量公式（公式）。

       每组测试的模块第一行仅包含两个整数公式和公式（公式）——即初始的青苹果数量和人数。

       输出：

       对于每组测试，源码游戏源码输出一个整数——将所有青苹果平均分配给公式人所需的模块柚子培训教育 源码最少操作数。

       如果无法通过有限的操作次数实现，则输出公式。

       分析：

       首先，一个重要的转化思想是：

       如果苹果的数量多于人数，不妨逐一将苹果分配给每个人，直到苹果数量少于人数——即无法通过单一苹果的分配实现平均分配。

       剩余的苹果数量即为n%m；

       接下来，我们需要判断能否通过切割实现平均分配。注意，n表示n=n%m赋值后。

       注意到，由于此时的苹果数量小于人数，因此每个苹果都需要切割；

       深入思考后不难发现：当m是2的整数次幂时，一定可以平均分配。微视小程序源码

       下面是简单的归纳证明：

       (1) 首先证明：当m=1时，总能进行平均分配

       显然，若最初有m个苹果，我们可以将每个苹果切成两半，得到2m个苹果，每个人分到m个苹果，即实现平均分配。

       (2) 归纳：设m=k时，可以进行平均分配，那么只需证明m=2k时也能进行平均分配即可。

       同样，只需在原有m=k的基础上，将每块苹果再切一刀即可平均分配；

       因此，当m是题材王指标源码2的整数次幂时，一定可以平均分配，得证。

       当m不是2的整数次幂时，此时尝试公式，其中gcd表示最大公约数，如n=3，m=，此时可以将一个苹果和四个人分成一组，由于4是2的整数次幂，因此每一组都可以进行均分；

       其他情况难以均分，这部分不再详细阐述，大家可以尝试反证。

       那么，现在我们的源码资本 陈青花结论升级为：当m是2的整数次幂时，一定可以平均分配。

       现在的问题转换为：判断m是否是2的整数次幂。

       这里简单介绍__builtin_popcount()方法：

       该函数的作用是返回二进制数字中“1”的个数。利用二进制原理，我们容易知道，当二进制数字中仅有一个1时，它表示的是2的幂次。

       因此，可以通过判断m是否为1来判断m是否是2的幂次。

       最后，我们只剩下最后一个问题：最少切割数。

       容易知道，为了使切割次数最少，应遵循“尽量分配”的原则，即每当切割出来的相同大小的苹果块能够实现每人一个时，就按每人一个分配一次，剩余部分继续切块。

       具体方法如下：

       (1) 先将所有的苹果一分为二，如果够的话，分配一次；

       (2) 若不够，每个苹果块再切一次...直到足够为止；

       (3) 足够时，按每人一块分配一次；

       重复此操作，直到全部分配完成，由于没有多余的切割，我们认为这种方法是最优的。

       接下来，我们将苹果和人进行分组，并对一组进行讨论：

       令m=a，n=b，a和b即表示一组内的苹果数量和人数。这样，我们只需求出每组的最少切割数，然后将结果乘以a即可得到总最小切割数。

       我们知道平均每人得到的苹果数量为a/b，由于切开的苹果质量为b，那么对于任何能均分的情况，我们都能找到一个集合S，使得b∈S；

       S可以视为每个人获得的苹果块的种类。

       一个重要的思维是：每次切割后，苹果块的数量增加1，增加的数量即为切割次数！

       由于原始的苹果数量为a，这意味着我们需要求出最终的苹果块数量。

       由于“尽量分配”原则，我们知道每人的每种苹果块只有一块:

       这意味着最终得到的苹果块数量是a/b；

       因此，最少切割数即为a/b。

       以示例说明：对于a=4，容易知道每个人得到的苹果块有两种大小，分别是1kg和2kg，此时b=2，那么只需要切割两次。

       问题最终转化成求|S|。

       为了使切割次数最少，我们需要使最终苹果块的数量尽可能少，这意味着我们需要让|S|尽可能小。

       在示例中，每个人得到的苹果块有两种大小，分别是1kg和2kg，我们知道此时切割的刀数最少——因为二进制中的b=2，转换为十进制即是3。

       容易证明，b的最小值即为二进制中b中“1”的个数。

       在二进制中，任何数除以2的整数次幂，只需在原数的基础上移动小数点（参考十进制÷的整数次幂），我们很容易知道，b中1的数量与原数中1的数量相同；

       由于__builtin_popcount()只能处理整数，因此__builtin_popcount(a)即为b中1的数量。

       那么，每组的最小切割数即为b，简化后即为a/b。

       附源码如下：

       写在后面：

       看似简单的一题，代码不到行，但思维含量极大，包含各种证明和方法，是一道很好的题。

       当然，通过猜测可能更快完成。