Задача №114203. Много пирожных
На кондитерской фабрике есть \(n\) видов пирожных, пирожных \(i\)-го вида та фабрике а штук. Было принято решение отвезти пирожные на продажу на ярмарку, но директор фабрики решил, что кондитерские изделия на ярмарочной витрине должны быть выложены одинаковыми рядами, при этом пирожных каждого вида должно быть одинаковое количество. Необязательно отвозить на ярмарку все виды пирожных, можно выбрать некоторые виды и взять одинаковое число пирожных каждого выбранного вида.
Помогите директору отвезти на ярмарку наибольшее число пирожных — найдите, сколько видов пирожных и сколько пирожных каждого вида нужно отвезти на ярмарку.
Первая строка входных данных содержит число \(n\) — количество видов пирожных на фабрике, \(1 \le n \le 10^5\). Следующие \(n\) строк содержат по одному числу \(a_i\) — количество пирожных \(i\)-го вида, \(1 \le a_i \le 10^5\). Сумма всех значений \(a_i\) не превосходит \(2 х 10^9\).
Программа должна вывести два целых числа. Первое число равно количеству видов пирожных, которые необходимо выбрать для ярмарки. Второе число равно количеству пирожных каждого выбранного вида, которые нужно отвезти на ярмарку.
Если возможных ответов несколько, выведите любой из них.
Пояснение к примеру. Имеется 3 вида пирожных количеством 4, 10 и 7 штук. Наилучший ответ будет, если взять по 7 пирожных второго и третьего вида.
Решение, правильно работающее только для случаев, когда все входные числа не превосходят 10, будет оцениваться в 30 баллов.
Решение, правильно работающее только для случаев, когда \(n \le 100\), будет оцениваться в 60 баллов.
3 4 10 7
2 7