창고의 공통 포장 수량

문제

물류 창고에는 종류가 서로 다른 물품이 보관되어 있다. 창고 담당자는 출고 전에 모든 물품을 작은 상자로 나누어 포장하려 한다. 물품의 종류는 1번부터 N번까지 구분하며, i번 물품의 재고는 A_i개다. 모든 재고는 양의 정수이고, 포장 도중에 물품을 추가하거나 버릴 수 없다. 이번 작업에서는 모든 상자에 들어가는 물품의 개수를 하나의 양의 정수 K로 통일한다. 한 상자에는 반드시 한 종류의 물품만 넣으며, 서로 다른 종류를 섞을 수 없다. 같은 종류의 물품을 여러 상자로 나누는 것은 가능하다. 상자에 빈자리를 남기는 것도 허용하지 않으므로, 각 종류의 재고를 정확히 K개씩 나누었을 때 남는 물품이 없어야 한다. 예를 들어 어떤 종류의 재고가 18개라면 K가 3일 때는 그 종류를 여섯 상자로 포장할 수 있다. 그러나 K가 4라면 두 개가 남으므로 이번 작업의 규칙을 만족하지 못한다. 한 종류에서 포장할 수 있다는 사실만으로 충분하지 않으며, 창고에 있는 모든 종류가 같은 K를 사용할 수 있어야 한다. 담당자는 상자 하나에 들어가는 물품의 개수 K를 가능한 한 크게 정하려 한다. K를 정한 뒤에는 각 종류의 재고를 모두 포장하는 데 필요한 상자 수를 합산한다. 물품의 부피와 무게는 고려하지 않으며, 상자의 개수에도 제한이 없다. 각 재고가 양의 정수이므로 적어도 K가 1인 포장은 항상 가능하다. 가능한 가장 큰 K와 그 K를 사용했을 때 필요한 전체 상자 수를 구하는 프로그램을 작성한다.

입력

첫째 줄에 물품 종류의 수 N이 주어진다.
둘째 줄에 N개의 정수 A_1, A_2, ..., A_N이 공백으로 구분되어 주어진다.
1 ≤ N ≤ 40,000이다.
1 ≤ A_i ≤ 1,000,000이다.
입력에 등장하는 모든 수는 정수다.

출력

가능한 가장 큰 상자당 물품 수 K와 필요한 전체 상자 수를 순서대로 공백으로 구분하여 한 줄에 출력한다.

3
18 30 42

6 15

4
7 10 13 16

1 46

1
25

25 1

출처: Devin.KR 자체 제작