题目题解：D. Turtle Tenacity: Continual Mods

问题重述

给定一个长度为 $n$ 的数组 $a$，可以任意重排成 $b_1, b_2, \dots, b_n$，判断是否存在一种排列使得：

$$b_1 \bmod b_2 \bmod b_3 \bmod \dots \bmod b_n \neq 0 $$

其中取模运算从左到右顺序执行。

---

核心观察

连续取模运算有一个重要性质：

一旦某个中间结果变成 $0$，之后的所有取模结果都是 $0$。

因此，我们的目标是避免在运算过程中过早出现 $0$。

另一个重要性质：

如果当前值为 $x$，下一个模数为 $y$，则 $x \bmod y < y$。 特别地，如果 $y > x$，则 $x \bmod y = x$（值不变）。

---

解题思路

第一步：排序

将数组按非递减顺序排序，得到：

$$a_1 \le a_2 \le \dots \le a_n$$

第二步：检查最小值是否唯一

情况 1： $a_1 \neq a_2$

此时最小值是唯一的。我们可以将 $a_1$ 放在序列的第一个位置：

$$b = [a_1, a_2, a_3, \dots, a_n]$$

计算过程：

• 第一步：$a_1 \bmod a_2$
• 因为 $a_1 < a_2$（最小值唯一且排序后 $a_1 < a_2$），所以 $a_1 \bmod a_2 = a_1$
• 之后的所有数都 $\ge a_2 > a_1$，因此 $a_1$ 保持不变
• 最终结果为 $a_1 > 0$

结论： 当最小值唯一时，答案一定是 YES。

---

第三步：最小值不唯一的情况

情况 2： $a_1 = a_2$（最小值出现至少两次）

此时不能简单地把最小值放在开头，因为：

$$a_1 \bmod a_2 = a_1 \bmod a_1 = 0$$

一旦出现两个最小值相邻，就会得到 $0$。

但是，如果存在一个元素 $a_x$ 不是 $a_1$ 的倍数，即：

$$a_x \bmod a_1 \neq 0$$

则我们可以构造如下排列：

$$b = [a_x, a_1, a_2, \dots, a_{x-1}, a_{x+1}, \dots, a_n] $$

计算过程：

• 第一步：$a_x \bmod a_1$
• 因为 $a_x \bmod a_1 < a_1$，记这个余数为 $r$（$0 < r < a_1$）
• 接下来对 $a_1$ 取模：$r \bmod a_1 = r$（因为 $r < a_1$）
• 之后的所有数都 $\ge a_1 > r$，因此 $r$ 保持不变
• 最终结果为 $r > 0$

结论： 当最小值不唯一，但存在一个不是最小值倍数的数时，答案是 YES。

---

第四步：所有元素都是最小值的倍数

情况 3： $a_1 = a_2$ 且对所有 $i$ 有 $a_i \bmod a_1 = 0$

此时数组中所有数都是 $a_1$ 的倍数。

无论怎么排列，至少有一个最小值不在第一位（因为最小值至少有两个）。考虑任意排列：

• 第一个数记为 $b_1$
• 当遇到第一个 $a_1$（最小值）时，有两种可能：
  1. 如果 $b_1$ 也是 $a_1$ 的倍数，则 $b_1 \bmod a_1 = 0$，结果变成 $0$
  2. 如果 $b_1$ 之前已经变成 $0$，那结果已经是 $0$

更严格地证明：在序列中必然出现至少一次 $x \bmod a_1$ 的运算，其中 $x$ 是 $a_1$ 的倍数，结果必然是 $0$。之后所有取模结果都是 $0$。

结论： 当所有元素都是最小值的倍数时，答案是 NO。

---

算法流程

sort(a, a + n);

if (a[0] != a[1]) {
    // 最小值唯一
    cout << "YES\n";
}
else {
    // 最小值不唯一，检查是否存在不是 a[0] 倍数的数
    bool found = false;
    for (int i = 1; i < n; i++) {
        if (a[i] % a[0] != 0) {
            found = true;
            break;
        }
    }
    cout << (found ? "YES\n" : "NO\n");
}

---

复杂度分析

• 时间复杂度：$O(n \log n)$，主要由排序贡献
• 空间复杂度：$O(1)$ 或 $O(n)$（取决于是否使用额外数组）

---

示例验证

输入	排序后	判断	输出
$[1,2,3,4,5,6]$		$1\neq2$ → YES	YES
$[3,3,3,3,3]$		全为3的倍数 → NO	NO
$[2,2,3]$		$3\%2=1\neq0$ → YES	YES
$[1,1,2,3,7]$		存在非1倍数 → YES（？实际输出NO，需注意）	NO

注意第4个样例：$[1,1,2,3,7]$，最小值是 $1$，所有数都是 $1$ 的倍数（因为任何数 $\bmod 1 = 0$），所以实际上是 NO。

---

总结

判断条件可以简洁表述为：

• YES 当且仅当：最小值唯一，或者存在一个不是最小值倍数的数
• NO 当且仅当：最小值不唯一，且所有数都是最小值的倍数