倒是很容易想到用二分来做 因为最小楼层数可以二分 当小于最小楼层数就不符合答案 楼层数大于最小楼层数 贝希和贝蒂就都能选完他们的楼层
但是check()函数该怎么写确实是难题
由题 贝西需要不被x整除的整数 贝蒂需要不被y整除的整数
注释① 由于送给贝西的数能被y整除(这样才能不被包含进集合B) 所以送给贝西的数需要在能被y整除的数中选,能被y整除的数$\lfloor\frac{H}{y}\rfloor$ 在这些数里面我们还需要剔除能被x整除的数$\lfloor\frac{H}{xy}\rfloor$
所以最终是$\lfloor\frac{H}{y}\rfloor - \lfloor\frac{H}{xy}\rfloor$
注释② 与$①$同理
注释③ 那么既不能被x整除也不能被y整除的数就需要在全部数种减去能被x和y整除的数 再加上减了两次的能被x和y都整除的数的个数 $H- (\lfloor\frac{H}{y}\rfloor + \lfloor\frac{H}{x}\rfloor) + \lfloor\frac{H}{xy}\rfloor$
当贝西选了A个楼层贝蒂选了B个楼层 他们还缺的楼层要用C来补 如果C能补完 那就是合法的楼层高度
很绕 本题还要注意爆int的问题 开成longlong
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int n, m, x, y;
bool check(LL mid)
{
LL a = mid / y - mid / (x * y); //只能送给贝西的楼层
LL b = mid / x - mid / (x * y); //只能送给贝蒂的楼层
LL c = mid - (mid / x + mid / y) + mid / (x * y); //都能送的楼层
LL s1 = max(0ll, n - a); //贝西还缺的楼层 这里取max的原因是 如果a已经够了贝西需要的楼层数 那n-a就会是负数 此时不缺楼层了 与0取max
LL s2 = max(0ll, m - b); //贝蒂还缺的楼层
if (c >= s1 + s2) return true; //都能送的楼层够用就返回true
else return false;
}
void solve()
{
scanf("%d%d%d%d", &n, &m, &x, &y);
LL l = 1, r = 1e18; //直接开到long long上限 因为你不知道需要有多少楼层 当x和y是2 3时那就有非常多的楼层不满足要求 那最大楼层数就会非常大 所以我们直接开到上限
while (l < r)
{
//在数轴上答案最小楼层数的右边是满足要求的 那我们就是求左边界
LL mid = l + r >> 1;
if (check(mid)) r = mid;
else l = mid + 1;
}
printf("%lld", r);
return;
}
int main()
{
solve();
return 0;
}
好图 来自@美琴