1

(本文以python解題)

# 263. Ugly Number

``````class Solution:
def isUgly(self, num: int) -> bool:
if num<1:
return False
for factor in {2,3,5}:
while num%factor == 0:
num = num//factor
return num==1
``````

# 264. Ugly Number II

``````class Solution:
def nthUglyNumber(self, n: int) -> int:
ugly = [0] * n # To store ugly numbers
ugly[0] = 1
i2 = i3 = i5 = 0

# set initial multiple value
next_multiple_of_2 = 2
next_multiple_of_3 = 3
next_multiple_of_5 = 5

for l in range(1, n):
ugly[l] = min(next_multiple_of_2, next_multiple_of_3, next_multiple_of_5)
if ugly[l] == next_multiple_of_2:
i2 += 1
next_multiple_of_2 = ugly[i2] * 2
if ugly[l] == next_multiple_of_3:
i3 += 1
next_multiple_of_3 = ugly[i3] * 3
if ugly[l] == next_multiple_of_5:
i5 += 1
next_multiple_of_5 = ugly[i5] * 5
return ugly[-1]
``````

# 313. Super Ugly Number

``````class Solution:
def nthSuperUglyNumber(self, n: int, primes: List[int]) -> int:
ugly = [0] * n # To store ugly numbers
ugly[0] = 1
p_idx = [0] * len(primes)

# set initial multiple value
next_multiple_of_p = primes[:]

for l in range(1, n):
ugly[l] = min(next_multiple_of_p[i] for i in range(len(primes)))
for i in range(len(primes)):
if ugly[l] == next_multiple_of_p[i]:
p_idx[i] += 1
next_multiple_of_p[i] = ugly[p_idx[i]] * primes[i]
return ugly[-1]
``````

# 1201. Ugly Number III

``````class Solution:
def gcd(self, m, n):
return m if n == 0 else gcd(n, m % n)

def lcm(self, m, n):
return m * n // self.gcd(m, n)

def count(self, k, a, b, c):
#數學的排容原理，計算有[1,k]中有幾個數可被a or b or c整除
na = k // a
nb = k // b
nc = k // c
nab = k // self.lcm(a, b)
nac = k // self.lcm(a, c)
nbc = k // self.lcm(b, c)
nabc = k // self.lcm(self.lcm(a, b), c)
return na + nb + nc - nab - nac - nbc + nabc

def nthUglyNumber(self, n: int, a: int, b: int, c: int) -> int:
l, r = 0, 2*10**9  #答案在[l, r]中間
while l < r:
mid = l + (r - l)//2
cnt = self.count(mid, a, b, c)
print(l, r, mid,cnt)
if cnt >= n:
if cnt == n and (mid % a == 0 or mid % b == 0 or mid % c == 0):
return mid
r = mid - 1
else:
l = mid + 1
return l
``````