e-olymp
Змагання

July 9 - ADA Training

Проблема Лонгі

Лонгі добре розбирається у математиці, він любить задумуватись над важкими математичними задачами, які можуть бути розв'язані за допомогою деяких красивих алгоритмів. І ось така задачка виникла:

Задано ціле число n (1 < n < 231), Ви повинні обчислити ∑gcd(i, n) для всіх 1in.

"О, я знаю, я знаю!" - вигукнув Лонгі! А чи знаєте Ви? Будь-ласка, розв'яжіть її.

Вхідні дані

Кожний рядок містить одне число n.

Вихідні дані

Для кожного значення n необхідно вивести в окремому рядку суму ∑gcd(i, n) для усіх 1in.

Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB
Вхідні дані #1
2
6
12
Вихідні дані #1
3
15
40