题目

https://leetcode.com/problems/nth-magical-number/

题解

看了答案：

草稿：

class Solution {
    public static final long MOD = 1000_000_007;

    public int nthMagicalNumber(int n, int a, int b) {
        long L = lcm(a, b); // 最小公倍数
        long M = L / a + L / b - 1; // 循环周期
        long q = n / M; // 循环次数
        long r = n - M * q; // 余数

        int i = 0;
        long cur = (L * q) % MOD;
        int ai = a > b ? 0 : 1;
        int bi = 1 - ai;
        while (i <= r) {
            if (ai * a < bi * b) {
                cur = ((L * q) % MOD + ((long) ai * a) % MOD) % MOD;
                ai++;
            } else {
                cur = ((L * q) % MOD + ((long) bi * b) % MOD) % MOD;
                bi++;
            }
            i++;
        }
        return (int) cur;
    }

    // 最小公倍数
    static long lcm(int a, int b) {
        return (a / gcd(a, b)) * b;
    }

    // 最大公因数
    static long gcd(int a, int b) {
        if (a == 0) return b;
        return gcd(b % a, a);
    }
}