以下是 LeetCode 3378. 统计最小公倍数图中的连通块数目 的 Rust 实现（已包含 LeetCode 提交格式）：

解题思路

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

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 的数通过并查集找根节点，统计不同根的数量。

Rust 代码（LeetCode 提交格式）

```rust
use std::collections::HashSet;

struct DSU {
    parent: Vec<usize>,
    rank: Vec<usize>,
}

impl DSU {
    fn new(n: usize) -> Self {
        let mut parent = vec![0; n + 1];
        let mut rank = vec![0; n + 1];
        for i in 0..=n {
            parent[i] = i;
        }
        DSU { parent, rank }
    }

    /// 查找根节点，带路径压缩
    fn find(&mut self, x: usize) -> usize {
        if self.parent[x] != x {
            self.parent[x] = self.find(self.parent[x]);
        }
        self.parent[x]
    }

    /// 合并两个集合，按秩合并
    fn union(&mut self, u: usize, v: usize) {
        let mut u_root = self.find(u);
        let mut v_root = self.find(v);
        if u_root == v_root {
            return;
        }
        // 按秩合并：将秩较小的树合并到秩较大的树下
        if self.rank[u_root] < self.rank[v_root] {
            std::mem::swap(&mut u_root, &mut v_root);
        }
        self.parent[v_root] = u_root;
        if self.rank[u_root] == self.rank[v_root] {
            self.rank[u_root] += 1;
        }
    }
}

impl Solution {
    pub fn count_components(nums: Vec<i32>, threshold: i32) -> i32 {
        let threshold = threshold as usize;
        let mut dsu = DSU::new(threshold);

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

        // 统计连通块数量
        let mut unique_parents = HashSet::new();
        for &num in &nums {
            let num = num as usize;
            if num > threshold {
                // 大于 threshold 的数各自独立成一个连通块
                unique_parents.insert(num);
            } else {
                unique_parents.insert(dsu.find(num));
            }
        }

        unique_parents.len() as i32
    }
}
```

复杂度分析

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

示例验证

- 示例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.rs](sandbox:///mnt/agents/output/leetcode_3378.rs)