题解 | 汉堡猪猪分糖果

·题意

给定n颗糖果，要求分成m份，每份c_i （c_i >= 1）个, 求c_1 & c_2 & c_3 & ... & c_m 的最大值。

·分析

·首先我们知道，根据位与&的特性，就算有某些c_i 占据了高的数位，有一个c_j 在该位上为0，那&起来的结果肯定为0。

·所以我们希望位与和的结果足够大，就得保证每个c_i 的最高位都为1。

·这启发我们从高位到低位枚举贪心，看看n 能分成m个的哪些位。

·枚举位

·若我们用的还剩下tmp个糖果， 当前为从高(31)到低(0) 第i位，如果最后的结果该位为1，则需要 m * (1 << i） 个糖果；

·若 tmp >= m * (1 << i）, 则直接选该位，tmp 对应减去m * (1 << i）

·若 tmp < m * (1 << i）, 注意，因为tmp 有可能比剩下的位全是1时还大( 即大于 m * ((1 << i） - 1))， 此时，我们需要将多出来的糖果放在这一位, 因为tmp < m * (1 << i） 所以这一位肯定填不满，不用选择该位；

		for (int i = 31; i >= 0; i -- )
		{
			ll bit = (1ll << i); // (对应盖位的二进制数)
			if (tmp >= bit * m) // tmp >= m * (1 << i）
			{
				tmp -= bit * m; 
				ans |= bit;
			}
			else if (tmp > bit * m - m) // tmp > m * ((1 << i） - 1)
			{
				tmp -= (tmp - bit * m + m + bit - 1) / bit * bit; // (减去能放在该位的多余糖果，注意是上取整)
			}
		}

·复杂度

时间复杂度 O(32 * T) 即 O(T);

空间负责度 O(1)

·完整代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;
typedef long long ll;

ll n, m;

int main()
{
	int T;
	scanf("%d", &T);
	while (T -- )
	{
		scanf("%lld%lld", &n, &m);
		ll tmp = n, ans = 0; 
		for (int i = 31; i >= 0; i -- )
		{
			ll bit = (1ll << i);
			if (tmp >= bit * m)
			{
				tmp -= bit * m; 
				ans |= bit;
			}
			else if (tmp > bit * m - m)
			{
				tmp -= (tmp - bit * m + m + bit - 1) / bit * bit;
			}
		}
		printf("%lld\n", ans);
	}
	
	return 0;
}  

希望对大家有所帮助qwq

还有，各位除夕快乐！