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。

自建示例

三个整除集合可能互相重叠:

输入:n = 6, a = 4, b = 6, c = 9
输出:16
解释:前六个丑数为 4、6、8、9、12、16;12 同时被 4 和 6 整除,但只计一次。

第一个丑数就是三个除数中的最小值:

输入:n = 1, a = 7, b = 11, c = 13
输出:7
解释:所有满足条件的正整数中,7 最小,因此它是第一个丑数。