A positive integer is magical if it is divisible by either a or b.

Given the three integers n, a, and b, return the nth magical number. Since the answer may be very large, return it modulo 109 + 7.

&nbsp;
Example 1:

Input: n = 1, a = 2, b = 3
Output: 2


Example 2:

Input: n = 4, a = 2, b = 3
Output: 6


&nbsp;
Constraints:


	1 &lt;= n &lt;= 109
	2 &lt;= a, b &lt;= 4 * 104


class Solution:
    def nthMagicalNumber(self, N: int, A: int, B: int) -> int:
        import math
        lcm= A*B // math.gcd(A,B)
        l,r=2,10**14
        while l<=r:
            mid=(l+r)//2
            n = mid//A+mid//B-mid//lcm
            if n>=N:
                r=mid-1
           
            else:
                l=mid+1
        return l%(10**9+7)
class Solution {
public int nthMagicalNumber(int n, int a, int b) {
    long N=(long)n;
    long A=(long)a;
    long B=(long)b;
    long mod=1000000007;
    long min=Math.min(A,B);
    long low=min;
    long high=min*N;
    long ans=0;
    while(low<=high)
    {
        long mid=(high-low)/2+low;
        long x=mid/A+mid/B-mid/lcm(A,B);
        if(x>=N)
        {
            ans=mid;
            high=mid-1;
        }
        else if(x<N)
        {
            low=mid+1;
        }
        else{
            high=mid-1;
        }
    }

    ans=ans%mod;
    return (int)ans;
}

long lcm(long a,long b)
{
    long tmpA=a;
    long tmpB=b;
    while(a>0)
    {
        long temp=a;
        a=b%a;
        b=temp;
    }

    return tmpA*tmpB/b;
}
}
class Solution 
{
public:
    
    int lcm(int a, int b)                   // Finding the LCM of a and b
    {
        if(a==b)
            return a;
        if(a > b)
        {
            int count = 1;
            while(true)
            {
                if((a*count)%b==0)
                    return a*count;
                count++;
            }
        }
        int count = 1;
        while(true)
        {
            if((b*count)%a==0)
                return b*count;
            count++;
        }
        return -1;      // garbage value--ignore.
    }
    
    int nthMagicalNumber(int n, int a, int b) 
    {
        long long int comm = lcm(a,b);                       //common element
        long long int first = (((comm*2) - comm) / a) - 1;   //no. of elements appearing before the comm multiples (a).
        long long int second = (((comm*2) - comm) / b) - 1;  //no. of elements appearing before the comm multiples(b).
    
        long long int landmark = (n / (first + second + 1)) * comm; // last common element before nth number.
        long long int offset = n % (first + second + 1);            // how many numbers to consider after last common
        
        long long int p = landmark, q = landmark;   // initialisations to find the offset from the landmarked element
        long long int ans = landmark;
        for(int i=1;i<=offset;i++)  // forwarding offset number of times.
        {
            if(p+a < q+b)           //this logic easily takes care of which elements to be considered for the current iteration. 
            {
                ans = p+a;
                p = p+a;
            }
            else
            {
                ans = q+b;
                q = q+b;
            }
        }
        
        return (ans%1000000007);    //returning the answer.
    }
};

/*
    a and b
    1st step would be to find the LCM of the two numbers --> Multiples of LCM would be the common numbers in the sequential pattern.
    The next step would be to find the numbers of a and numbers of b appearing between the common number.
    
	DRY : 
	
    4 and 6
    4 -> 4 8 12 16 20 24 28 32 36 40   -->  
    6 -> 6 12 18 24 30 36 42 48 54 60  -->
    
    4 6 8    12     16 18 20        24 --> n/(f + s) --->  23/4 = 5 and 3
    5th -----> (comm * 5 = 60) ------>
*/
/**
 * @param {number} n
 * @param {number} a
 * @param {number} b
 * @return {number}
 */
var nthMagicalNumber = function(n, a, b) {
    const gcd = (a1,b1)=>{
        if(b1===0) return a1;
        return gcd(b1,a1%b1)
    }
    const modulo = 1000000007;
    let low = 0;
    let high = 10e17;
    let lcmAB = Math.floor((a*b)/gcd(a,b));
    
    while(low<high){
        let mid = Math.floor((low+high)/2);
        let ans = Math.floor(mid/a)+Math.floor(mid/b)-Math.floor(mid/lcmAB);
        if(ans<n){
            low = mid + 1;
        }else{
            high = mid;
        }
    }
    return high%modulo;
};
Nth Magical Number