图论

P5881

设对于每个数\(i\)的整数因式部分为\(h(i)\),则\(gcsd(x,y)=h(gcd(x,y))^2=gcd(h(x),h(y))^2\)

原问题是对于所有\(gcsd(x,y)>x\)的数连边，求出所有连通块个数以及块内最大\(c_i\)的和。

所以用线性筛求出每个数的\(h(i)\),对于\(h(a_i) \leq x\)的数\(a_i\)，可以直接抛弃，因为他们自始至终不会产生边。

对于\(h(a_i)>x\),它们的大小不会超过\(\sqrt a\),所以只需要\(\sqrt a\)个点就可以解决，\(h(a_i)\)相同的数可以看成一个点，\(c\)就是最大值。

这样，对于\(x\)从大到小排序后，再一次向图中加边，用并查集维护答案即可。

• 结论：

1) 对于边数较多的情况，如果所有边都是一个一个区间地加入，就可以线段树优化建图；否则，就要思考删点删边，将不会涉及到的点去除。

2) 线性筛的好处就是，对每个数都只需要考虑它的最小质因子，因为在它之前的数已经求好了，而这一步一定是由最小质因子筛出来的。不仅是筛法，许多dp也遵循这样的单调性更新原则。这样可以减少维护的东西，如这题从维护所有的质因子变成只需要维护最小质因子。