题目描述
请你设计一个程序,用来找出第 n
个丑数。
丑数是可以被 a
或 b
或 c
整除的 正整数。
样例
输入:n = 3, a = 2, b = 3, c = 5
输出:4
解释:丑数序列为 2, 3, 4, 5, 6, 8, 9, 10... 其中第 3 个是 4。
输入:n = 4, a = 2, b = 3, c = 4
输出:6
解释:丑数序列为 2, 3, 4, 6, 8, 9, 12... 其中第 4 个是 6。
输入:n = 5, a = 2, b = 11, c = 13
输出:10
解释:丑数序列为 2, 4, 6, 8, 10, 11, 12, 13... 其中第 5 个是 10。
输入:n = 1000000000, a = 2, b = 217983653, c = 336916467
输出:1999999984
限制
1 <= n, a, b, c <= 10^9
1 <= a * b * c <= 10^18
- 本题结果在
[1, 2 * 10^9]
的范围内
算法
(二分,数论,容斥原理) $O(\log N)$
- 我们尝试二分最终的数字,每次判定有多少个丑数数小于等于它。
- 假设当前需要判定的数字为
m
。我们采用容斥原理求出有多少个丑数小于等于m
。 - 首先求出
a, b
的最小公倍数x
,a, c
的最小公倍数y
和b, c
的最小公倍数z
,以及a, b, c
的最小公倍数t
。 - 利用容斥原理,则每次有
m / a + m / b + m / c - m / x - m / y - m / z + m / t
个丑数小于等于m
。 - 注意,求三个数的最小公倍数,需要用两个数的最小公倍数和第三个数求。
时间复杂度
- 二分的时间复杂度为 $O(\log N)$,这里的 $N$ 为最大可能的答案。
空间复杂度
- 无需任何额外的空间,故空间复杂度为 $O(1)$。
C++ 代码
class Solution {
public:
#define LL long long
int nthUglyNumber(int n, int a, int b, int c) {
LL l = 1, r = 2000000000;
LL x = 1ll * a * b / __gcd(a, b);
LL y = 1ll * a * c / __gcd(a, c);
LL z = 1ll * b * c / __gcd(b, c);
LL t = 1ll * x * c / __gcd(x, 1ll * c);
while (l < r) {
LL mid = (l + r) >> 1, cnt = 0;
cnt = mid / a + mid / b + mid / c - mid / x - mid / y - mid / z + mid / t;
if (cnt >= n)
r = mid;
else
l = mid + 1;
}
return l;
}
};
怎么保证最后的l一定是丑数呢?
这个可以思考一下,如果不是
l
,二分会不会结束呢?4.利用容斥原理,则每次有 m / a + m / b + m / c - m / x - m / y - m / z + m / t 个丑数小于等于 t。
最后一个字母写错了叭,小于等于m??
已修正