ABBYY Cup 2.0 - Easy |
---|
Закончено |
Умный Бобер из ABBYY решил устроить себе выходной. Но бездельничать целый день оказалось слишком скучно, и он решил поиграть в игру с камешками. Изначально у Бобра есть n камешков. Он раскладывает их в a одинаковых рядов по b штук в каждом (a > 1). Учтите, что Бобер обязательно использует все камешки, то есть n = a·b.
После того, как он разложил камешки, Умный Бобер забирает обратно любой из полученных рядов (то есть b камешков) и выбрасывает все остальные камешки. Затем он снова раскладывает все свои камешки (выбирая, возможно, другие a и b) и снова забирает себе один ряд, и так далее. Игра продолжается до тех пор, пока в какой-то момент у Бобра не останется ровно один камешек.
Игровой процесс можно представить себе как конечную последовательность целых чисел c1, ..., ck, где:
Результатом игры называется сумма чисел ci. Вам дано число n. Найдите максимальный возможный результат игры.
Единственная строка входных данных содержит единственное целое число n — начальное количество камешков у Умного Бобра.
Ограничения на входные данные для получения 30 баллов:
Ограничения на входные данные для получения 100 баллов:
Выведите единственное целое число — максимальный возможный результат игры.
10
16
8
15
Рассмотрим первый пример (c1 = 10). Возможные варианты развития игры:
Название |
---|