以下是 LeetCode 3378. 统计最小公倍数图中的连通块数目 的 TypeScript 实现：

解题思路

本题核心思路是 并查集 + 倍数枚举：

1. 关键观察：如果 `a` 能整除 `b`（即 `b` 是 `a` 的倍数）且 `b <= threshold`，则 `lcm(a, b) = b <= threshold`，所以 `a` 和 `b` 之间必有边。

2. 大于 threshold 的数：`lcm(a, b) >= max(a, b)`，所以若 `nums[i] > threshold`，它与任何数的 lcm 都大于 threshold，是孤立节点。

3. 枚举策略：对于每个 `num <= threshold`，枚举其所有倍数 `j = num, 2*num, 3*num, ... <= threshold`，将这些数与 `num` 用并查集合并。这样所有有公共因子的数最终会被合并到同一个连通块。

4. 统计答案：大于 threshold 的数各自独立；小于等于 threshold 的数通过并查集找根节点，统计不同根的数量。

TypeScript 代码

```typescript
class DSU {
    private parent: number[];
    private rank: number[];

    constructor(n: number) {
        this.parent = new Array(n + 1);
        this.rank = new Array(n + 1).fill(0);
        for (let i = 0; i <= n; i++) {
            this.parent[i] = i;
        }
    }

    /** 查找根节点，带路径压缩 */
    find(x: number): number {
        if (this.parent[x] !== x) {
            this.parent[x] = this.find(this.parent[x]);
        }
        return this.parent[x];
    }

    /** 合并两个集合，按秩合并 */
    union(u: number, v: number): void {
        let uRoot = this.find(u);
        let vRoot = this.find(v);
        if (uRoot === vRoot) {
            return;
        }
        // 按秩合并：将秩较小的树合并到秩较大的树下
        if (this.rank[uRoot] < this.rank[vRoot]) {
            [uRoot, vRoot] = [vRoot, uRoot];
        }
        this.parent[vRoot] = uRoot;
        if (this.rank[uRoot] === this.rank[vRoot]) {
            this.rank[uRoot]++;
        }
    }
}

function countComponents(nums: number[], threshold: number): number {
    const dsu = new DSU(threshold);

    // 对于每个 num <= threshold，将其与所有倍数用并查集合并
    for (const num of nums) {
        if (num > threshold) {
            continue; // 大于 threshold 的数不参与并查集
        }
        // 枚举 num 的所有倍数：num, 2*num, 3*num, ... <= threshold
        for (let j = num; j <= threshold; j += num) {
            dsu.union(num, j);
        }
    }

    // 统计连通块数量
    const uniqueParents = new Set<number>();
    for (const num of nums) {
        if (num > threshold) {
            // 大于 threshold 的数各自独立成一个连通块
            uniqueParents.add(num);
        } else {
            uniqueParents.add(dsu.find(num));
        }
    }

    return uniqueParents.size;
}
```

复杂度分析

- 时间复杂度：O(threshold × log(threshold))。对于每个数 `num`，枚举其倍数的时间为 `threshold/num`，总和约为 `threshold × (1 + 1/2 + 1/3 + ...)` ≈ `threshold × log(threshold)`。并查集操作近似 O(α(n))。
- 空间复杂度：O(threshold)，用于并查集数组和 Set。

示例验证

- 示例1：`nums = [2,4,8,3,9], threshold = 5`
  - 大于 5 的数：8, 9 → 各自独立（2个连通块）
  - 2 的倍数：2, 4 → 合并 2 和 4
  - 3 的倍数：3（无其他倍数 ≤5）
  - 最终连通块：{2,4}, {3}, {8}, {9} → 4个

- 示例2：`nums = [2,4,8,3,9,12], threshold = 10`
  - 大于 10 的数：12 → 1个连通块
  - 2 的倍数：2, 4, 6, 8, 10 → 合并 2,4,8
  - 3 的倍数：3, 6, 9 → 合并 3,9
  - 通过 6（2×3），2的连通块和3的连通块连通
  - 最终连通块：{2,3,4,8,9}, {12} → 2个

下载文件：[leetcode_3378.ts](sandbox:///mnt/agents/output/leetcode_3378.ts)