C. Jellyfish and Green Apple
题目大意:
有\(n\)苹果,\(m\)个人,将苹果平分给每个人,每块苹果可以二分,问最少的分割次数
思路:
首先,当\(n\%m==0\)时,说明,苹果可以等分直接输出\(0\)
其次当\(n>m\)时,\(n\%=m\),
最终的苹果块数\(x\)肯定是\(lcd(n,m)\),由\(lcd(n,m)*gcd(n,m)=n*m\)
因为苹果只能二分所以,每个苹果被分成的个数必须是\(2\)的幂级数,每个人拿到的苹果块数应该逢二进一(因为满二说明这刀可以不切),即\(x/m\)中二进制\(1\)的个数
code:
int n, m;
void solved()
{
cin >> n >> m;
if (n % m == 0)
{
cout << 0 << endl;
return;
}
else
{
n %= m;
int x = m * n / gcd(m, n);
int x1 = x / n;
if (x1 & (x1 - 1))
{
cout << -1 << endl;
return;
}
int y = x / m;
int res = 0;
// while (y)
// {
// if (y & 1)
// res++;
// y >>= 1;
// // Brian Kernighan 的位计数算法
// // ++res;
// // y = (y & (y - 1));
// }
res = __builtin_popcount(y);
cout << res * m - n << endl;
}
}