Решения

Областная олимпиада по информатике. 10-11 классы. 2014-2015 учебный год.

Задача A. Факториал

Ограничение по времени:

2 секунды

Ограничение по памяти:

64 мегабайта

Условие этой задачи очень простое. Найдите наименьшее $K$ такое, что $K!$ делится на $N$ без остатка. $K! = 1 \cdot 2 \cdot 3 \cdot \ldots \cdot (K-1) \cdot K.$

Формат входного файла

В первой и единственной строке дано число $N$ $(1 \le N \le 10^{16}).$

Формат выходного файла

Выведите ответ на задачу.

Примеры:

Вход

Ответ

Вход

Ответ

Замечание

$N \le 10 $ — $10\%$ тестов.
$N \le 100 $ — $20\%$ тестов.
$N \le 1000$ — $30\%$ тестов.
$N \le 10^6 $ — $40\%$ тестов.
$N \le 10^9 $ — $50\%$ тестов.

посмотреть в олимпиаде

Комментарий/решение: