2020中国大学生程序设计竞赛（CCPC）-网络选拔赛 题解
时间：2020-09-21 16:58:48
收藏：0
阅读：400
1001
1002
题意：给定一个n个点的完全图，边权为lcm(i+1,j+1)，求最小生成树。
考虑这样一个构造方法
所有数字都向自身的最小质因数连边
这样可以保证每个数字的贡献都是其本身，达到了理论最小。（lcm一定比自己本身要大）
然后就有了k棵以质数为根的树
然后考虑连接这k棵树
显然质数之间的lcm就是它们的乘积
所以所有根都和2连边即可
考虑计算答案
记\(tot\)为2到n+1的所有素数的和
\[\\]
\[ans=2*(tot-2)-tot+\sum_{i=2}^{n+1} i
\ =tot - 4+\sum_{i=2}^{n+1} i
\ =tot+\frac{n^2+3n-8}{2}
\\]
原文：https://www.cnblogs.com/Creed-qwq/p/13705057.html
评论（0）