# LeetCode: 1201. 丑数 III¶

## 1、题目描述¶

输入：n = 3, a = 2, b = 3, c = 5



输入：n = 4, a = 2, b = 3, c = 4



输入：n = 5, a = 2, b = 11, c = 13



输入：n = 1000000000, a = 2, b = 217983653, c = 336916467



• $1 <= n, a, b, c <= 10^9$
• $1 <= a * b * c <= 10^{18}$
• 本题结果在 [1, 2 * 10^9] 的范围内

## 2、解题思路¶

• 首先计算数字两两之间的最小公倍数
• 然后算出三个数的最小公倍数
• 计算出从最小的数字到最小公倍数之间有多少满足条件的数字，后面的数字将在这里面循环，只是初始值不同
• 通过二分法，找出目标值是这个循环中的第几个数字
import math

class Solution:
def nthUglyNumber(self, n: int, a: int, b: int, c: int) -> int:
lcm_ab = a * b // math.gcd(a, b)
lcm_ac = a * c // math.gcd(a, c)
lcm_bc = b * c // math.gcd(b, c)

lcm = lcm_ab * c // math.gcd(lcm_ab, c)

def find_ugly_nums(k):
# 找出<=K 的丑数的个数
cur = 0
cur += k // a + k // b + k // c - k // lcm_ab - k // lcm_ac - k // lcm_bc + k // lcm
return cur

cycle = find_ugly_nums(lcm)
start = lcm * (n // cycle)
pos = n % cycle
if pos == 0:
return start

left = min(a, b, c)
right = lcm

while left < right:
mid = (left + right) // 2
if find_ugly_nums(mid) < pos:
left = mid + 1
else:
right = mid
return start + left