#PU1471. USACO 2025 January Contest, Silver — Problem 2. Farmer John's Favorite Operation

USACO 2025 January Contest, Silver — Problem 2. Farmer John's Favorite Operation

USACO 2025 January Contest, Silver — Problem 2. Farmer John's Favorite Operation

题目描述

It is another cold and boring day on Farmer John's farm. To pass the time, Farmer John has invented a fun leisure activity involving performing operations on an integer array. Farmer John has an array aa of NN (1≤N≤2⋅1051 \leq N \leq 2 \cdot 10^5) non-negative integers and an integer MM (1≤M≤1091 \leq M \leq 10^9). Then, FJ will ask Bessie for an integer xx. In one operation, FJ can pick an index ii and subtract or add 11 to aia_i. FJ's boredom value is the minimum number of operations he must perform so that ai−xa_i-x is divisible by MM for all 1≤i≤N1 \leq i \leq N. Among all possible xx, output FJ's minimum possible boredom value.

输入格式

The first line contains TT (1≤T≤101 \leq T \leq 10), the number of independent test cases to solve. The first line of each test case contains NN and MM. The second line of each test case contains a1,a2,...,aNa_1, a_2, ..., a_N (0≤ai≤1090 \leq a_i \leq 10^9). It is guaranteed that the sum of NN over all test cases does not exceed 5⋅1055 \cdot 10^5.

输出格式

For each test case, output an integer on a new line containing FJ's minimum possible boredom value among all possible values of xx.

数据范围

(见题面原文)

样例

样例 1

2
5 9
15 12 18 3 8
3 69
1 988244353 998244853
10
21
In the first test case, one optimal choice of $x$ is $3$. FJ can perform $10$
operations to make
$a = [12, 12, 21, 3, 12]$.