题目描述

某公司部门需要派遣员工去国外做项目。

现在，代号为 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

用例

解题思路

题目的问题是：要找到一个最小的k，使得在遵守上述规则的情况下，可以从编号在[1, k]中的员工中选择足够的员工派遣到x国和y国，满足他们的需求。

输入数据的解释如下：

• 2 表示员工的ID如果是2的倍数，就不能派遣到国家X。
• 3 表示员工的ID如果是3的倍数，就不能派遣到国家Y。
• 3 表示国家X需要3个员工。
• 1 表示国家Y需要1个员工。

我们需要找到一个最小的员工ID，使得在[1, ID]的范围内，能够找到至少3个可以派遣到国家X的员工和至少1个可以派遣到国家Y的员工。

在这个例子中，员工ID为5是满足条件的最小值。因为在[1, 5]的范围内，可以找到3个可以派遣到国家X的员工（他们的ID是1, 3, 5），以及1个可以派遣到国家Y的员工（他的ID是1）。所以，输出结果是5。

这段代码使用了二分查找法（Binary Search）来寻找满足特定条件的最小员工ID。二分查找法是一种在有序集合中查找特定元素的搜索算法，通过每次比较中间元素来缩小搜索范围，从而提高查找效率。

这里的特定条件是：在排除不能同时为两个国家工作的员工后，剩余的员工数量能满足两个国家的需求。

1. 二分查找法：

   • 初始化搜索范围，下限为两国员工需求之和，上限为一个大数（例如10亿）。
   • 在每次循环中，计算搜索范围的中间值 midStaffID。
   • 根据 midStaffID 判断是否满足条件，然后调整搜索范围。如果满足条件，缩小上限；否则，增大下限。
   • 重复上述过程，直到找到满足条件的最小 midStaffID。

2. 排除法：

   • 计算在1到 midS 范围内，不能同时为两个国家工作的员工数量。