二分
题目描述
我们的目标是找到一个最小楼层数ans,使得其中有n个不包含质数x的楼层属于A牛,有m个不包含质数y的楼层属于B牛。我们并不关心A和B具体得到了哪层楼,只要有足够的楼层可以分配给他们即可。
对于其中某些楼层,既可以满足A牛,也可以满足B牛,ans - ans // (x * y) 可以筛选出要么只能满足A,要么只能满足B,或者A和B可以同时满足的楼层数,如果该数量大于n + m,具有了满足A牛和B牛的初步条件。
进一步,我们可以轻松地得到是否有ans - (ans // x) 大于等于n ,对于B同理,如果ans同时满足上述三个条件,则该ans满足条件,即有超过n层楼可以分配给A牛,超过m层楼可以分配给B牛。
n, m, x, y = map(int, input().split())
H = n + m
in_xy = H // (x * y)
while (H - in_xy) < n + m:
H *= 2
in_xy = H // (x * y)
l = H //2 - 1
r = H + 1
def check(mid):
if mid - (mid // x) >= n and mid - (mid // y) >= m and (mid - mid // (x * y)) >= n + m:
return True
return False
while l + 1 < r:
mid = l + r >> 1
if check(mid):
r = mid
else:
l = mid
print(r)