Задачи
Проблема Лонги
Проблема Лонги
Лонги хорошо разбирается в математике, он любит задумываться над трудными математическими задачами, которые могут быть решены при помощи некоторых изящных алгоритмов. И вот такая задачка возникла:
Дано целое число n (1 < n < 2^31), Вы должны вычислить ∑gcd(i, n) для всех 1 ≤ i ≤ n.
"О, я знаю, я знаю!" - воскликнул Лонги! А знаете ли Вы? Пожалуйста, решите её.
Входные данные
Каждая строка содержит одно число n.
Для каждого значения n следует вывести в отдельной строке сумму ∑gcd(i, n) для всех 1 ≤ i ≤ n.
Пример
Входные данные #1
2 6 12
Выходные данные #1
3 15 40