세탁소의 공통 포장 단위

문제

한 세탁소는 세탁과 건조가 끝난 작업복을 종류별로 포장하여 보관한다. 오늘 포장할 작업복은 N종류이며, 각 종류의 작업복은 한 벌 이상 있다. 담당자는 포장 규칙을 단순하게 유지하기 위해 오늘 사용하는 모든 포장에 같은 수의 작업복을 넣으려 한다. 하나의 포장에는 반드시 같은 종류의 작업복만 들어가야 한다. 서로 다른 종류의 작업복은 크기나 관리 방법이 같더라도 섞을 수 없다. 또한 모든 작업복을 정확히 한 번씩 포장해야 하며, 포장하지 않고 남겨 두거나 다른 날의 작업복을 가져와 수량을 맞출 수 없다. 한 포장에 넣는 작업복 수를 양의 정수 d라고 하자. 어떤 종류의 작업복이 a벌 있다면, 그 종류는 정확히 a를 d로 나눈 수만큼의 포장으로 나뉘어야 한다. 따라서 a가 d로 나누어떨어지지 않으면 그 d는 사용할 수 없다. 종류마다 포장 수가 달라도 되지만, 한 포장에 들어가는 작업복 수 d는 모든 종류에서 같아야 한다. 사용 가능한 d가 여러 개라면 담당자는 그중 가장 큰 값을 선택한다. 포장 한 개에 더 많은 작업복을 넣어 전체 포장 수를 줄이기 위해서다. 작업복 수가 같은 종류가 여러 개 있더라도 서로 다른 종류이므로 각각 따로 포장하며, 입력에서 같은 수량이 반복된다는 이유로 어느 종류를 생략하지 않는다. 예를 들어 두 종류가 각각 8벌과 12벌이라면 한 포장에 4벌씩 넣어 각각 2개와 3개의 포장으로 나눌 수 있다. 하지만 한 포장에 8벌씩 넣으면 두 번째 종류를 남김없이 포장할 수 없으므로 허용되지 않는다. 모든 종류의 수량이 양수이므로 한 포장에 1벌씩 넣는 방법은 항상 가능하다. 따라서 사용할 수 있는 포장 단위가 없는 경우는 발생하지 않는다. 가장 큰 포장 단위 d와, 그 단위를 사용했을 때 모든 종류에 걸쳐 만들어지는 포장의 총개수를 구하는 프로그램을 작성한다.

입력

첫째 줄에 작업복 종류의 수 N이 주어진다. N은 1 이상 50,000 이하의 정수다.
둘째 줄에 각 종류의 작업복 수 a_1, a_2, ..., a_N이 공백으로 주어진다. 각 a_i는 1 이상 100,000 이하의 정수다.

출력

가장 큰 포장 단위 d와 이 단위로 모든 작업복을 포장했을 때의 포장 총개수를 한 줄에 공백으로 구분하여 출력한다.

3
18 30 42

6 15

4
7 11 13 17

1 48

1
99999

99999 1

출처: Devin.KR 자체 제작