題目連結：
題目意譯：
一個醜數為一正整數，其可以被 a 、 b 或是 c 所整除。
給定四整數 n 、 a 、 b 和 c ，回傳第 n 個醜數。
限制：
1 ≦ n 、 a 、 b 、 c ≦ 10 ^ 9
1 ≦ a × b × c ≦ 10 ^ 18
保證結果位於範圍 [1, 2 × 10 ^ 9] 中。
範例測資：
範例 1：
輸入： n = 3, a = 2, b = 3, c = 5
輸出： 4
解釋： 醜數們為 2, 3, 4, 5, 6, 8, 9, 10……第 3 個為 4。
範例 2：
輸入： n = 4, a = 2, b = 3, c = 4
輸出： 6
解釋： 醜數們為 2, 3, 4, 6, 8, 9, 10, 12……第 4 個為 6。
範例 3：
輸入： n = 5, a = 2, b = 11, c = 13
輸出： 10
解釋： 醜數們為 2, 4, 6, 8, 10, 11, 12, 13……第 5 個為 10。
範例 4：
輸入： n = 1000000000, a = 2, b = 217983653, c = 336916467
輸出： 1999999984
解題思維：
假設我們要求正整數 1 ～ K 之間有多少整數可以被 a 、 b 或是 c 整除（即求 1 ～ K 之間有多少醜數），則我們可以利用排容原理求得（Inclusion–Exclusion Principle，如這題所述），即
floor(K ÷ a) + floor(K ÷ b) + floor(K ÷ c)
- floor(K ÷ LCM(a, b)) - floor(K ÷ LCM(a, c)) - floor(K ÷ LCM(b, c))
+ floor(K ÷ LCM(a, b, c))
其中 floor() 為下高斯函數（對於正數來說，等價於無條件捨去小數部分）、LCM() 為求括號中的數字之最小公倍數（Lowest Common Divisor）。
有了以上算法之後，我們便可以將其套用在二分搜尋法（Binary Search）上用來判斷二分的「答案」（如這題）：
令下界 L = 1 、上界 U = 2000000000。
接著每次二分時，令 M = (L + U) ÷ 2 ，如果 M 根據上面的算法得出的醜數數量 < n，則提高我們的下界 → 令 L = M + 1 ；反之，如果 M 得出的醜數數量 ≧ n，則降低上界 → U = M 。
當 L = U 時，此時的 L 即是第 n 個醜數。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
達人
