企业官网建设流程全解析

作为常年在洛谷刷题的选手，看到"集合"这道题，第一反应就是：这不就是典型的筛法 + 并查集组合拳吗？但真正动手写的时候，不少同学还是会在几个关键点上卡住。今天不聊虚的，直接拆解 P1621 的完整解题链路，从筛子选型到并查集合并，把每一步背后的逻辑讲透。这篇文章适合刚学完并查集、想用综合题练手的同学，也适合准备比赛想复盘基础算法的选手——我把踩过的坑、测试边界和优化思路全写出来，照着走一遍，你就能彻底吃透这道题。

1. 题目到底在问什么：合并规则的直觉化理解

先别急着上代码，把题意嚼碎了再动手，能帮你省下大量调试时间。

1.1 原题规则重述与抽象

题面给你一个区间 [a, b]，以及一个质数 p。你要反复做这样一个操作：如果区间内存在两个数 x 和 y，它们共同拥有一个不小于 p 的质因子，那么 x 和 y 就必须被划到同一个集合里。注意，这个合并可以传递——A 和 B 有公共质因子，B 和 C 有公共质因子，哪怕 A 和 C 直接看没有共同质因子，A、B、C 最终也属于同一集合。全部合并结束后，统计区间里还剩下多少个独立的集合。

规则的核心是"通过质因子建立连接关系"，不是两两比较数值大小，也不是看倍数关系。举个例子，区间 [10, 20]，p = 3：

• 10 = 2 × 5，不含 ≥3 的质因子，孤家寡人；
• 11 是质数，它自己 ≥3，但它只有一个倍数（自己），没有其他数和它共享 11 这个因子，所以它也是单个集合；
• 12 = 2² × 3，含质因子 3；
• 15 = 3 × 5，含质因子 3 和 5；
• 18 = 2 × 3²，含质因子 3；
• 14 = 2 × 7，含质因子 7；
• 同理 16、17、19 也各自独立。

于是 12、15、18 之间通过质因子 3 串在一起，14 和它自己在一起，如果区间里还有 21（21 = 3 × 7），那么 14 可以通过 7 和 21 相连，21 又通过 3 连到 12、15、18——最后整批全成一个集合。这就是传递性合并的威力。

1.2 为什么说它是"图论连通块"问题

你完全可以把每个数看成图上的一个节点。两个节点之间连边，当且仅当它们共享一个 ≥p 的质因子。那么题目的答案就是这张图的连通分量数量。而并查集天生就是维护"动态连通性"的数据结构，这就是为什么这道题会出现在并查集题单里。

但问题来了：如果直接暴力枚举区间内所有数对，判断它们是否有公共质因子，复杂度是 O(n²) 级别的。题目区间长度最大能到 50000，n² 就是 25 亿次操作，显然不可行。所以必须换个角度建边：不需要枚举数对，只需要枚举质因子，把同一个质因子的所有倍数合并到一起。区间内一个数最多有 log n 个不同质因子，通过筛法找出所有 ≥p 的质因子，再对每个质因子枚举它在区间内的倍数区间，这样总的合并次数接近调和级数，复杂度立刻降下来。

2. 筛法选型：埃氏筛和欧拉筛到底选哪个

所有合并的前提是"知道哪些数是质数"。这道题的数据范围是区间右端点 b ≤ 100000（实际以题目给定为准），非常温和，两种筛法都随便过。但我还是想把两种筛子的代码、区别、适用场景一次讲明白，因为你以后会遇到更变态的数据范围。

2.1 埃氏筛：思想简单，代码好写

埃氏筛的核心思想：从 2 开始，从小到大，如果当前数字没有被标记为合数，那它就是质数，然后把它的所有倍数标记为合数。代码非常直观：

const int MAXN = 100005; bool isPrime[MAXN]; void eratosthenes(int n) { memset(isPrime, true, sizeof(isPrime)); isPrime[0] = isPrime[1] = false; for (int i = 2; i * i <= n; i++) { if (isPrime[i]) { for (int j = i * i; j <= n; j += i) { isPrime[j] = false; } } } }

注意内层循环从i * i开始，而不是从i * 2开始。为什么？因为对于小于 i² 的 i 的倍数，比如 2i、3i、...、i(i-1)，它们一定已经被更小的质因子标记过了，从 i² 开始可以省掉大量重复标记。这是一个非常重要的小优化。

埃氏筛的时间复杂度是 O(n log log n)，看起来接近线性，但常数不小，因为一个合数可能被多个质因子重复标记。比如 12 会被 2 标记一次、3 又标记一次。

2.2 欧拉筛：每个合数只被最小质因子筛掉一次

欧拉筛（线性筛）的改进在于：保证每个合数只被它的最小质因子筛掉一次，思路是让每个合数只通过"最小质因子 × 最大因数"的方式被标记，用prime[]数组记录已经找到的质数列表：

int prime[MAXN]; bool isComposite[MAXN]; int cnt = 0; void eulerSieve(int n) { memset(isComposite, false, sizeof(isComposite)); cnt = 0; for (int i = 2; i <= n; i++) { if (!isComposite[i]) { prime[++cnt] = i; } for (int j = 1; j <= cnt && i * prime[j] <= n; j++) { isComposite[i * prime[j]] = true; if (i % prime[j] == 0) { break; } } } }

关键就在那行if (i % prime[j] == 0) break;。这行代码保证了：当prime[j]是 i 的因子时，更大的质数乘以 i 得到的结果，其最小质因子不再是prime[j]，应该留给后续更大的 i 去筛，所以必须 break 掉。如果不 break，同一个合数会被筛多次，欧拉筛就退化成埃氏筛了。

欧拉筛的时间复杂度严格 O(n)，空间上多一个prime[]数组。在 n 很大（比如 10⁷）时，欧拉筛的优势才明显；n = 10⁵ 这个量级，两者差距几乎感受不到。

2.3 这道题的选型建议

我的建议是：如果你还在练习阶段，优先掌握欧拉筛，因为它对"每个合数只被筛一次"这个逻辑的理解要求更高，能训练你处理边界条件的能力；如果比赛时心态紧张，写埃氏筛能少想很多细节，且以 P1621 的数据范围完全不会超时。我个人提交的版本用的是欧拉筛，原因后面会提——因为在合并阶段，我们需要按质数从小到大枚举，线性筛本身就会在结束之后留下一个有序的prime[]数组，可以直接拿来用，不用重新从 2 到 b 遍历一遍判断。

3. 建图与合并：并查集操作的核心推演

筛法解决了"区间内有哪些质数"的问题，接下来是这道题最核心的环节：如何通过质因子把数合并成集合。

3.1 为什么不能直接找公共质因子

我想先深入聊一下暴力思路为什么不行，这能帮你想清楚优化的本质。最笨的方法：两层循环枚举 x ∈ [a, b]，y ∈ [a, b]，对每一对 (x, y) 做质因数分解，检查是否有 ≥p 的相同质因子。复杂度是 O((b-a)² × 分解成本)，完全不能接受。

稍微聪明一点的想法：对每个数做质因数分解，然后建立一个"质因子 → 数字"的映射（比如用哈希表存：3 → {12, 15, 18}），然后把同一质因子对应的所有数字合并。这样每个数只需要分解一次，复杂度是 O(n log n) 级别，听起来已经很不错了。但问题是：对每个数做质因数分解需要试除，在 n = 10⁵ 时可以过，不过代码复杂一些，需要额外写分解函数。

最优雅的办法其实是反过来：不用对每个数分解质因数，而是从质数出发，直接在区间内枚举它的倍数。对于质数 prime[i]（prime[i] ≥ p），区间 [a, b] 内所有 prime[i] 的倍数，都共享 prime[i] 这个质因子，因此它们必须在同一集合内。你只需要从第一个大于等于 a 的倍数开始，每隔 prime[i] 个数合并一次，就完成了这个质因子对连通性的贡献。这比逐个数分解质因数更省事，而且思路和筛法天然衔接。

3.2 并查集模板与路径压缩细节

并查集本身很简单，但竞赛里为了常数最优，建议直接写递归 + 路径压缩：

int fa[MAXN]; int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); } void unionSet(int x, int y) { int fx = find(x), fy = find(y); if (fx != fy) { fa[fx] = fy; } }

路径压缩在find里顺手完成，fa[x] = find(fa[x])这行让 x 直接挂到根下面。在数据量不大的时候，按秩合并（rank 数组）可写可不写，因为 P1621 的合并次数最多也就十几万次，路径压缩足以保证接近 O(1) 的均摊复杂度。

3.3 合并过程的完整推演：从质数到倍数的双向映射

现在把完整合并流程走一遍。设区间 [a, b]，质数集合 primes 已经用筛法得到。算法伪代码如下：

初始化 fa[i] = i, 对 i in [a, b] for each 质数 prime_i in primes: if prime_i < p: continue first = ceil(a / prime_i) * prime_i if first == a 且 first % prime_i != 0: first += prime_i // 处理整除细节 for j = first; j <= b; j += prime_i: unionSet(first, j)

等等，ceil那里容易出错，我单独说明一下。要找到区间内 prime_i 的第一个倍数，最简单的方式是first = ((a + prime_i - 1) / prime_i) * prime_i，用整数运算实现向上取整。但要注意：如果a本身能被 prime_i 整除，(a + prime_i - 1) / prime_i得到的值比实际大 1，乘回去会跳过 a 本身。比如 a = 6, prime = 3，(6 + 2) / 3 = 2，2 * 3 = 6，刚好没问题；但 a = 7, prime = 3，(7 + 2) / 3 = 3，3 * 3 = 9，跳过了 7 附近实际上 7 不是 3 的倍数所以没跳错；真正危险的是 a = 8, prime = 4（但 prime 是质数，4 这种情况不存在）。所以质数场景下(a + prime - 1) / prime * prime是安全的。

更稳妥的写法是直接first = (a % prime == 0) ? a : a + (prime - a % prime);，一眼就能看懂。我推荐这种写法，避免公式背错。

合并时注意unionSet(first, j)，这里的意图是：first 是质数 prime_i 在区间内的第一个倍数，后面每个倍数 j 都与 first 合并。但本质是"同一质因子的所有倍数互相合并"，所以你也可以unionSet(last, j)，也就是让后一个和前一个合并，效果一样。第一种写法路径更扁平，find 更快，所以我代码里用unionSet(first, j)。

为了让你彻底理解合并的传递性，我用一个具体例子手推一遍：

区间 [20, 30]，p = 5。筛选出质数：5, 7, 11, 13, 17, 19, 23, 29。

• prime = 5：区间内 5 的倍数有 20, 25, 30。合并 20-25，20-30。此时 {20,25,30} 在一个集合。
• prime = 7：倍数有 21, 28。合并 21-28。
• prime = 11：倍数有 22。只有一个倍数，不需要合并（自己和自己 union 没有意义）。
• prime = 13：倍数有 26。同上。
• prime = 17：倍数有 17 自身（17 在区间内）。注意！17 是质数，它自己含质因子 17 ≥ 5，但只有一个倍数，属于"质数本身"形成的集合，这里不用合并。
• prime = 19：倍数 19，同上。
• prime = 23：倍数 23，同上。
• prime = 29：倍数 29，同上。

再看 24 = 2³ × 3，不含 ≥5 的质因子，它自己成一个集合；27 = 3³，同理；28 已经通过 7 和 21 合并；20、25、30 通过 5 合并。所以最终集合有：{20,25,30}、{21,28}、{22}、{23}、{24}、{26}、{27}、{29}，一共 8 个集合。你可以手算验证，和并查集统计结果完全一致。

3.4 复杂度分析：为什么并查集合并次数不会爆炸

每处理一个质数 prime_i，在区间内枚举倍数的次数大约是(b - a) / prime_i。对所有从 p 到 b 的质数求和：

sum_{prime ≥ p, prime ≤ b} (b - a) / prime ≈ (b - a) * sum_{prime ≤ b} 1/prime

其中所有不超过 b 的质数的倒数之和大约是 log log b + M（某常数），当 b = 10⁵ 时，log log 10⁵ ≈ 2.5 左右。也就是说，总合并次数大约是区间长度乘以一个很小的常数，远小于 n²。这就是为什么枚举倍数而非枚举数对能可行。埃氏筛本身 O(n log log n)，并查集均摊接近常数，整个算法在大约 O(n log log n) 的预处理 + O((b-a) × log log b) 的合并中完成。

4. 完整实现与常见坑位排雷

说了这么多原理，是时候给出一份完整可 AC 的参考代码了。我使用的是 C++ 版本，如果你的判题环境支持 C++17，下面这段可以直接交。

4.1 参考代码（欧拉筛 + 并查集）

#include <bits/stdc++.h> using namespace std; const int MAXN = 100005; int fa[MAXN]; int prime[MAXN]; bool isComposite[MAXN]; int primeCnt = 0; void eulerSieve(int n) { for (int i = 2; i <= n; i++) { if (!isComposite[i]) { prime[++primeCnt] = i; } for (int j = 1; j <= primeCnt && i * prime[j] <= n; j++) { isComposite[i * prime[j]] = true; if (i % prime[j] == 0) { break; } } } } int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); } void unionSet(int x, int y) { int fx = find(x), fy = find(y); if (fx != fy) { fa[fx] = fy; } } int main() { int a, b, p; cin >> a >> b >> p; eulerSieve(b); for (int i = a; i <= b; i++) { fa[i] = i; } for (int i = 1; i <= primeCnt && prime[i] <= b; i++) { int curPrime = prime[i]; if (curPrime < p) { continue; } int first; if (a % curPrime == 0) { first = a; } else { first = a + (curPrime - a % curPrime); } if (first > b) { continue; } for (int j = first; j <= b; j += curPrime) { unionSet(first, j); } } int ans = 0; for (int i = a; i <= b; i++) { if (find(i) == i) { ans++; } } cout << ans << endl; return 0; }

最后统计时用find(i) == i来判断一个节点是否是根节点，特别注意这里不能直接数fa[i] == i，因为路径压缩后fa[i]可能已经是根了，也可能没有来得及压缩。最稳定的方式是再调用一次find，既能统计又能顺手压缩。

4.2 坑位一：质数 p 本身的倍数从哪开始

如果你的区间 [a, b] 刚好包含 p 的倍数，比如 a = 10, b = 20, p = 5，那么 first = 10，程序会把 10、15、20 合并。但注意 5 本身不在区间内，它没有作为节点参与并查集，不过 10、15、20 共享质因子 5 完全没问题。反过来，如果 a = 5, b = 10, p = 5，first = 5，5 参与合并，把自己和 10 并在一起，正确。

有一个很多人会犯的错误：在合并时直接拿质数curPrime作为节点去 union，比如unionSet(curPrime, j)。如果质数 curPrime 不在区间 [a, b] 内，fa[curPrime] 根本没有初始化，结果是未定义行为，大概率 WA。所以一定要用区间内的第一个倍数作为合并锚点。我在代码里用first就是这个目的。

4.3 坑位二：只有一个倍数时不需要合并

当质数 curPrime 在区间内只有一个倍数，比如上面例子里的 17、19、23、29，first和j是同一个数，unionSet(first, first)虽然不会出错，但白白多一次 find 调用。还可以跳过。合并之前判断一下：

int second = first + curPrime; if (second <= b) { for (int j = second; j <= b; j += curPrime) { unionSet(first, j); } }

这样每个质数如果只贡献一个倍数，就不做无意义合并。对于题意来说，这些质数本身以及它们的唯一倍数，应该独立成集合，跳过合并不影响结果。

4.4 坑位三：区间内小于 p 的数怎么处理

区间内很可能存在小于 p 的数（比如 a = 1, p = 5）。这些数能和其他数共享的质因子只能小于等于它自身，而题目要求共享质因子必须 ≥p，因此这些数无法通过任何质因子和其他数合并，它们各自独立成集合。你不需要在代码里特别处理它们，只要初始化 fa[i] = i，然后它们永远不参与 union 操作，最后统计时会自然算作独立集合。

4.5 坑位四：如果 b 比较小但 p 比 b 还大

当 p > b 时，区间内根本不存在 ≥p 的质因子，因此每个数都独立成集合，答案就是 b - a + 1。我们的代码中，所有质数 curPrime < p 都会 continue，不会有任何合并操作，统计结果自然正确。有的同学会在这个边界 panic，其实完全不用，逻辑上已经涵盖了。

4.6 用对数数据验证你的算法

在提交之前，我建议你用几个小数据手工验证：

第三行写到的误区就是：别凭感觉猜小数据，拿代码跑一遍最稳。我当年就是在这题的小样例上翻过车，把 14 和 28 的合并想当然了，漏掉了区间范围对连通性的限制。

5. 算法对比与拓展思考：从这道题能延伸出什么

P1621 只是"筛法 + 并查集"的一个入门代表。理解透这道题之后，你完全可以把它扩展到更广的场景。

5.1 "区间倍数合并"模型还能解什么题

很多题目都有类似结构：给定区间或集合，通过某个属性建立等价关系，然后统计等价类数量。比如：

• 给定 n 个数，如果两个数最大公约数大于某个阈值，则合并，最后统计集合数量；
• 社交网络里，如果两个人有共同兴趣标签，则归入同一圈子，统计圈子数量；
• 字符串处理中，如果两个位置能被同一字符覆盖，则合并连通块。

这些问题的通用解法框架都是：找到建立边的"桥梁"（质因子、公约数、标签），把每个桥梁对应的元素合并。只要合并次数可控，并查集就是最优解。

5.2 质因数分解路线 vs 筛法倍数路线

我在前面提过，还可以对区间内每个数做质因数分解，然后合并相同质因子的数。这里补充对比一下：

当 b 很大（比如 10⁷）时，逐个数分解必然超时，筛法优势明显。而这道题 b ≤ 10⁵，两种都能过，但掌握筛法路线，对你未来处理更大的数据范围更有帮助。顺便一提，筛法不仅能筛质数，还能在筛的过程中顺便记录每个数的最小质因子，这样后续分解任意一个数的质因数只需要 O(log n) 时间，是数论题里的常用技巧。

5.3 并查集合并顺序对结果有影响吗

熟悉并查集的读者可能好奇：合并顺序是否影响答案？结论是不影响，因为并查集最终维护的是连通关系，只要所有需要合并的边都被合并过，无论先后顺序，最终连通分量划分唯一。这意味着你完全可以按质数从小到大的顺序枚举，或者从大到小，结果一致。但从小到大有个额外好处：小的质数通常合并次数较多，先合并可以让后续 find 的路径更短，常数上略有优化。

5.4 如果区间长度很大，还能怎么做

假设 b 达到 10⁷，区间长度 10⁵ 这种还好说；但如果区间长度也到 10⁷，合并次数接近 n log log n，用路径压缩 + 迭代式 find 可以勉强压进时限。递归 find 在深度较深时可能爆栈（虽然路径压缩后会好很多），你可以改写成迭代版本：

int find(int x) { while (fa[x] != x) { fa[x] = fa[fa[x]]; // 路径减半 x = fa[x]; } return x; }

这种"路径减半 + 路径压缩"混合写法在极端数据下更稳，省掉了递归开销。我建议你两版都练一练，比赛时根据情况选用。

6. 最后的建议与经验之谈

刷算法题最容易出现的状况是：看题解觉得好简单，合上屏幕自己写就卡壳。P1621 这道题特别适合检验"你是不是真的理解并查集合并的本质"——因为它的题眼不在并查集本身，而在于发现"质因子是连接点"这个抽象过程。

我的练习建议是：第一遍独立写出代码，哪怕超时或 WA 也没关系；第二遍对照本文的推演过程，重点检查你的first计算和只合并区间内节点这两个细节；第三遍尝试用埃氏筛和欧拉筛各写一版，对比代码长度和常数差异。三遍下来，你对"筛法 + 并查集"这个组合的敏感度会有质的提升。

我最初做这题时，卡在质数 curPrime 不一定落在区间内这件事上，直接拿 curPrime 当合并锚点，结果样例怎么都过不了。后来把"锚点必须是区间内的第一个倍数"这个条件刻进脑子里，同类题目就再也没犯过类似错误。希望这篇文章也能帮你少走一段弯路，把这道经典题稳稳拿下。

如果你还想继续深挖，可以去试试"并查集 + DFS/BFS"结合质因子建图的题目，或者把区间改成"前 n 个正整数"再问连通块数。祝刷题顺利，AC 常伴。