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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
export default function nthUglyNumber(    n: number,    a: number,    b: number,    c: number,): number {    return Number(nthUglyBigInt(BigInt(n), BigInt(a), BigInt(b), BigInt(c)));}export function nthUglyBigInt(    n: bigint,    a: bigint,    b: bigint,    c: bigint,): bigint {    // 先将数值转换为 BigInt 类型    (a = BigInt(a)), (b = BigInt(b)), (c = BigInt(c)), (n = BigInt(n));
    // BigInt 不能使用 Math 函数判断，所以自己写一个    // 求最小公倍数
    // 检查是否是丑数    function check(val: bigint) {        return val % a === 0n || val % b === 0n || val % c === 0n;    }
    let r = n * min(a, b, c);    let l = 0n;    const a_b = lcm(a, b);    const a_c = lcm(a, c);    const b_c = lcm(b, c);    const a_b_c = lcm(a_b, c);
    // 二分查找丑数    while (l < r) {        const mid = l + (r - l) / 2n;        const count = mid / a +            mid / b +            mid / c -            mid / a_b -            mid / b_c -            mid / a_c +            mid / a_b_c;
        if (count === n) {            // 当 count 等于 n 时还需要再判断是否为丑数，因为对于BigInt的除法来说， 4 / 2 和 5 / 2 的结果是相等的            if (check(mid)) {                return mid;            } else {                r = mid - 1n;            }        }        if (count < n) {            l = mid + 1n;        } else {            r = mid - 1n;        }    }
    return check(l) ? l : -1n;} // 求最大公约数export function lcm(a: bigint, b: bigint) {    return (a * b) / gcd(a, b);}export function min(a: bigint, b: bigint, c: bigint) {    let m = a;    if (m > b) {        m = b;    }    if (m > c) {        m = c;    }
    return m;}export function gcd(a: bigint, b: bigint): bigint {    if (b === 0n) {        return a;    } else {        return gcd(b, a % b);    }}