[USACO26FEB] Make All Distinct B

题目描述

你有一个整数数组 $a_1\dots a_N$，其元素初始都在 $[1,N]$ 范围内（$1\le N\le 2\cdot 10^5$），还有一个非零整数 $K$（$-N \le K\le N, K\neq 0$）。

你可以执行任意多次（可能为零次）以下操作：选择一个下标 $i$，并将 $a_i$ 设为 $a_i+K$。

求使数组所有元素互不相同所需的最少操作次数。

输入格式

输入包含 $T$（$1\le T\le 10$）个独立的测试用例。每个测试用例如下描述：

第一行包含 $N$ 和 $K$。

第二行包含 $a_1\dots a_N$。

保证所有测试用例的 $N$ 之和不超过 $10^6$。

输出格式

对于每个测试用例，输出一行，包含最少操作次数。

注意：本题涉及整数的数值可能较大，可能需要使用 64 位整数类型（例如 C/C++ 中的 “long long”）。

输入输出样例 #1

输入 #1

4
4 1
4 1 4 1
4 -3
4 1 4 1
4 4
4 1 4 1
3 -1
1 1 2

输出 #1

2
4
2
1

说明/提示

对于第一个测试用例，下面是一种可能的两次操作序列，能使所有元素互不相同。

4 1 4 1
5 1 4 1 （a_1 <- a_1 + 1）
5 1 4 2 （a_4 <- a_4 + 1）

评分标准

• 输入 2-4：$N\le 50$
• 输入 5-7：$N\le 2000$
• 输入 8-10：$K=1$
• 输入 11-13：无额外限制。

题目来源：Akshaj Arora, Benjamin Qi

翻译由 DeepSeek 完成