Farmer John's Favorite Operation

题目描述

在 Farmer John 的农场里，又是寒冷又无聊的一天。为了打发时间，Farmer John 发明了一项有趣的休闲活动：对一个整数数组进行操作。 Farmer John 有一个包含 $N$（$1 \leq N \leq 2 \cdot 10^5$）个非负整数的数组 $a$，以及一个整数 $M$（$1 \leq M \leq 10^9$）。接着，FJ 会让 Bessie 给出一个整数 $x$。在一次操作中，FJ 可以选择一个下标 $i$，并将 $a_i$ 加 $1$ 或减 $1$。 FJ 的无聊值定义为：为了使对所有 $1 \leq i \leq N$，$a_i-x$ 都能被 $M$ 整除，他必须执行的最少操作次数。 在所有可能的 $x$ 中，输出 FJ 的最小可能无聊值。

输入格式

第一行包含 $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$ 中，FJ 的最小可能无聊值。

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

10
21

提示

在第一个测试用例中，一个最优的 $x$ 取值是 $3$。FJ 可以进行 $10$ 次操作，使得 $a = [12, 12, 21, 3, 12]$。 SCORING: Input 2: $N \le 1000$ and $M \le 1000$. Input 3: $N\le 1000$. Inputs 4-5: $M\le 10^5$. Inputs 6-16: No additional constraints. Problem credits: Chongtian Ma

标签: USACO|2025|Silver

来源

USACO|2025|Silver