Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 

Осколки

(Время: 2 сек. Память: 16 Мб Сложность: 88%)

На Землю надвигается страшная угроза, к нам летит облако из N огромных астероидов. Известно только то, что все они одинакового размера. У учёных есть ракеты, способные уничтожить астероиды, каждая такая ракета характеризуется зарядом m – натуральным числом от 1 до N. Но, к сожалению, неизвестно, как каждая из ракет поведёт себя при столкновении с астероидом, поэтому было принято решение запустить по одной ракете каждого вида. И только после столкновения стало известно, что ракета с зарядом m после уничтожения астероида образует осколки в количестве, равном наибольшему общему делителю чисел m и N. Помогите узнать, сколько осколков упадёт на Землю, у Вас совсем мало времени!

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

В единственной строке входного файла INPUT.TXT содержится натуральное число N – количество запущенных ракет и взорванных ими астероидов (1 ≤ N ≤ 1018).

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

В выходной файл OUTPUT.TXT выведите количество осколков, которые упадут на Землю.

Примеры

INPUT.TXTOUTPUT.TXT
135
2615

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]

Красноярский краевой Дворец пионеров, (c)2006 - 2019, E-mail: admin@acmp.ru