Lc1201

#time O(lgN) space O(1)
class Solution:
    def nthUglyNumber(self, n: int, a: int, b: int, c: int) -> int:
        max_val = 2*10**9
        l = 1
        r = max_val
        #step1 gcd   
        def gcd(a,b):
            if b == 0:
                return a
            else:
                return gcd(b, a%b)
        
        #step 2 lcm
        def lcm(a,b):
            return a*b//gcd(a,b)
        
        # step3 vienn count
        def vien(num, a,b,c):
            res=  num//a + num//b + num//c - num//lcm(a,b) - num//lcm(a,c) - num//lcm(b,c) + num//lcm(a,lcm(b,c))
            return res
        
        # step4 binary search 
        while l <r:
            mid = (l+r) >>1
            if vien(mid, a,b,c) < n:
                l = mid + 1
            else:
                r = mid
        return l