P2303 [SDOI2012] Longge's Problem

Longge excels at mathematics, and he enjoys tackling challenging math problems.

Here is the problem: Given an integer $n$, you need to compute $\sum\limits_{i=1}^n \gcd(i, n)$, where $\gcd(i, n)$ denotes the greatest common divisor of $i$ and $n$.

The input consists of a single line containing the integer $n$.

Output a single integer on one line representing the answer.

#### Constraints - For $60\%$ of the testdata, it is guaranteed that $n \leq 2^{16}$. - For $100\%$ of the testdata, it is guaranteed that $1 \leq n < 2^{32}$. Translated by ChatGPT 5