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