P1390 Sum of GCDs

One day, TIBBAR and LXL competed to see who could first compute the sum of the greatest common divisors of every pair of distinct numbers among the $n$ numbers from $1 \sim n$. LXL is still typing a complicated and lengthy program, hoping to get an answer within $100s$. TIBBAR, however, wants to pass in $1s$ for a decisive win; please help him accomplish this task.

Given $n$, compute $$\sum_{i = 1}^n \sum_{j = i + 1}^n \gcd(i, j)$$ where $\gcd(i, j)$ denotes the greatest common divisor of $i$ and $j$.

The input consists of a single line with one integer, denoting $n$.

Output a single line with one integer representing the answer.

Constraints - For 40% of the testdata, $n \leq 2 \times 10^3$. - For 100% of the testdata, $2 \leq n \leq 2 \times 10^6$. Translated by ChatGPT 5