布克波波

分类

题解(4)

/ 注册

全部文章（共1篇）

题解 | #小竹与妈妈#

用埃氏筛O(nlog(logn))求得1~5e6每个数的质因数个数,用并查集来维护连通块的大小，合并时判断两个数的最大公约数是否含有两个以上的质因数，如果是则合并，最后遍历所有位置，输出最大连通块大小即可。维护连通块不难，建图用dfs搜索也可以实现。困难的是想到可以用gcd的约数个数判断是否优雅，和...

C++ 数学深度优先搜索并查集

2022-11-28

0 443