Daily LeetCode – day0116 0878. Nth Magical Number

// 0878. Nth Magical Number
class Solution {
    public int nthMagicalNumber(int n, int a, int b) {
        int c = lcm(a, b);
        long left = Math.min(a, b);
        long right = left * n;
        while (left < right) {
            long mid = left + (right - left) / 2;
            long count = mid / a + mid / b - mid / c;
            if (count == n) {
                right = mid;
            } else if (count > n) {
                right = mid;
            } else if (count < n){
                left = mid + 1;
            }
        }
        return (int) (left % (1e9 + 7));
    }

    private int lcm(int a, int b) {
        return a * b / gcd(a, b);
    }

    private int gcd(int a, int b) {
        if (b == 0) {
            return a;
        }
        return gcd(b, a % b);
    }
}

学习笔记：
这道题目是一道不容易的题目，很考验基本功。
先用一波数学分析，这样就可以快速求出某个数字是第n个了。
先手是求最大公约数，然后最小公倍数，接下来就是二分查找。
这是向左边界进行搜索的二分查找。