1201. Ugly Number III ===================== 题目信息 -------- :题号: 1201 :难度: Medium :主题: 二分查找、容斥原理、最小公倍数 :原题: `LeetCode 1201 `_ :重点: 丑数定义为能被 ``a``、``b`` 或 ``c`` 至少一个整除的正整数;返回按升序排列后的第 ``n`` 个 题目重述 -------- 给定四个正整数 ``n``、``a``、``b`` 和 ``c``。若正整数 ``x`` 能被 ``a``、``b`` 或 ``c`` 中至少一个数整除,则称 ``x`` 为丑数。 把所有丑数按严格递增顺序排列,请返回其中第 ``n`` 个。一个数即使同时被多个给定整数整除,也只在序列中出现一次。 ``1 <= n, a, b, c <= 10^9``,题目保证答案不超过 ``2 * 10^9``。 自建示例 -------- 三个整除集合可能互相重叠: .. code-block:: text 输入:n = 6, a = 4, b = 6, c = 9 输出:16 解释:前六个丑数为 4、6、8、9、12、16;12 同时被 4 和 6 整除,但只计一次。 第一个丑数就是三个除数中的最小值: .. code-block:: text 输入:n = 1, a = 7, b = 11, c = 13 输出:7 解释:所有满足条件的正整数中,7 最小,因此它是第一个丑数。