878

class Solution {
public:
    int nthMagicalNumber(int n, int a, int b) {
        int mod = 1e9+7;
        long long int low = 0, high, mid, lcm;
        high = (long long)min(a, b) * n;
        lcm = a*b / __gcd(a, b);

        // Binary search the number.
        while(low < high){
            mid = low + (high-low)/2;
            if((mid/a + mid/b - mid/lcm) < n)
                low = mid+1;
            else
                high = mid;
        }

        return low%mod;
    }
};