1201. Ugly Number III¶
题目信息¶
- 题号:
1201
- 难度:
Medium
- 主题:
二分查找、容斥原理、最小公倍数
- 原题:
- 重点:
丑数定义为能被
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 最小,因此它是第一个丑数。