Language:

English
Russian

Практикум по программированию

Для участников:
Регистрация  ||   Вход
Список соревнований
Вы не вошли в систему! Вход или регистрация.

Функция Эйлера

Time limit:2 sec.
Memory limit: 65536 KByte

Недавно Дима узнал, что функция Эйлера от натурального числа k- это количество чисел, не больших k и взаимно простых с ним. Дима стал искать значения функции Эйлера для всех делителей данного числа n, потом сложил все полученные значения. Напишите, какой ответ получился у Димы.

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

В единственной строке ввода дано натуральное 1 ≤ n ≤ 1014.

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

В строке вывода напечатайте ответ на вопрос задачи.

Пример

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

Примечание

Делители числа 6: 1, 2, 3 и 6. Тогда искомая сумма будет равна ф(1) + ф(2) + ф(3) + ф(6) = 1 + 1 + 2 + 2 = 6.

© Copyright ВоГУ, АВТ, Носов Д.А., Смоленцев К.Н.