택배 칸막이의 공통 길이

문제

택배 포장 작업장에서는 긴 완충재 막대를 잘라 상자 안의 칸막이로 사용한다. 오늘 작업대에 놓인 막대는 N개이며, 각 막대의 길이는 센티미터 단위의 양의 정수이다. 막대마다 길이가 다를 수 있지만, 자동 포장 장치는 길이가 모두 같은 칸막이만 받아들일 수 있다. 작업자는 오늘 준비한 막대를 전부 사용하여 칸막이를 만들려고 한다. 작업자는 먼저 모든 칸막이에 공통으로 적용할 길이 d를 정한다. d 역시 센티미터 단위의 양의 정수여야 한다. 그다음 각 막대를 길이 d인 조각들로 나눈다. 절단 과정에서 사라지는 길이는 없으며, 원래 막대의 양 끝을 다듬는 작업도 하지 않는다. 각 막대는 남는 부분 없이 정확히 나누어져야 한다. 어떤 막대의 길이가 이미 d라면 그 막대 자체를 칸막이 한 개로 사용하며, 별도로 자를 필요가 없다. 서로 다른 막대를 이어 붙이는 것은 허용되지 않는다. 한 막대에서 남은 부분을 다른 막대의 남은 부분과 합쳐 칸막이를 만드는 것도 허용되지 않는다. 따라서 선택한 d는 각 막대에 대해 따로 적용할 수 있어야 한다. 예를 들어 두 막대를 사용할 때에도 두 길이의 합만 d로 나누어지는 것으로는 충분하지 않다. 길이가 같은 막대가 여러 개 있다면 각각 별개의 막대로 취급하여 모두 사용한다. 작업장은 작은 조각을 지나치게 많이 보관하지 않도록, 이 조건을 만족하는 d 중 가장 큰 값을 사용한다. 모든 막대의 길이가 양의 정수이므로 적어도 길이 1인 칸막이는 항상 만들 수 있다. 막대의 길이 목록이 주어질 때 사용할 공통 길이 d와, 모든 막대를 이 길이로 나눈 뒤 얻는 칸막이의 총개수를 구한다. 막대를 자르는 순서나 각 막대에서 얻는 개수는 출력하지 않는다.

입력

첫째 줄에 막대의 개수 N이 주어진다. 둘째 줄에 각 막대의 길이 L_1, L_2, ..., L_N이 공백으로 주어진다.
1 ≤ N ≤ 40,000
1 ≤ L_i ≤ 999,999
입력의 모든 수는 정수이다.

출력

가능한 가장 큰 공통 길이 d와 만들어지는 칸막이의 총개수를 공백으로 구분하여 한 줄에 출력한다. 조건을 만족하는 d는 항상 존재한다.

4
18 30 42 24

6 19

3
7 11 13

1 31

1
25

25 1

출처: Devin.KR 자체 제작