第 N 个神奇数字

一个正整数如果能被 a 或 b 整除，那么它是神奇的。
给定三个整数 n , a , b ，返回第 n 个神奇的数字。因为答案可能很大，所以返回答案 对 109 + 7 取模 后的值。

  • 输入：n = 1, a = 2, b = 3
    输出：2

  • 输入：n = 4, a = 2, b = 3
    输出：6

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
const MOD = 10 ** 9 + 7;
var nthMagicalNumber = function (n, a, b) {
    if (a > b) {
        return nthMagicalNumber(n, b, a);
    }
    if (b % a == 0) {
        return (a * n) % MOD;
    }
    // 求出a,b的最小公倍数以及中间的二者的倍数
    const res = commonMultiple(a, b);
    console.log(res);
    const len = res.length;
    let last = res[len - 1];
    const k = Math.floor((n - 1) / len);
    const rest = (n - 1) % len;
    return (last * k + res[rest]) % MOD;
};

var commonMultiple = function (a, b) {
    const ans = [];
    let proda = a;
    let prodb = b;
    while (proda !== prodb) {
        if (proda < prodb) {
            ans.push(proda);
            proda += a;
        } else if (prodb < proda) {
            ans.push(prodb);
            prodb += b;
        }
    }
    ans.push(proda);
    return ans;
};