Hide
GCD Sum 2
Given an integer $N$, compute the sum
\[ \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$.
Input
The first and only line contains the integer $N$ ($1 \le N \le 5 \cdot 10^7$) from the statement.
Output
Output the sum from the task description.
| Sample Input 1 | Sample Output 1 |
|---|---|
1 |
0 |
| Sample Input 2 | Sample Output 2 |
|---|---|
11 |
77 |
| Sample Input 3 | Sample Output 3 |
|---|---|
4242 |
43415937 |
| Sample Input 4 | Sample Output 4 |
|---|---|
50000000 |
13151742086945156 |
