|
Осколки
(Время: 2 сек. Память: 16 Мб Сложность: 88%)
На Землю надвигается страшная угроза, к нам летит облако из N огромных астероидов. Известно только то, что все они одинакового размера. У учёных есть ракеты, способные уничтожить астероиды, каждая такая ракета характеризуется зарядом m – натуральным числом от 1 до N. Но, к сожалению, неизвестно, как каждая из ракет поведёт себя при столкновении с астероидом, поэтому было принято решение запустить по одной ракете каждого вида. И только после столкновения стало известно, что ракета с зарядом m после уничтожения астероида образует осколки в количестве, равном наибольшему общему делителю чисел m и N. Помогите узнать, сколько осколков упадёт на Землю, у Вас совсем мало времени!
Входные данные
В единственной строке входного файла INPUT.TXT содержится натуральное число N – количество запущенных ракет и взорванных ими астероидов (1 ≤ N ≤ 1018).
Выходные данные
В выходной файл OUTPUT.TXT выведите количество осколков, которые упадут на Землю.
Примеры
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 3 | 5 |
| 2 | 6 | 15 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| |
