Nth Magical Number

class Solution {
public:
    int nthMagicalNumber(int n, int a, int b) {
        long long L = (long long)a / __gcd(a, b) * b;
        long long lo = 1, hi = (long long)n * min(a, b);
        while (lo < hi) {
            long long m = (lo + hi) / 2;
            long long c = m / a + m / b - m / L;
            if (c < n) lo = m + 1; else hi = m;
        }
        return (int)(lo % 1000000007LL);
    }
};

func nthMagicalNumber(n int, a int, b int) int {
    gcd := func(x, y int) int {
        for y != 0 {
            x, y = y, x%y
        }
        return x
    }
    L := a / gcd(a, b) * b
    lo, hi := 1, n*a
    if b < a {
        hi = n * b
    }
    for lo < hi {
        m := (lo + hi) / 2
        c := m/a + m/b - m/L
        if c < n {
            lo = m + 1
        } else {
            hi = m
        }
    }
    return lo % 1000000007
}

import math

class Solution:
    def nthMagicalNumber(self, n: int, a: int, b: int) -> int:
        L = a // math.gcd(a, b) * b
        lo, hi = 1, n * min(a, b)
        while lo < hi:
            m = (lo + hi) // 2
            c = m // a + m // b - m // L
            if c < n:
                lo = m + 1
            else:
                hi = m
        return lo % 1_000_000_007

function nthMagicalNumber(n, a, b) {
    const gcd = (x, y) => {
        while (y !== 0) { [x, y] = [y, x % y]; }
        return x;
    };
    const L = BigInt(a) / BigInt(gcd(a, b)) * BigInt(b);
    const A = BigInt(a), B = BigInt(b), N = BigInt(n);
    let lo = 1n, hi = N * (a < b ? A : B);
    while (lo < hi) {
        const m = (lo + hi) / 2n;
        const c = m / A + m / B - m / L;
        if (c < N) lo = m + 1n;
        else hi = m;
    }
    return Number(lo % 1000000007n);
}

class Solution {
    public int nthMagicalNumber(int n, int a, int b) {
        long L = (long) a / gcd(a, b) * b;
        long lo = 1, hi = (long) n * Math.min(a, b);
        while (lo < hi) {
            long m = (lo + hi) / 2;
            long c = m / a + m / b - m / L;
            if (c < n) lo = m + 1;
            else hi = m;
        }
        return (int) (lo % 1000000007L);
    }

    private int gcd(int x, int y) {
        while (y != 0) {
            int t = y;
            y = x % y;
            x = t;
        }
        return x;
    }
}

function nthMagicalNumber(n: number, a: number, b: number): number {
    const gcd = (x: number, y: number): number => {
        while (y !== 0) { [x, y] = [y, x % y]; }
        return x;
    };
    const L = BigInt(a) / BigInt(gcd(a, b)) * BigInt(b);
    const A = BigInt(a), B = BigInt(b), N = BigInt(n);
    let lo = 1n, hi = N * (a < b ? A : B);
    while (lo < hi) {
        const m = (lo + hi) / 2n;
        const c = m / A + m / B - m / L;
        if (c < N) lo = m + 1n;
        else hi = m;
    }
    return Number(lo % 1000000007n);
}