员工派遣
某公司部门需要派遣员工去国外做项目。
现在，代号为 $x$ 的国家和代号为 $y$ 的国家分别需要 $cnt_x$ 名和 $cnt_y$ 名员工。
部门每个员工有一个员工号（1, 2, 3, ...），工号连续，从 1 开始。
部长派遣员工的规则如下：
- 规则 1：从 $[1, k]$ 中选择员工派遣出去
- 规则 2：编号为 $x$ 的倍数的员工不能去 $x$ 国，编号为 $y$ 的倍数的员工不能去 $y$ 国。
目标： 找到最小的 $k$，使得可以将编号在 $[1, k]$ 中的员工分配给 $x$ 国和 $y$ 国，且满足两国的需求。
输入描述
四个整数 $x, y, cnt_x, cnt_y$。
- $2 \le x < y \le 30000$
- $x$ 和 $y$ 一定是质数
- $1 \le cnt_x, cnt_y < 10^9$
- $cnt_x + cnt_y \le 10^9$
问题分析
这道题的核心在于判断对于给定的 $k$，是否能够满足两个国家的用工需求。由于 $k$ 越大，可选的员工越多，满足条件的可能性也越大，这符合单调性，因此可以使用二分查找来确定最小的 $k$。
关键在于如何计算在范围 $[1, k]$ 内，有多少员工可以分配给 $x$ 国，多少可以分配给 $y$ 国，以及是否存在冲突。
根据题目规则：
- 能被 $x$ 整除的员工：不能去 $x$ 国，但可以去 $y$ 国（除非也能被 $y$ 整除）。
- 能被 $y$ 整除的员工：不能去 $y$ 国，但可以去 $x$ 国（除非也能被 $x$ 整除）。
- 既能被 $x$ 又能被 $y$ 整除的员工（即 $LCM(x, y)$ 的倍数）：既不能去 $x$ 国也不能去 $y$ 国，属于无效人员。
- 既不能被 $x$ 也不能被 $y$ 整除的员工：可以去任意一个国家。
我们需要将员工池划分为三类有效资源：
- 专供 $x$ 国：能被 $y$ 整除但不能被 $x$ 整除的人数。
- 专供 $y$ 国：能被 $x$ 整除但不能被 $y$ 整除的人数。
- 通用资源：既不能被 $x$ 也不能被 $y$ 整除的人数。
设 $L = LCM(x, y)$。在 $[1, k]$ 范围内：
- 能被 $x$ 整除的数量：$\lfloor k/x \rfloor$
- 能被 $y$ 整除的数量：$\lfloor k/y \rfloor$
- 能被 $L$ 整除的数量：$\lfloor k/L \rfloor$
各类可用人数计算如下：
- 专供 $x$ 国 ($count_{only_x}$)：能被 $y$ 整除但不能被 $x$ 整除。 $$count_{only_x} = \lfloor k/y \rfloor - \lfloor k/L \rfloor$$
- 专供 $y$ 国 ($count_{only_y}$)：能被 $x$ 整除但不能被 $y$ 整除。 $$count_{only_y} = \lfloor k/x \rfloor - \lfloor k/L \rfloor$$
- 通用资源 ($count_{any}$)：既不能被 $x$ 也不能被 $y$ 整除。 $$count_{any} = k - (\lfloor k/x \rfloor + \lfloor k/y \rfloor - \lfloor k/L \rfloor)$$
判定逻辑
给定 $k$，检查是否满足以下条件：
- $x$ 国总需求不能超过其专属资源加通用资源：$cnt_x \le count_{only_x} + count_{any}$
- $y$ 国总需求不能超过其专属资源加通用资源：$cnt_y \le count_{only_y} + count_{any}$
- 两国从通用资源中抽取的需求之和不能超过通用资源总量： $$\max(0, cnt_x - count_{only_x}) + \max(0, cnt_y - count_{only_y}) \le count_{any}$$
