878.md

878. Nth Magical Number

Solution 1 (time O(log(n)), space O(1))

class Solution(object):
    def nthMagicalNumber(self, n, a, b):
        """
        :type n: int
        :type a: int
        :type b: int
        :rtype: int
        """
        def gcd(a, b):
            return a if b == 0 else gcd(b, a % b)

        c = a * b // gcd(a, b)
        left, right = 0, 1e18
        while left < right:
            mid = (left + right) // 2
            if mid // a + mid // b - mid // c >= n:
                right = mid
            else:
                left = mid + 1
        return int(right % 1000000007)