농부 존이 가장 좋아하는 연산

농부 존의 농장에 또다시 춥고 지루한 하루가 찾아왔다. 시간을 보내기 위해 농부 존은 정수 배열에 연산을 수행하는 재미있는 여가 활동을 고안했다.

농부 존은 음이 아닌 정수 \(N\)개(\(1 \leq N \leq 2 \cdot 10^5\))로 이루어진 배열 \(a\)와 정수 \(M\)(\(1 \leq M \leq 10^9\))을 가지고 있다. 그런 다음 농부 존은 베시에게 정수 \(x\)를 요청한다. 한 번의 연산으로 농부 존은 인덱스 \(i\)를 골라 \(a_i\)에 \(1\)을 더하거나 뺄 수 있다. 농부 존의 지루함 값은 모든 \(1 \leq i \leq N\)에 대해 \(a_i-x\)가 \(M\)으로 나누어떨어지도록 만들기 위해 수행해야 하는 연산의 최소 횟수이다.

가능한 모든 \(x\) 중에서 농부 존의 최소 지루함 값을 출력하시오.

Problem credits: Chongtian Ma

배점

• 입력 2: \(N \le 1000\)이고 \(M \le 1000\).
• 입력 3: \(N\le 1000\).
• 입력 4-5: \(M\le 10^5\).
• 입력 6-16: 추가 제약이 없다.

Problem credits: Chongtian Ma

첫째 줄에 풀어야 할 독립적인 테스트 케이스의 수 \(T\)(\(1 \leq T \leq 10\))가 주어진다.

각 테스트 케이스의 첫째 줄에 \(N\)과 \(M\)이 주어진다.

각 테스트 케이스의 둘째 줄에 \(a_1, a_2, ..., a_N\)(\(0 \leq a_i \leq 10^9\))이 주어진다.

모든 테스트 케이스에 대한 \(N\)의 합은 \(5 \cdot 10^5\)를 넘지 않음이 보장된다.

각 테스트 케이스마다, 가능한 모든 \(x\) 값 중 농부 존의 최소 지루함 값을 새로운 줄에 정수로 출력한다.

riseoj 작성

출처 올림피아드 > USACO > 2024-2025 > January > Silver