도서관 책띠의 공통 간격

문제

도서관은 전시할 책에 길이가 정해진 종이 책띠를 두른다. 이번 전시에서는 책띠마다 같은 간격으로 안내 표시를 찍으려 한다. 안내 표시는 책띠의 시작점과 끝점에도 있어야 하며, 이웃한 두 표시 사이의 간격은 모두 같아야 한다. 책띠의 길이와 표시 간격은 같은 단위를 사용하고, 표시 간격은 양의 정수로 정한다. 보관함에는 N권의 책과 각 책에 사용할 책띠가 하나씩 있다. i번째 책의 책띠 길이는 A_i다. 길이가 A_i인 책띠에 간격 d로 표시를 찍을 수 있으려면 A_i가 d로 나누어떨어져야 한다. 시작점에서 간격 d만큼 이동하는 일을 반복했을 때 정확히 끝점에 도달해야 하기 때문이다. 책띠를 자르거나 이어 붙이거나 길이를 바꾸는 작업은 허용되지 않는다. 전시 담당자는 보관함의 책 중 정확히 K권을 골라야 한다. 선택한 모든 책띠에 동일한 간격 d를 사용하며, 선택하지 않은 책띠에는 표시를 찍지 않는다. 표시를 너무 촘촘하게 찍지 않도록 가능한 간격 중 가장 큰 값을 구하려 한다. 어떤 간격을 사용할 수 있는 책이 K권보다 많더라도 그중 K권만 고르면 되므로 그 간격을 사용할 수 있다. 책의 번호는 서로 다르며 책띠 길이가 같은 책도 각각 한 권으로 센다. 선택할 책은 보관함에서 연속해서 놓여 있을 필요가 없고, 입력에 나타난 순서도 선택에 영향을 주지 않는다. K가 1이면 책 한 권에 사용할 수 있는 가장 큰 간격을 찾는다. K가 N이면 모든 책띠에 공통으로 사용할 수 있어야 한다. 길이는 모두 양의 정수이므로 간격 1은 언제나 사용할 수 있으며 답이 없는 경우는 없다. 최대 간격만 출력하고, 선택한 책의 번호나 안내 표시의 개수는 출력하지 않는다. 책띠 길이 목록이 주어졌을 때 전시 규칙을 만족하는 최대 간격을 구하는 프로그램을 작성한다.

입력

첫째 줄에 정수 N과 K가 공백으로 구분되어 주어진다. 1 ≤ K ≤ N ≤ 100,000이다.
둘째 줄에 N개의 정수 A_1, A_2, ..., A_N이 공백으로 구분되어 주어진다. 모든 i에 대해 1 ≤ A_i ≤ 200,000이다. 같은 길이가 여러 번 주어질 수 있다.

출력

정확히 K권의 책을 골랐을 때 선택한 모든 책띠에 사용할 수 있는 가장 큰 양의 정수 간격을 출력한다. 가능한 책 선택이 여러 개여도 간격 하나만 출력한다. 답은 항상 존재한다.

6 3
12 18 24 25 30 42

6

4 4
7 11 13 17

1

5 1
8 27 14 27 6

27

출처: Devin.KR 자체 제작