캠핑장의 등불 간격

문제

한 캠핑장에는 서로 떨어진 원형 산책로 N개가 있다. 관리인은 야간에 손님이 길을 따라 걸을 수 있도록 각 산책로에 등불을 설치하려 한다. 산책로의 길이는 모두 미터 단위의 양의 정수로 기록되어 있다. 산책로마다 출발점을 하나 정하고, 출발점에도 반드시 등불을 하나 설치한다. 관리인은 모든 산책로에서 이웃한 등불 사이의 거리를 같은 값 d미터로 맞추려 한다. d는 양의 정수여야 한다. 각 산책로의 출발점에서 진행 방향을 따라 d미터마다 등불을 설치했을 때, 마지막 등불에서 출발점으로 돌아오는 구간의 길이도 정확히 d미터여야 한다. 따라서 길이가 L미터인 산책로에는 L을 d로 나누어떨어지게 할 수 있을 때만 이 간격을 사용할 수 있다. 길이가 d와 같은 산책로에는 출발점의 등불 하나만 설치하며, 그 등불에서 한 바퀴 돌아오는 거리가 d미터가 된다. 설치와 관리에 드는 수고를 줄이기 위해 가능한 간격 중 가장 큰 d를 선택한다. 산책로들은 서로 연결되어 있지 않으므로, 서로 다른 산책로의 등불을 함께 사용하는 일은 없다. 한 산책로의 출발점은 한 바퀴를 마쳤을 때 다시 만나더라도 중복해서 세지 않는다. 산책로의 길이가 같아도 각각 별개의 산책로로 취급한다. 모든 산책로의 길이가 주어질 때, 선택해야 하는 등불 간격과 전체 산책로에 설치할 등불 수의 합을 구하는 프로그램을 작성한다. 간격 1미터는 항상 사용할 수 있으므로 가능한 간격이 없는 경우는 없다. 가장 큰 간격은 하나로 정해지며, 그 간격에서 등불 수도 유일하게 정해진다.

입력

첫째 줄에 산책로 수 N이 주어진다. 둘째 줄에 각 산책로의 길이 L_1, L_2, ..., L_N이 공백으로 구분되어 주어진다. 모든 입력값은 정수이며, 1 ≤ N ≤ 30,000, 1 ≤ L_i ≤ 1,000,000,000이다.

출력

가장 큰 등불 간격 d와 전체 등불 수의 합을 순서대로 한 줄에 공백으로 구분하여 출력한다. 두 값 모두 정수로 출력한다.

3
18 30 42

6 15

1
17

17 1

4
8 9 8 9

1 34

출처: Devin.KR 자체 제작