解題說明
Ugly Number III
題目描述： 給定整數 n, a, b, c，找第 n 個「醜數」——能被 a、b 或 c 整除的正整數（按升序排列中的第 n 個）。
解題思路：
- 二分搜尋 + 容斥原理：二分搜尋答案 x。對於給定的 x，計算 [1, x] 中有多少個數能被 a, b 或 c 整除。
- 容斥公式：count = x/a + x/b + x/c - x/lcm(a,b) - x/lcm(a,c) - x/lcm(b,c) + x/lcm(a,b,c)
- 其中 lcm(a,b) = a*b / gcd(a,b)。
- 二分搜尋找到最小的 x 使得 count >= n。
- 注意：使用 long long 避免溢出。
C++ 解法
複雜度分析
時間複雜度：O(log(2 * 10^9)) ≈ O(31) — 二分搜尋的範圍
空間複雜度：O(1) — 只用常數空間
虛擬碼
1. Precompute LCMs: lcm(a,b), lcm(a,c), lcm(b,c), lcm(a,b,c)
2. Binary search on answer x in range [1, 2*10^9]:
a. Compute count of ugly numbers in [1, mid] using inclusion-exclusion:
count = mid/a + mid/b + mid/c - mid/lcm(a,b) - mid/lcm(a,c) - mid/lcm(b,c) + mid/lcm(a,b,c)
b. If count >= n: search left half (hi = mid)
c. Else: search right half (lo = mid + 1)
3. Return lo其他解法
-
三指標合併：類似歸併排序，維護三個指標分別指向 a, b, c 的倍數序列，每次取最小值。時間複雜度 O(n)，在 n 很大時（最大 10^9）會超時。
-
最小堆：將 a, b, c 的倍數放入最小堆，每次取出最小值。用集合去重。時間複雜度 O(n log n)，同樣在 n 很大時不可行。二分搜尋是此題的最優解。
延伸思考
- 如果不是 3 個除數而是 k 個，容斥公式會變得多複雜？有更好的方法嗎？
- 如果要找第 n 個不能被 a, b, c 任何一個整除的數呢？
- 二分搜尋的上界如何更精確地確定？