미리듣기 조각의 공통 길이

문제

음악 스트리밍 서비스는 새로 등록된 음원에서 미리듣기 조각을 만드는 작업을 준비하고 있다. 작업 대상 음원은 N개이며, 각 음원의 재생 길이는 양의 정수 초 단위로 주어진다. 서비스는 이번 작업에서 사용할 조각의 길이 d를 하나만 정하려고 한다. d 역시 양의 정수 초 단위여야 한다. 어떤 음원을 길이 d인 조각으로 나눌 때에는 음원의 시작부터 끝까지 빠짐없이 나누어야 한다. 모든 조각의 길이는 정확히 d여야 하며, 마지막에 짧은 조각을 남기거나 음원의 일부를 버릴 수 없다. 무음을 덧붙여 길이를 늘리는 것도 허용하지 않는다. 따라서 재생 길이가 d의 배수인 음원만 이번 작업에 사용할 수 있다. 재생 길이가 d와 같다면 조각 하나로 나눌 수 있으므로 사용할 수 있다. 담당자는 최소 K개의 음원을 사용할 수 있어야 한다고 정했다. 이 조건을 만족하는 조각 길이 가운데 가장 큰 d를 선택한다. 조건을 만족하는 d를 고른 뒤에 일부 음원만 임의로 선택하는 것이 아니라, 그 d로 나눌 수 있는 작업 대상 음원을 모두 사용한다. 따라서 실제로 사용하는 음원의 개수는 K보다 클 수도 있다. 서로 다른 음원의 재생 길이가 같을 수 있다. 재생 길이가 같더라도 입력에서 서로 다른 항목으로 주어진 음원은 각각 하나로 센다. 음원의 등록 순서는 길이 선택에 영향을 주지 않는다. 또한 서로 다른 음원에서 만들어지는 조각의 개수를 더하는 문제는 아니다. 조건에서 세는 것은 사용할 수 있는 원본 음원의 개수다. 선택해야 하는 가장 큰 조각 길이와, 그 길이로 나눌 수 있는 음원의 개수를 구한다. 모든 재생 길이가 양의 정수이고 K가 N 이하이므로, 길이 1은 항상 조건을 만족한다. 따라서 답이 없는 경우는 발생하지 않는다.

입력

첫째 줄에 음원의 개수 N과 필요한 최소 음원 개수 K가 공백으로 구분되어 주어진다. N과 K는 정수이며 1 ≤ K ≤ N ≤ 50000이다.
둘째 줄에 각 음원의 재생 길이 A1, A2, ..., AN이 공백으로 구분되어 주어진다. 각 Ai는 1 이상 200000 이하의 정수다.

출력

최소 K개의 음원을 나눌 수 있는 가장 큰 양의 정수 d와, 재생 길이가 d의 배수인 음원의 개수를 공백으로 구분하여 출력한다.

5 3
12 18 24 30 35

6 4

3 2
7 11 13

1 3

4 1
8 20 20 9

20 2

출처: Devin.KR 자체 제작