题目解析

两个人玩游戏。给定长度为 $n$ 的数组 $a$ 和一个整数 $k$。

• 第一个人先选一个下标 $i$，这一选定的数将作为“基准数”。
• 第二个人从剩下的数中选一个下标 $j$。
• 如果 $|a_i - a_j|$ 能被 $k$ 整除，则第二个人赢；否则第一个人赢。

问：第一个人是否存在一种选法，使得无论第二个人怎么选，他都能赢。
如果存在，输出 YES 和选中的下标；否则输出 NO。

数学转化

我们知道：

[ |a_i - a_j| \text{ 能被 } k \text{ 整除} \iff a_i \equiv a_j \pmod{k} ]

所以第二个人赢的条件是：他能在剩下的数中找到一个与第一个人选的数模 $k$ 同余的数。

反之，第一个人要赢，必须保证他所选的数在模 $k$ 的剩余类中，是唯一的一个。

因为第二个人会选同一个剩余类里的数（只要存在），从而获胜。

算法步骤

1. 对每个数 $x$ 计算 $x \bmod k$，并按模值分组。
2. 查找是否存在某个模值 $r$，使得该组只有一个元素。
3. 如果找到，则第一个人选那个下标，输出 YES 和下标（标程里输出 $b[i][0]$ 就是该元素在输入中的顺序下标，注意输入下标从 1 开始）。
4. 如果所有模值分组大小都不为 1，则输出 NO。

举例验证

例：
$n=4, k=2$
数组：$[1, 2, 3, 4]$

模 2 分组：

• 余 0：$[2,4]$
• 余 1：$[1,3]$

每组大小都是 2，不存在大小为 1 的组 → 输出 NO。

例：
$n=3, k=3$
数组：$[1, 2, 4]$

模 3 分组：

• 余 0：$[]$
• 余 1：$[1,4]$（两个元素）
• 余 2：$[2]$（一个元素）

找到余 2 组大小为 1 → 输出 YES 和下标 3（注意输入：1 下标1，2 下标2，4 下标3）。

复杂度

• 时间：$O(n + k)$
• 空间：$O(n + k)$
• 适合 $n, k$ 较大但总和有限制的题目设定。