在学校刷洛谷的时候看到“P1621 集合”这个题名很容易下意识把它和编程语言里的集合类型联系在一起。真正读完题面才会发现完全不是那么回事它把所有区间里带有“不小于p的公共质因数”的数字强行合并成一个大组最后统计还有几个独立集合。这道题是学完并查集之后非常值得一刷的练手题尤其适合正在补充数据结构基础、准备比赛或者考研机试的读者。它的价值不在于知识点本身有多深而在于你必须自己从“数论关系”里看出“图的连通关系”这种建模能力比多背几个模板重要得多。下面我把这道题的思路、代码、边界坑位一次说清楚。1. P1621 到底在考什么先把题意翻译成人话1.1 题面拆解与等价转化题面并不长给定三个正整数a、b、p把区间[a,b]里的每个整数看成一个独立元素如果两个数的公共质因数中至少有一个不小于p就把这两个元素放进同一个集合。合并关系可以不断传递最后问一共有多少个集合。读题最爽的一刻是把“公共质因数”翻译成“连边条件”。比如a10、b20、p3时10和20都能被5整除12和15都能被3整除15和20又能同时被5整除于是从10这一条链上能一路连到20。如果把每个数字当成点把“共享某个不小于p的质因数”当成一条无向边那么这道题就变成了在给定的一张图里统计连通块数量。这个转化非常关键因为一旦脑内有图选择并查集就是顺理成章的事。很多同学初读时想用“枚举所有数对 求最大公约数 分解质因数”的方案思路本身没有错但复杂度会瞬间失控。区间长度只要到万级别两两配对的计算量就达到亿级完全不可行。所以必须观察合并规则的特殊之处所有连边关系都归根于质数而同一个质数的倍数天然构成一个“集团”。把图的边按质数这一层进行压缩复杂度一下子就落到了一个可接受的范围。1.2 为什么立刻想到并查集并查集常被称为DSUDisjoint Set Union标签一般是“动态维护若干不相交集合”或“快速判断两点是否连通”。本题最终要统计不相交集合的数量和并查集的语义天然对齐。用BFS或者DFS先建图再统计也能做但需要显式构造邻接表内存和处理逻辑都更重并查集只需要一个father数组边来一条就merge一次不需要把图真正存下来。还有一个容易被忽略的点并查集是在线算法。合并过程中不需要提前知道整张图的样子来一条边处理一条边非常适合本题“按质数批量生成边”的写法。路径压缩、按秩合并这两个优化听起来普通但在这里作用非常明显——同一个质数生成的边可能很多如果路径压缩没做最坏情况会把查询复杂度推上去做了压缩之后单次查找接近常数级别整体跑起来会轻松很多。2. 算法选型筛法 并查集两个经典工具一次合体2.1 为什么只需要处理质数“公共质因数”是破题的核心。如果两个数存在一个不小于p的公共因数d而d本身是合数那么这个d一定可以分解出某个质因子qq同样不小于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; vectorbool 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 边界a1、p2 这类看似简单的数据a1时区间从1开始。1不是任何质数的倍数所以它永远是独立集合不会参与任何合并。这个情况并不影响算法因为枚举质数q时向上取整得到的first最小也会是2不会把1错误并进去。但如果代码里的father数组从0开始初始化或者不小心对0执行了合并答案就会出现莫名偏移。p2是另一个常见起点。p取2时所有偶数都能共享质因数2因此会形成巨大的连通块。这里有个容易犯迷糊的点筛质数时循环只需要到b的平方根但合并倍数时却必须从p循环到b两者循环范围完全不同。如果把合并也塞进筛法内部等于用平方根范围覆盖合并必然遗漏大量质数。4.2 合并错位first 不是 a 的倍数当a10、q3时(a q - 1) / q * q的结果是12这是区间内3的第一个倍数没有问题。但如果误写成a / q * q得到的是9已经小于a循环里若从9开始加q就会错误合并到区间外的数导致结果不可控。C整数除法是向下取整向上取整必须用带偏移的写法或者提前判断a % q 0再特殊处理。还有一个细节first这个基准点不要随意更改。例如先把first和firstq合并再把firstq和first2q合并效果是一样的但如果把first设成区间外的某个数后面的合并就可能带出区间外元素。最稳妥的做法是始终用区间内第一个倍数作为“代表点”把所有后续倍数都合并到它身上。4.3 计数混乱集合数到底该减几次题目要求的最终集合数量等价于一开始的独立元素总数减去有效合并次数。每成功合并两个原本不连通的点集合数就减1如果两点已经连通merge返回false时集合数不能动。初学者经常把“合并发生次数”和“需要连的边数”混在一起最后答案差一两个。最稳妥的验证方式是先用小样例a10,b20,p3手动算一遍确认答案是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时跳出循环因为后面的质数只会更大区间内更不可能有倍数。这里整理一个常见问题速查表方便下次直接对照症状可能原因处理方式答案偏大合并时first算错或者漏处理某些质数重新检查first的计算确认质数枚举范围到b为止答案偏小把区间外数字也并了进来检查a和first的大小关系保证基准点落在区间内大数据超时筛法起点写错或者没有跳过first b把标记起点改为q*q并尽早结束空转合并随机wafather数组只初始化到b没从a开始初始化fa[i]ii从a循环到b5. 延伸由这道题想到的“集合”知识串联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刷透之后建议再找几道并查集相关的综合题练习比如带权并查集、离线处理区间合并的题目你会发现自己对连通性问题的敏感度提升得很明显。