P9488 ZHY’s Spanning Tree.

ZHY has a complete graph with $n$ vertices. The distance (edge weight) between vertex $u$ and vertex $v$ is $\gcd(u,v)$. Find the sum of edge weights of the maximum spanning tree of this complete graph.

A positive integer $n$.

An integer, representing the sum of edge weights of the maximum spanning tree.

**This problem uses bundled testdata.** $\text{Subtask}$ $0\kern{3pt}$(10pts): $n\le 5$. $\text{Subtask}$ $1\kern{3pt}$(20pts): $n\le 1000$. $\text{Subtask}$ $2\kern{3pt}$(30pts): $n\le 10^{6}$. $\text{Subtask}$ $3\kern{3pt}$(40pts): $n\le 10^{7}$. For all testdata, $1\le n \le 10^{7}$. Translated by ChatGPT 5