Problem Description

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.

Input Format

A positive integer $n$.

Output Format

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

4

4

30

183

100

1916

Hint

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