e-olymp
Задачи

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

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

Лонги хорошо разбирается в математике, он любит задумываться над трудными математическими задачами, которые могут быть решены при помощи некоторых изящных алгоритмов. И вот такая задачка возникла:

Дано целое число n (1 < n < 231), Вы должны вычислить ∑gcd(i, n) для всех 1in.

"О, я знаю, я знаю!" - воскликнул Лонги! А знаете ли Вы? Пожалуйста, решите её.

Входные данные

Каждая строка содержит одно число n.

Входные данные

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

Лимит времени 1 секунда
Лимит использования памяти 64 MiB
Входные данные
2
6
Выходные данные
3
15