ICPC, MXI Saratov Quaterfinal, 3008
Автор задачи: Константин Дроздов
Первоисточник: Навеяно вступительной олимпиадой СГАУ по информатике (Лукачевский марафон, 2008)
Задачу добавил: LGR
Успешно сдано решений: 4
3008 год. В ноябре в городе Саратове будет проводиться 1011-ый четвертьфинал ICPC, и подготовка задач идет полным ходом. Сложность решения жюри в одной из задач оказалась О(D(k)), где D(k) - количество делителей числа k, включая 1 и само k. Для тестирования необходимо, разумеется, найти число с наибольшим D(k), но, как оказалось, все не так просто.
Проблема состоит в том, что инструкция запрещает любое участие в составлении тестов членов жюри, решавших задачу. Когда решали задачу, пришлось привлечь всех членов жюри (задача была очень сложной), и в итоге тесты передали сочинять уборщице. Она написала программу, но в её решении не очень уверены, поскольку сборная уборщиц её года заняла всего 10е место на финале мира АСМ. Поэтому Вас попросили о помощи.
Входные данные
Файл input.txt содержит единственное целое число N (1 <= N <= 1012)
Вsоdные данные
Файл output.txt должен содержать целое число k (1 <= k <= N) такое, что для него D(k) наибольшее (разумеется, среди чисел 1..N), и, через пробел, D(k). Если чисел таковых k несколько, выведите наименьшее из них.
Примеры
input.txt
20
output.txt
12 6
input.txt
2008
output.txt
1680 40
input.txt
9876543210
output.txt
6983776800 2304