頁面無法載入？點擊這裡可能會修復。
Placeholder

#8259
子任務

최애 연산자 1s 1024MB

問題

농부 존의 농장은 또다시 춥고 지루한 하루이다. 시간을 보내기 위해 농부 존은 정수 배열을 가지고 연산을 수행하는 재미있는 오락을 고안했다.

농부 존에게는 길이가 N(1 \leq N \leq 2 \cdot 10^5)인 음이 아닌 정수 배열 a 와 정수 M(1 \leq M \leq 10^9)이 있다. 이후, 농부 존은 한 개의 정수 x 를 정할 것이다.

하나의 연산에서, 농부 존은 인덱스 iii 를 선택한 후 a_i​ 에서 1을 더하거나 빼는 작업을 수행할 수 있다.

농부 존의 지루함 수치(boredom value)란, 모든 1 \leq i \leq N 에 대해 (a_i - x) 가 M 으로 나누어 떨어지도록 만들기 위해 필요한 최소 연산 횟수를 의미한다.

모든 가능한 x 중에서 농부 존의 최소 지루함 수치를 출력하라.


輸入

첫 번째 줄에는 정수 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 을 넘지 않음이 보장된다.


輸出

각 테스트 케이스에 대해, 농부 존의 최소 지루함 수치를 한 줄에 하나씩 출력하라.


子任務

編號 分數 條件
#110分

N \le 1000, M\le 1000

#220分

N \le 1000

#330分

M\le 10^5

#440分

추가 제약 조건 없음


範例 

2
5 9
15 12 18 3 8
3 69
1 988244353 998244853
10
21

첫 번째 테스트 케이스에서, 최적의 x 중 하나는 3 이다.
이 경우, 10번의 연산을 수행하면 a = [12,12,21,3,12] 로 만들 수 있다.

두 번째 테스트 케이스에서, 최적의 x 를 선택하면 최소 연산 횟수는 21 이다.


來源

USACO 2025 January Silver

需要登入才能撰寫程式碼。