科学计算【免费下载链接】codeforces-go算法竞赛模板库 by 灵茶山艾府 项目地址https://gitcode.com/GitHub_Trending/co/codeforces-go点击查看免费下载本文围绕力扣双周赛 145 的 Q4count-connected-components-in-lcm-graph展开深入讲解把 LCM 条件改写为 GCD 条件、再枚举 GCD 并用并查集合并的完整解题链从朴素枚举为何超时到只取最小的 g 倍数作为锚点 x这一关键优化再到正确性论证、复杂度分析以及 Python / Java / C / Go 五份可直接运行的完整代码。文中还会对照本仓库codeforces-go中该题的 Go 实现 与其测试用例并延伸到并查集模板库中 GCD/LCM 相关题目的解题家族。读完本文你将掌握枚举约数 并查集这一在数论类图连通题中高频出现的优化范式。题目与问题建模本题是力扣双周赛 145 的压轴题函数签名为func countComponents(nums []int, threshold int) int从仓库测试文件 d_test.go 中记录的题目地址可以看出其题意是给定数组nums与阈值threshold在数组下标之间建图——当下标i、j满足LCM(nums[i], nums[j]) threshold时存在一条边要求统计图中的连通分量个数。题目额外保证所有元素互不相同这是后文用值直接映射下标的前提。仓库样例数据 d.txt 给出了两组用例可以当作手算验证输入threshold输出手算验证[2,4,8,3,9]54仅LCM(2,4)4≤5连边连通块为{2,4}、{8}、{3}、{9}[2,4,8,3,9,12]1022,4,8,3,9全部连通12孤立恰好 2 个连通块核心思路把 LCM 条件改写为 GCD 条件下文将threshold简记为t。利用恒等式LCM(x, y) x·y / GCD(x, y)原条件LCM(x, y) ≤ t等价于x·y / GCD(x, y) ≤ t设g GCD(x, y)则原问题转化为找出所有满足x·y ≤ g·t的整数对(x, y)。核心思路枚举g 1, 2, 3, ..., t以及g的倍数x和y对满足x·y ≤ g·t的x、y把它们在nums中对应的下标用并查集连接起来。由于题目保证元素互不相同一个值唯一对应一个下标因此可以直接以值为键建立下标映射再以下标为并查集节点。关键优化朴素枚举会超时只需枚举最小的 g 的倍数直接按上述思路实现会遇到性能瓶颈g的倍数有O(t/g)个枚举x和y需要O((t/g)²)的时间累加起来完全不可接受。解决办法对每个g不需要枚举所有x。只需找到在nums中最小的g的倍数作为x若不存在则直接跳过该g然后再枚举其他g的倍数y——只要某个y能与这个x连起来那么这些y就已经被并进同一个连通块了。为什么选择最小的x因为y的可行范围是x·y ≤ g·t即y ≤ g·t / x。x越小满足条件的y就越多一次枚举就能把尽量多的y合并进来避免对每个x重复扫描。由此对每个g的枚举代价从O((t/g)²)降为一次找最小倍数 一轮扫描倍数y整体由调和级数控制在O(t·log t)量级详见复杂度分析。另一个值得注意的实现细节因为x ≥ gx是g的倍数所以y的上界g·t/x ≤ t恒成立——枚举y永远不会越过threshold。因此 Python 实现中的循环条件可以只写g * threshold // x 1而不必再判y thresholdGo 实现里额外加上的y threshold判断是冗余但无害的防御性写法。正确性论证g 不必恰好等于 GCD(x, y)答疑如果枚举的过程中出现g 2, x 4, y 8的情况怎么办此时GCD(4, 8) 4 ≠ g 2连边依据并不严格。回答虽然GCD对不上但不影响正确性。因为x和y都是g的倍数所以g | GCD(x, y)即GCD(x, y) ≥ g。此时若x·y/g ≤ t成立则必有x·y / GCD(x, y) ≤ x·y / g ≤ t即LCM(x, y) ≤ t也必然成立。这说明放宽标准的合并只会把真实存在边的对合并起来绝不会把本不该连通的点误连同时对每个g从 1 枚举到t任何真实连边对应的g GCD(x, y)都会被覆盖到。安全不漏连、不乱连加上完备真实边必然被枚举到保证了算法整体正确。多语言实现以下五种实现Python 哈希表版、Python 数组版、Java、C、Go均来自题解文档可直接提交。核心逻辑一致哈希表/数组记录值 → 下标外层枚举g内层先找最小倍数x再枚举y并合并。class Solution: def countComponents(self, nums: List[int], threshold: int) - int: n len(nums) fa list(range(n)) # 非递归并查集 def find(x: int) - int: rt x while fa[rt] ! rt: rt fa[rt] while fa[x] ! rt: fa[x], x rt, fa[x] return rt # 记录每个数的下标 idx {x: i for i, x in enumerate(nums)} for g in range(1, threshold 1): fi -1 for x in range(g, threshold 1, g): if x in idx: fi find(idx[x]) break if fi 0: continue for y in range(x g, g * threshold // x 1, g): if y in idx: fj find(idx[y]) if fj ! fi: fa[fj] fi # 合并 idx[x] 和 idx[y] n - 1 # 连通块个数减一 return nclass Solution: def countComponents(self, nums: List[int], threshold: int) - int: n len(nums) fa list(range(n)) # 非递归并查集 def find(x: int) - int: rt x while fa[rt] ! rt: rt fa[rt] while fa[x] ! rt: fa[x], x rt, fa[x] return rt # 记录每个数的下标 idx [-1] * (threshold 1) for i, x in enumerate(nums): if x threshold: idx[x] i for g in range(1, threshold 1): fi -1 for x in range(g, threshold 1, g): if idx[x] 0: fi find(idx[x]) break if fi 0: continue for y in range(x g, g * threshold // x 1, g): if idx[y] 0: fj find(idx[y]) if fj ! fi: fa[fj] fi # 合并 idx[x] 和 idx[y] n - 1 # 连通块个数减一 return nclass Solution { public int countComponents(int[] nums, int threshold) { int n nums.length; // 初始化并查集 int[] fa new int[n]; for (int i 0; i n; i) { fa[i] i; } // 记录每个数的下标 int[] idx new int[threshold 1]; Arrays.fill(idx, -1); for (int i 0; i n; i) { if (nums[i] threshold) { idx[nums[i]] i; } } for (int g 1; g threshold; g) { int minX -1; for (int x g; x threshold; x g) { if (idx[x] 0) { minX x; break; } } if (minX 0) { continue; } int fi find(fa, idx[minX]); int upper (int) ((long) g * threshold / minX); for (int y minX g; y upper; y g) { if (idx[y] 0) { int fj find(fa, idx[y]); if (fj ! fi) { fa[fj] fi; // 合并 idx[x] 和 idx[y] n--; // 连通块个数减一 } } } } return n; } private int find(int[] fa, int x) { if (fa[x] ! x) { fa[x] find(fa, fa[x]); } return fa[x]; } }class Solution { public: int countComponents(vectorint nums, int threshold) { int n nums.size(); vectorint fa(n); iota(fa.begin(), fa.end(), 0); // 非递归并查集 auto find - int { int rt x; while (fa[rt] ! rt) { rt fa[rt]; } while (fa[x] ! rt) { int tmp fa[x]; fa[x] rt; x tmp; } return rt; }; // 记录每个数的下标 vectorint idx(threshold 1, -1); for (int i 0; i n; i) { if (nums[i] threshold) { idx[nums[i]] i; } } for (int g 1; g threshold; g) { int min_x -1; for (int x g; x threshold; x g) { if (idx[x] 0) { min_x x; break; } } if (min_x 0) { continue; } int fi find(idx[min_x]); int upper (long long) g * threshold / min_x; for (int y min_x g; y upper; y g) { if (idx[y] 0) { int fj find(idx[y]); if (fj ! fi) { fa[fj] fi; // 合并 idx[x] 和 idx[y] n--; // 连通块个数减一 } } } } return n; } };func countComponents(nums []int, threshold int) int { n : len(nums) fa : make([]int, n) for i : range fa { fa[i] i } // 非递归并查集 find : func(x int) int { rt : x for fa[rt] ! rt { rt fa[rt] } for fa[x] ! rt { fa[x], x rt, fa[x] } return rt } // 记录每个数的下标 idx : make([]int, threshold1) for i, x : range nums { if x threshold { idx[x] i 1 // 这里 1 了下面减掉 } } for g : 1; g threshold; g { minX : -1 for x : g; x threshold; x g { if idx[x] 0 { // idx[x] 0 表示不存在 minX x break } } if minX 0 { continue } fi : find(idx[minX] - 1) for y : minX g; y threshold y g*threshold/minX; y g { if idx[y] 0 { fj : find(idx[y] - 1) if fj ! fi { fa[fj] fi // 合并 idx[x] 和 idx[y] n-- // 连通块个数减一 } } } } return n }实现细节对照下标映射的两种形态Python 哈希表版把nums中所有元素含大于threshold的孤立元素都放进idxPython 数组版、Java、C 与 Go 版只记录x threshold的元素因为任何大于t的元素其 LCM 必然大于t永远孤立无需参与合并。Go 版的1/-1技巧Go 切片默认值为 0而数组下标从 0 开始直接存i无法区分值为 0 的元素与不存在。仓库实现 d.go 存i 1用idx[x] 0判定存在用find(idx[minX] - 1)还原真实下标即注释所写的这里 1 了下面减掉。并查集写法Python/C/Go 均采用非递归两趟find先找根rt再回头把路径上节点直接指向rt避免递归爆栈同时完成路径压缩。复杂度分析时间复杂度O(n α·t·log t)其中n是nums的长度t是thresholdα是并查集单次合并的均摊复杂度近乎常数。由调和级数可知二重循环不计并查集的总次数为Σ(g1..t) t/g O(t·log t)。空间复杂度O(n)哈希表版或O(n t)数组版取决于实现。仓库实战本地 Go 实现与测试验证该题在仓库中对应的完整文件位于 leetcode/biweekly/145/d/ 目录下包括d.go与上文 Go 题解完全一致的实现函数countComponents(nums []int, threshold int) intd.txt由样例输入/输出构成的测试数据文件每组用例格式为数组 → threshold → 期望答案d_test.go测试入口调用仓库自研测试框架testutil.RunLeetCodeFuncWithFile逐行读取d.txt并与函数返回值比对。本地验证方式在仓库根目录执行go test ./leetcode/biweekly/145/d/即可跑通上述两组样例。这种xxx.go xxx.txt xxx_test.go三位一体的组织方式是本仓库所有力扣题目的标准形态测试文件头部的// Generated by copypasta/template/leetcode/generator_test.go注释表明这些测试用例与题解骨架可由 generator_test.go 中的TestWeekly/TestBiweekly自动生成方便在每场周赛/双周赛结束后快速补齐代码与用例。从题解到模板库并查集的 GCD/LCM 应用图谱本题的枚举g 并查集并非孤立技巧。在仓库的并查集模板中作者为并查集维护了覆盖数百道题目的题单注释其中质因子并查集 GCD1 并查集一节恰好构成本题的姊妹家族核心套路预处理每个数的质因子用pre[p]记录质因子p上一次出现的下标然后merge(i, pre[p])——通过质因子把GCD 关系转化为下标连通同类题目包括2709. 最大公约数遍历2172 分、1627. 带阈值的图连通性2221 分与本题关系最近、952. 按公因数计算最大组件大小2272 分、1998. 数组的最大公因数排序2429 分等模板注释中均有收录。从源码结构可以推断本题属于该模板库GCD/LCM 连通类问题的另一条实现路线本题用枚举约数 锚点最小倍数避免质因子分解而质因子并查集则用分解质因子 挂链合并把复杂度压到近乎线性。两者互为补充遇到按约数/质因子连通的题目时可以按数据范围灵活选择。相似题目与延伸练习1627. 带阈值的图连通性2221 分本题最直接的姊妹题同为LCM ≤ t / GCD 与阈值模型可对照学习仓库并查集模板注释中还收录了2709 / 952 / 1998等 GCD/LCM 连通类题目以及LC2459并查集 置换、LC3235对偶图等进阶应用题解文档还将其归入常用数据结构前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树分类题单适合作为练习并查集与其他常用数据结构时的索引。掌握等式变形 → 枚举关键量 → 用并查集合并三步走的思路后再遇到LCM、GCD、质因子等数论条件驱动的图连通计数问题就可以快速定位到这套枚举 并查集框架上并直接套用仓库模板库中现成的并查集实现。赞分享科学计算【免费下载链接】codeforces-go算法竞赛模板库 by 灵茶山艾府 项目地址https://gitcode.com/GitHub_Trending/co/codeforces-go点击查看免费下载相关推荐力扣双周赛 134 题解交替组计数、贪心取点与 AND 值为 k 的子数组枚举codeforces-go 仓库配套实现力扣双周赛 134 题解交替组计数、贪心取点与 AND 值为 k 的子数组枚举codeforces go 仓库配套实现 本篇文章以 leetcode/bi科学计算codeforces-go 仓库实战力扣双周赛 104「英雄的力量」贡献法递推题解全解析codeforces go 仓库实战力扣双周赛 104「英雄的力量」贡献法递推题解全解析 导读 本篇技术指南以仓库中 双周赛 104 第四题题解 https:科学计算如何从 knip、jscpd 一键迁移到 Fallow:fallow migrate 配置转换完整指南如何从 knip、jscpd 一键迁移到 Fallow:fallow migrate 配置转换完整指南 Fallow 是一款面向 TypeScript 和 Ja科学计算上一篇免费Steam游戏解锁神器Onekey一键解锁完整教程下一篇StreamFX插件完全指南7个专业级特效让你的OBS直播画面瞬间升级创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考