1201. Ugly Number III

Ugly Number III

題目描述： 給定整數 n, a, b, c，找第 n 個「醜數」——能被 a、b 或 c 整除的正整數（按升序排列中的第 n 個）。

解題思路：

1. 二分搜尋 + 容斥原理：二分搜尋答案 x。對於給定的 x，計算 [1, x] 中有多少個數能被 a, b 或 c 整除。
2. 容斥公式：count = x/a + x/b + x/c - x/lcm(a,b) - x/lcm(a,c) - x/lcm(b,c) + x/lcm(a,b,c)
3. 其中 lcm(a,b) = a*b / gcd(a,b)。
4. 二分搜尋找到最小的 x 使得 count >= n。
5. 注意：使用 long long 避免溢出。

時間複雜度：O(log(2 * 10^9)) ≈ O(31) — 二分搜尋的範圍

空間複雜度：O(1) — 只用常數空間

1. 三指標合併：類似歸併排序，維護三個指標分別指向 a, b, c 的倍數序列，每次取最小值。時間複雜度 O(n)，在 n 很大時（最大 10^9）會超時。

2. 最小堆：將 a, b, c 的倍數放入最小堆，每次取出最小值。用集合去重。時間複雜度 O(n log n)，同樣在 n 很大時不可行。二分搜尋是此題的最優解。

1. 如果不是 3 個除數而是 k 個，容斥公式會變得多複雜？有更好的方法嗎？
2. 如果要找第 n 個不能被 a, b, c 任何一個整除的數呢？
3. 二分搜尋的上界如何更精確地確定？