Nth Magical Number

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

        lcm = a*b//gcd(a,b)
        cyc = lcm//a + lcm//b - 1
        res = n//cyc * lcm
        n = n%cyc

        if n == 0:
            return res%int(1e9+7)
        if n == 1:
            return (res + min(a,b))%int(1e9+7)

        lo,hi = min(a,b)+1, lcm-1
        mid = (lo + hi)//2
        while (lo < hi):
            tar = mid//a + mid//b
            if n <= tar:
                hi = mid
            else:
                lo = mid + 1
            mid = (lo + hi)//2
        return (res+lo)%int(1e9+7)