题目分析

本题是一个数学题，这个题目并不是很困难，很容易就想到要使用什么方法。这里提示一下，一个数可以整除a，那么第k个数就是a x k，如果一个数既可以整除a，又可以整除b，那么如何考虑呢？是否第a + b个数是a x b呢？

二分查找

上面的答案是否定的，因为第a x b既可以整除a，又可以整除b。小伙伴就会问了，那第a + b个数是否是a x b + min(a, b)呢？

答案也不是，因为a x b一定可以整除a和b，小于a x b的值也可能可以整除a和b，只要是a和b的最小公倍数即可。记最小公倍数为lcm。

因此给定一个数x，判断小于等于x的数里能整除a和b的数有多少个，即x / a + x / b - x / lcm。这句话是本题的关键，里面含有多少个最小公倍数，就说明多计算了多少次。

而且随着x的增加，能整除a和b的数是单调递增的，那么可以使用二分查找求解。

算法的时间复杂度为O(log(mn))，空间复杂度为O(1)。其中m为a和b的范围，n为个数范围。

class Solution {
    private static final int MOD = 1000000007;

    public int nthMagicalNumber(int n, int a, int b) {
        long left = Math.min(a, b);
        long right = n * left;
        int lcm = getLcm(Math.max(a, b), (int) left);
        while (left < right) {
            long mid = (left + right) >> 1;
            int cnt = (int) (mid / a + mid / b - mid / lcm);
            if (n > cnt) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return (int) (left % MOD);
    }

    private int getLcm(int a, int b) {
        int gcd = getGcd(a, b);
        return a / gcd * b;
    }

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

数学

本题还可以继续优化，一个lcm内含有lcm / a + lcm / b - 1个元素。记cnt = lcm / a + lcm / b - 1。

那么n个元素有n / cnt个lcm。记base = n / cnt x lcm，所以base中含有n / cnt x cnt个元素可以整除a和b。

那么剩余n % cnt个元素，记为remain。那么剩下的元素就从a和b开始计数即可。最多计数a + b次。

算法的时间复杂度为O(a + b)，空间复杂度为O(1)。

class Solution {
    private static final int MOD = 1000000007;

    public int nthMagicalNumber(int n, int a, int b) {
        int lcm = getLcm(Math.max(a, b), Math.min(a, b));
        int cnt = lcm / a + lcm / b - 1;
        long base = (long) n / cnt * lcm;
        int remain = n % cnt;
        if (remain == 0) {
            return (int) (base % MOD);
        }
        int pA = a;
        int pB = b;
        while (--remain > 0) {
            if (pA < pB) {
                pA += a;
            } else {
                pB += b;
            }
        }
        return (int) ((base + Math.min(pA, pB)) % MOD);
    }

    private int getLcm(int a, int b) {
        int gcd = getGcd(a, b);
        return a / gcd * b;
    }

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

刷题总结

本题除了掌握如何求解外，还需要掌握如何使用辗转相除法计算最大公约数gcd，以及如何使用gcd求出最大公倍数lcm。