Problem B. MST
该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
Problem B. MST
时间限制:1s
空间限制:128MB
题目描述
现有 \(n-1\) 个结点组成的完全图,各点的标号分别是 \(1,2,...,n-1\) ,权值分别是 \(2,3,...,n\)
结点 \(a\) 到结点 \(b\) 之间的距离是它们权值的最小公倍数。
求图的最小生成树。
输入格式
一个整数 \(n\)
输出格式
输出最小生成树的边权和。
样例输入1
6
样例输出1
26
样例1解释
其中一种可行方法见上图。
样例输入2
10086
样例输出2
56685500
数据范围
\(2\le n\le 10^6\)
请注意,答案可能超出 32 位整数的范围