CF1374D Zero Remainder Array

给定一个由 $n$ 个正整数组成的数组 $a$。 初始时，你有一个整数 $x=0$。每一步操作，你可以进行以下两种操作之一： 1. 从 $1$ 到 $n$ 中恰好选择一个 $i$，将 $a_i$ 增加 $x$（即 $a_i := a_i + x$），然后将 $x$ 增加 $1$（即 $x := x + 1$）。 2. 仅将 $x$ 增加 $1$（即 $x := x + 1$）。 对于每个 $i$，第一种操作最多只能对其应用一次。 你的任务是求出最少需要多少步操作，才能使数组中每个元素都能被 $k$ 整除（$k$ 的值已给出）。 你需要回答 $t$ 组独立的测试用例。

输入的第一行包含一个整数 $t$（$1 \le t \le 2 \cdot 10^4$），表示测试用例的数量。接下来是 $t$ 组测试用例。 每组测试用例的第一行包含两个整数 $n$ 和 $k$（$1 \le n \le 2 \cdot 10^5; 1 \le k \le 10^9$），分别表示数组 $a$ 的长度和要求的除数。第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^9$），表示数组 $a$ 的各个元素。 保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$（$\sum n \le 2 \cdot 10^5$）。

对于每组测试用例，输出一个答案，即使数组中每个元素都能被 $k$ 整除所需的最少操作次数。

以样例的第一个测试用例为例： 1. $x=0$，$a = [1, 2, 1, 3]$。仅增加 $x$； 2. $x=1$，$a = [1, 2, 1, 3]$。将 $x$ 加到第二个元素上，并增加 $x$； 3. $x=2$，$a = [1, 3, 1, 3]$。将 $x$ 加到第三个元素上，并增加 $x$； 4. $x=3$，$a = [1, 3, 3, 3]$。将 $x$ 加到第四个元素上，并增加 $x$； 5. $x=4$，$a = [1, 3, 3, 6]$。仅增加 $x$； 6. $x=5$，$a = [1, 3, 3, 6]$。将 $x$ 加到第一个元素上，并增加 $x$； 7. $x=6$，$a = [6, 3, 3, 6]$。此时已得到满足条件的数组。 注意，同一个元素不能多次加上 $x$。 由 ChatGPT 4.1 翻译