Задачі
Проблема Лонгі
Проблема Лонгі
Лонгі добре розбирається у математиці, він любить задумуватись над важкими математичними задачами, які можуть бути розв'язані за допомогою деяких красивих алгоритмів. І ось виникла така задачка:
Задано ціле число $n$. Обчисліть $∑gcd(i, n)$ для всіх $1 \le i \le n$.
"\textit{О, я знаю, я знаю!}" --- вигукнув Лонгі! А чи знаєте Ви? Будь-ласка, розв'яжіть її.
\InputFile
Кожний рядок містить одне число $n~(1 < n < 2^{31})$.
\OutputFile
Для кожного значення $n$ виведіть в окремому рядку суму $∑gcd(i, n)$ для усіх $1 \le i \le n$.
Вхідні дані #1
2 6 12
Вихідні дані #1
3 15 40