某公司部门需要派遣员工去国外做项目。
现在，代号为 x 的国家和代号为 y 的国家分别需要 cntx 名和 cnty 名员工部门每个员工有一个员工号 (1,2,3,......)，工号连续，从 1开始。部长派遣员工的规则:
规则1: 从 1,k中选择员工派遣出去
规则2: 编号为 x的倍数的员工不能去 x国，编号为 y 的倍数的员工不能去y 国
问题
找到最小的k，使得可以将编号在 [1,k] 中的员工分配给 x 国和 y 国，且满足 x 国和 y 国的需求
输入描述
四个整数 x,y,cntx,cnty。
2 < x < y < 30000
x和y 一定是质数
1 < cntx, cnty < 10^9
cntx + cnty < 10^9
输出描述
满足条件的最小的 k
示例1：
输入：
2 3 3 1输出：
5说明:
输入中：
2 表示国家代号 2
3 表示国家代号 3
3 表示国家 2 需要3 个人
1 表示国家 3 需要1个人
输出的5表示k最小为5
def save():
x, y, contx, conty = map(int, input().split())
left = contx + conty
right = (contx + conty) * 2
if not is_pass(right, x, y, contx, conty):
right *=2
while left < right:
mid = (left + right) // 2
if is_pass(mid,x, y, contx, conty):
right = mid
else:
left = mid+1
print(left)
return left
def is_pass(k, x, y, contx, conty):
if contx > k - (k // x):
return False
elif conty > k -(k // x):
return False
elif conty+contx > k-(k//(x*y)):
return False
return True
if __name__ == '__main__':
save()
注意
首先，1~k中能够被x整除的数个数为 k/x, 能够被y整除的个数为k/y，
其次，1~k中,既能被x整除，也能够被y整除的个数，就是 k/x*y。这样的话，既不是x也不是y的倍数，就是 k-k/x-k/y-k/x*y。