P1621集合题解：埃氏筛与并查集合并公共质因数

在学校刷洛谷的时候，看到“P1621 集合”这个题名，很容易下意识把它和编程语言里的集合类型联系在一起。真正读完题面才会发现完全不是那么回事：它把所有区间里带有“不小于p的公共质因数”的数字强行合并成一个大组，最后统计还有几个独立集合。这道题是学完并查集之后非常值得一刷的练手题，尤其适合正在补充数据结构基础、准备比赛或者考研机试的读者。它的价值不在于知识点本身有多深，而在于你必须自己从“数论关系”里看出“图的连通关系”，这种建模能力比多背几个模板重要得多。下面我把这道题的思路、代码、边界坑位一次说清楚。

1. P1621 到底在考什么：先把题意翻译成人话

1.1 题面拆解与等价转化

题面并不长：给定三个正整数a、b、p，把区间[a,b]里的每个整数看成一个独立元素；如果两个数的公共质因数中至少有一个不小于p，就把这两个元素放进同一个集合。合并关系可以不断传递，最后问一共有多少个集合。

读题最爽的一刻是把“公共质因数”翻译成“连边条件”。比如a=10、b=20、p=3时，10和20都能被5整除，12和15都能被3整除，15和20又能同时被5整除，于是从10这一条链上能一路连到20。如果把每个数字当成点，把“共享某个不小于p的质因数”当成一条无向边，那么这道题就变成了：在给定的一张图里统计连通块数量。这个转化非常关键，因为一旦脑内有图，选择并查集就是顺理成章的事。

很多同学初读时想用“枚举所有数对 + 求最大公约数 + 分解质因数”的方案，思路本身没有错，但复杂度会瞬间失控。区间长度只要到万级别，两两配对的计算量就达到亿级，完全不可行。所以必须观察合并规则的特殊之处：所有连边关系都归根于质数，而同一个质数的倍数天然构成一个“集团”。把图的边按质数这一层进行压缩，复杂度一下子就落到了一个可接受的范围。

1.2 为什么立刻想到并查集

并查集常被称为DSU（Disjoint Set Union），标签一般是“动态维护若干不相交集合”或“快速判断两点是否连通”。本题最终要统计不相交集合的数量，和并查集的语义天然对齐。用BFS或者DFS先建图再统计也能做，但需要显式构造邻接表，内存和处理逻辑都更重；并查集只需要一个father数组，边来一条就merge一次，不需要把图真正存下来。

还有一个容易被忽略的点：并查集是在线算法。合并过程中不需要提前知道整张图的样子，来一条边处理一条边，非常适合本题“按质数批量生成边”的写法。路径压缩、按秩合并这两个优化听起来普通，但在这里作用非常明显——同一个质数生成的边可能很多，如果路径压缩没做，最坏情况会把查询复杂度推上去；做了压缩之后，单次查找接近常数级别，整体跑起来会轻松很多。

2. 算法选型：筛法 + 并查集，两个经典工具一次合体

2.1 为什么只需要处理质数

“公共质因数”是破题的核心。如果两个数存在一个不小于p的公共因数d，而d本身是合数，那么这个d一定可以分解出某个质因子q，q同样不小于p，并且q也是两个数的公共质因数。也就是说，所有需要建立的关系都可以收窄到质数上：只要对每个不小于p的质数q，把区间内所有能被q整除的数合并到一起，就能覆盖全部有效连边。

这段逻辑是整道题正确性的地基。有人会问：直接用合数合并不是更省事吗？实际上，如果一个更大的合数因子存在，它的质因子已经在更小的质数处被处理过，再用合数处理只会产生冗余合并，不会带来任何新信息。反过来，只用质数作为合并代理，也不会漏掉任何必要的连接关系。因此，枚举质数是准确且高效的选择。

2.2 埃氏筛在本题承担的任务

既然要枚举质数，自然可以选择欧拉筛或埃氏筛。我推荐埃氏筛，因为它代码短、思路直观，对本题的规模非常够用。筛法从2循环到b，对每个质数q，从q的平方开始把后面的倍数标记为合数，整体复杂度是O(b log log b)。b通常开到10^5甚至10^6，在现代评测机上都是毫秒级。

筛法和并查集合并可以安排在同一轮循环里，但顺序一定不能乱：必须先标记合数，再判断q作为质数是否满足不小于p，然后进行倍数合并。如果把筛合数的循环放在合并倍数之后，某些小于q平方的合数还没有被标记，你在同轮里判断isPrime时会得到错误信息。我自己的习惯是分成两个循环：第一个循环完整计算质数表，第二个循环单独做合并。这样内存只多一个布尔数组，但逻辑干净很多，不容易把自己绕晕。

2.3 合并过程与复杂度估算

对于每个符合条件的质数q，区间[a,b]内它的倍数个数大约是⌊b/q⌋ - ⌈a/q⌉ + 1。把所有质数的这个数量加起来，总合并次数大约等于b乘以所有不大于b的质数倒数之和，这个数在数论里约等于b log log b。因此，算法总复杂度可以写成O(b log log b)，并查集那部分由于路径压缩的存在，可以近似看成常数。这个复杂度在常见数据范围下非常稳定。

这里有一个性能细节值得注意：对于某个质数q，区间内第一个倍数的计算要写成first = ((a + q - 1) / q) * q，不要用浮点数，也不要在循环里从a开始逐个试探。只要第一个倍数算对，后面每次加q就能覆盖所有合法倍数。如果first已经大于b，说明当前q在区间里没有倍数，可以直接跳过；当q持续增大到超过b时，整个循环也可以提前结束。

3. 完整实现：我提交的C++代码和Python对照

3.1 C++主流程

直接上代码，我写的是最容易理解的版本，没有刻意做极端优化，但在常规数据范围内表现足够稳定：

#include <bits/stdc++.h> using namespace std; const int MAXN = 1000005; int fa[MAXN]; int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); } bool merge(int x, int y) { int rx = find(x), ry = find(y); if (rx == ry) return false; fa[rx] = ry; return true; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int a, b, p; cin >> a >> b >> p; if (p > b) { cout << b - a + 1 << "\n"; return 0; } for (int i = a; i <= b; i++) fa[i] = i; vector<bool> isPrime(b + 1, true); if (b >= 0) isPrime[0] = false; if (b >= 1) isPrime[1] = false; for (long long q = 2; q * q <= b; q++) { if (!isPrime[q]) continue; for (long long j = q * q; j <= b; j += q) { isPrime[j] = false; } } int setCnt = b - a + 1; for (int q = p; q <= b; q++) { if (!isPrime[q]) continue; int first = ((a + q - 1) / q) * q; if (first > b) continue; for (int x = first + q; x <= b; x += q) { if (merge(first, x)) setCnt--; } } cout << setCnt << "\n"; return 0; }

几个地方说明一下：find用递归写路径压缩，最容易理解；如果担心递归深度，可以改成迭代版，逻辑完全一样。merge返回是否真的发生了合并，这样可以在合并的同时更新集合计数，最后直接输出setCnt，省得再遍历一遍统计根节点。first一定落在[a,b]内，因为对a做了向上取整，并且提前检查了first > b才跳过，不会出现越界风险。

3.2 Python 写法对照

Python版的思路完全相同，只是筛法部分会慢一些，建议把b压在10^5到10^6这个量级使用。如果是自己练习，这个限制完全够用；如果评测数据更大，建议换PyPy或者直接用C++。代码如下：

import sys def solve(): data = sys.stdin.read().split() a, b, p = map(int, data[:3]) if p > b: print(b - a + 1) return fa = list(range(b + 1)) def find(x): while fa[x] != x: fa[x] = fa[fa[x]] x = fa[x] return x def merge(x, y): rx, ry = find(x), find(y) if rx == ry: return False fa[rx] = ry return True is_prime = [True] * (b + 1) if b >= 0: is_prime[0] = False if b >= 1: is_prime[1] = False for q in range(2, int(b ** 0.5) + 1): if is_prime[q]: for j in range(q * q, b + 1, q): is_prime[j] = False ans = b - a + 1 for q in range(p, b + 1): if not is_prime[q]: continue first = (a + q - 1) // q * q if first > b: continue for x in range(first + q, b + 1, q): if merge(first, x): ans -= 1 print(ans) if __name__ == "__main__": solve()

Python版和C++版主要有两个差异：find改成了递推写法，避免递归带来的潜在开销；输入一次性用read().split()读取，减少了反复调用input的损耗。其余步骤完全一致，也正因如此，Python版特别适合用来对照学习逻辑，本地跑几个小样例就知道自己想不想得通。

3.3 提交前自查清单

每次提交前，我都会快速过一遍下面的检查点：

• 输入的三个整数顺序是不是a、b、p，有没有把p当成了区间上限。
• father数组的初始化区间是[a,b]，而不是[1,b]，否则会多出很多孤立点。
• 筛法里标记合数的起点是q的平方，不是2q，否则会有大量重复标记。
• 合并倍数时起点用向上取整的first，不能简单从a出发。
• 初始集合数量是b - a + 1，每次真实合并才减一，冗余合并不减。
• 当p大于b时，区间内不会发生任何有效合并，直接输出b - a + 1。

这些点看起来都很基础，但它们正是很多人交了三四发才过的原因。尤其是最后一条，很多题解不会单独提，但自己第一次做题时很容易漏判。

4. 常见问题与排查技巧实录

4.1 边界：a=1、p=2 这类看似简单的数据

a=1时，区间从1开始。1不是任何质数的倍数，所以它永远是独立集合，不会参与任何合并。这个情况并不影响算法，因为枚举质数q时，向上取整得到的first最小也会是2，不会把1错误并进去。但如果代码里的father数组从0开始初始化，或者不小心对0执行了合并，答案就会出现莫名偏移。

p=2是另一个常见起点。p取2时，所有偶数都能共享质因数2，因此会形成巨大的连通块。这里有个容易犯迷糊的点：筛质数时循环只需要到b的平方根，但合并倍数时却必须从p循环到b，两者循环范围完全不同。如果把合并也塞进筛法内部，等于用平方根范围覆盖合并，必然遗漏大量质数。

4.2 合并错位：first 不是 a 的倍数

当a=10、q=3时，(a + q - 1) / q * q的结果是12，这是区间内3的第一个倍数，没有问题。但如果误写成a / q * q，得到的是9，已经小于a；循环里若从9开始加q，就会错误合并到区间外的数，导致结果不可控。C++整数除法是向下取整，向上取整必须用带偏移的写法，或者提前判断a % q == 0再特殊处理。

还有一个细节：first这个基准点不要随意更改。例如先把first和first+q合并，再把first+q和first+2q合并，效果是一样的；但如果把first设成区间外的某个数，后面的合并就可能带出区间外元素。最稳妥的做法是始终用区间内第一个倍数作为“代表点”，把所有后续倍数都合并到它身上。

4.3 计数混乱：集合数到底该减几次

题目要求的最终集合数量，等价于一开始的独立元素总数减去有效合并次数。每成功合并两个原本不连通的点，集合数就减1；如果两点已经连通，merge返回false时集合数不能动。初学者经常把“合并发生次数”和“需要连的边数”混在一起，最后答案差一两个。最稳妥的验证方式是先用小样例a=10,b=20,p=3手动算一遍，确认答案是7，再拿代码去对。

如果不想依赖递减计数，也可以在所有合并完成后，遍历区间[a,b]，统计满足find(i) == i的点个数。两种写法都正确，递减法省一次遍历，统计法更直观，特别适合调试阶段用来核对结果。

4.4 性能优化：这题最容易被卡在哪

最容易被卡的点其实是筛法本身。如果从每个数开始把所有倍数全部标记成合数，而且不用q的平方作为起点，复杂度会从O(b log log b)退化成O(b log b)，在小数据下不明显，一旦b到10^6就可能超时。另外，输入输出也很关键，C++用cin/cout记得关同步，Python用缓冲读取，这些都能省下不少时间。

另一个隐蔽性能点是空间和循环的取舍。当q逐渐增大时，first很快会大于b，如果不在循环里检查first > b就进入内层循环，很多大质数阶段就是在空转。虽然单次空转是O(1)，但叠加起来依然会拖慢程序。遇到这种情况，可以直接在first > b时跳出循环，因为后面的质数只会更大，区间内更不可能有倍数。

这里整理一个常见问题速查表，方便下次直接对照：

5. 延伸：由这道题想到的“集合”知识串联

5.1 数学集合与并查集集合

P1621里的“集合”，本质上是数学意义上的等价类。合并关系满足自反、对称、传递，最后划分出的集合两两不相交。这和高中数学里“集合”的概念完全一致，只是实现方式变成了并查集。我第一次做完这题最大的收获，是把“集合”这个词从语言层面的模糊理解，拉到了可计算的数据结构层面，后面再遇到“等价关系”“划分”这些词，就不再觉得抽象了。

5.2 Python/Java 里的集合世界

做完P1621再回头看各种语言里的集合，会更有层次感。Python的set擅长去重和快速查找，提供add、remove、union、intersection等接口，还有集合推导式这种一行生成集合的写法：{x * 2 for x in range(10) if x % 2 == 0}。Java的集合框架把List、Set、Map、Queue划分得清清楚楚，HashSet和TreeSet各有各的适用场景。需要留神的是，这些语言层面的集合更强调“元素唯一、顺序无关”，和并查集里“支持合并、查找根”的集合是两类需求，概念虽同名，含义完全不同。

5.3 向量数据库中的 Collection

近两年做应用开发的读者可能接触过Chroma这类向量数据库，往一个Collection里写入数据后，底层会自动拆出多张表来管理向量、元数据、文档和索引信息，它们通过内部主键互相关联，支撑语义检索。这个“集合”和P1621里的并查集集合相去甚远——一个是存储上的逻辑容器，一个是计算上的动态等价类。我觉得这种跨场景对比很有意思：同一个词在不同系统里被反复重载，真正判断它含义的是上下文。

5.4 这些知识如何反哺算法题

算法题刷多以后会发现，很多“集合”问题最终都在问连通性。相邻格子是连通，公共质因数是连通，社交网络里的好友关系也是连通。一旦建立起“问题背景五花八门，但底层都是并查集/BFS/DFS”的映射能力，解题速度会有质的提升。P1621正好提供了一个很好的训练素材：它把数论和并查集两个看似无关的领域焊接在一起，逼着你把隐藏关系提取成图，再交给成熟的数据结构去处理。

我做这道题的时候，第一版直接暴力枚举数对求gcd，数据一加大就原地爆炸；后来改成“筛出质数，再按质数合并”，才第一次体会到建模的价值。这里给刚入门的读者留一个笨办法：卡住不会做时，先拿小数据手动算一遍，把每一轮合并画成树，再回头对照代码，很多“这里为什么要这样写”的问题会立刻清晰。P1621刷透之后，建议再找几道并查集相关的综合题练习，比如带权并查集、离线处理区间合并的题目，你会发现自己对连通性问题的敏感度提升得很明显。