같은 칸에 모이는 상품 번호

문제

편의점 창고에서는 상품에 붙은 정수 번호를 이용해 보관함의 칸을 정한다. 새 보관함의 칸 수를 K로 정하면 칸에는 0부터 K−1까지 번호를 붙이고, 상품 번호를 K로 나눈 나머지와 같은 번호의 칸에 그 상품을 넣는다. 예를 들어 칸 수가 6이면 상품 번호 13은 1번 칸에 들어간다. 상품 번호는 상품의 종류를 나타내므로, 여러 상품에 같은 번호가 붙어 있을 수도 있다. 이번에 들어온 상품들은 함께 꺼내 쓰는 묶음이다. 직원은 이 묶음에 속한 모든 상품이 하나의 칸에 들어가도록 보관함을 설정하려 한다. 어느 번호의 칸에 들어가는지는 상관없지만, 상품마다 서로 다른 칸에 들어가서는 안 된다. 보관함에는 충분한 공간이 있으므로 한 칸에 들어가는 상품 수에는 제한이 없다. 상품 번호를 바꾸거나 일부 상품을 묶음에서 제외하는 것은 허용하지 않는다. 보관함의 칸 수 K는 2 이상 M 이하인 정수로만 설정할 수 있다. 조건을 만족하는 설정이 여러 개라면 직원은 다른 묶음도 나중에 나누어 담을 수 있도록 칸 수가 가장 큰 설정을 선택한다. 단, 현재 주어진 묶음의 상품들은 그 설정에서도 모두 같은 칸에 들어가야 한다. 조건을 만족하는 설정이 하나도 없다면 보관함을 사용할 수 없다고 표시한다. 상품의 개수와 각 상품 번호, 설정 가능한 최대 칸 수 M이 주어진다. 직원이 선택해야 하는 K를 구한다. 상품이 한 개뿐이거나 모든 상품 번호가 같아도 같은 규칙을 적용한다. 선택된 칸의 번호나 상품의 배치 순서는 출력하지 않으며, 가능한 칸 수 중 가장 큰 값만 출력한다.

입력

첫째 줄에 상품 수 N과 최대 칸 수 M이 공백으로 주어진다.
둘째 줄에 상품 번호 X₁, X₂, …, Xₙ이 공백으로 주어진다.
모든 입력값은 정수이며, 1 ≤ N ≤ 30,000, 2 ≤ M ≤ 1,000,000,000, 0 ≤ Xᵢ ≤ 1,000,000,000이다.

출력

모든 상품 번호를 K로 나눈 나머지가 같아지는 정수 K 중 2 ≤ K ≤ M을 만족하는 가장 큰 값을 출력한다. 그러한 K가 없으면 -1을 출력한다.

3 10
14 38 62

8

3 20
7 12 18

-1

4 17
23 23 23 23

17

출처: Devin.KR 자체 제작