음악 조각의 공통 길이

문제

한 음악 스트리밍 서비스는 곡을 내려받을 때 여러 개의 짧은 조각으로 나누어 저장하는 방식을 시험하고 있다. 이번 시험에는 N개의 곡을 사용하며, i번 곡의 재생 시간은 정수 T_i밀리초이다. 각 곡의 시작부터 끝까지 빠짐없이 저장해야 하므로 재생 시간을 줄이거나 끝부분에 무음을 덧붙일 수 없다. 저장 장치를 단순하게 만들기 위해 모든 곡에서 같은 길이의 조각을 사용하려고 한다. 조각의 길이를 정수 L밀리초로 정하면, 각 곡은 그 곡의 시작 지점부터 길이가 정확히 L인 조각들로 나뉘어야 한다. 마지막 조각만 짧게 만드는 것은 허용하지 않는다. 따라서 어떤 곡이든 재생 시간이 L로 나누어떨어져야 한다. L은 반드시 양의 정수여야 한다. 곡마다 만들어지는 조각의 개수는 달라도 된다. 예를 들어 어떤 곡의 재생 시간이 다른 곡의 두 배라면, 같은 길이로 나눈 뒤 첫 번째 곡의 조각 개수가 두 번째 곡의 두 배가 되어도 문제가 없다. 다만 서로 다른 곡의 끝부분과 시작 부분을 이어서 하나의 조각을 만들 수는 없다. 각 곡은 독립적으로 나눈다. 서비스는 조각 하나를 관리할 때마다 고정된 정보를 저장하므로, 사용할 수 있는 공통 조각 길이 중 가장 긴 길이를 선택하려고 한다. 그 길이를 선택한 뒤에는 모든 곡에서 만들어지는 조각의 총개수도 계산해야 한다. 재생 시간이 같은 곡이 여러 개 주어져도 각각 별개의 곡이므로, 각 곡에서 생기는 조각을 모두 합산한다. 곡의 순서는 결과에 영향을 주지 않는다. 모든 재생 시간이 양의 정수이므로 길이 1밀리초인 조각은 언제나 사용할 수 있고, 가능한 길이가 없는 경우는 없다. 가장 긴 길이는 수치로 하나만 정해지므로 별도의 동점 처리는 필요하지 않다. 모든 곡을 정확히 나눌 수 있는 가장 긴 조각 길이와, 그 길이로 나누었을 때 만들어지는 조각의 총개수를 구한다.

입력

첫째 줄에 곡의 수를 나타내는 정수 N이 주어진다. 1 ≤ N ≤ 30,000이다.
둘째 줄에 N개의 정수 T_1, T_2, …, T_N이 공백으로 구분되어 주어진다. 모든 i에 대해 1 ≤ T_i ≤ 1,000,000,000이며, 단위는 밀리초이다.

출력

가장 긴 공통 조각 길이 L과 그 길이로 나누었을 때 만들어지는 조각의 총개수를 정수 두 개로 공백으로 구분하여 출력한다. L의 단위는 밀리초이며, 단위 문자는 출력하지 않는다.

3
4200 6300 10500

2100 10

4
1001 1000 2500 4999

1 9500

1
987654321

987654321 1

출처: Devin.KR 자체 제작