Codeforces Round 929 (Div. 3) D. Turtle Tenacity: Continual Mods（数学，贪心）

本文主要是介绍Codeforces Round 929 (Div. 3) D. Turtle Tenacity: Continual Mods（数学，贪心），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

给定数组 $a_1,a_2,\dots ,a_n$ ，判断是否有可能将其元素重排为 $b_1,b_2,\dots ,b_n$ ，从而得到 $b_1$ $mod$ $b_2$ $mod$ …$mod$ $b_n$ $\ne$ $0$ 。

这里的 $x$ $mod$ $y$ 表示 $x$ 除以 $y$ 的余数。另外，模运算是从左向右计算的。即 $x$ $mod$ $y$ $mod$ $z$ $=$ $(x$ $mod$ $y)$ $mod$ $z$ 。例如， $2024$ $mod$ $1000$ $mod$ $8$ $=$ $(2024$ $mod$ $1000)$ $mod$ $8$ $=$ $24$ $mod$ $8$ $=$ $0$ 。

输入
输入的第一行包含一个整数 $t(1\le t\le 10^4)$ - 测试用例的数量。

每个测试用例的第一行包含一个整数 $n(2\le n\le 10^5)$。

每个测试用例的第二行包含 $n$ 个整数 $a_1,a_2,\dots ,a_n(1\le a_i\le 10^9)(1\le a_i\le 10^9)$.

所有测试用例的 $n$ 之和不超过 $2\cdot 10^5$ 。

输出
对于每个测试用例，如果可能，则输出 “YES”，否则输出 “NO”。

您可以用任何大小写(大写或小写)输出答案。例如，字符串 “yEs”、“yes”、"Yes "和 "YES "将被识别为肯定回答。

Example
input

8
6
1 2 3 4 5 6
5
3 3 3 3 3
3
2 2 3
5
1 1 2 3 7
3
1 2 2
3
1 1 2
6
5 2 10 10 10 2
4
3 6 9 3

output

YES
NO
YES
NO
YES
NO
YES
NO

乍一拿到这道题可能觉得莫名其妙，因为给定一个数组进行随意的排列能排出来无数种（别管具体多少种，反正会爆）排法，所以这题必定有规律可循（废话）。

那么来思考：最终mod出来的数是不是0究竟取决于谁呢？

• 假如现在有一个最小数为1，后面的数都是大于1的，比如什么 $2$ $5$ $3$ $5$ $2$ $8$ $7$ $4$…，那么最后 $mod$ 得出来是什么呢 ？ 稍微思考一下就知道$1$ $mod$ $2$ $=$ $1$,$1$ $mod$ $5$ $=$ $1$,$1$ $mod$ $3$ $=$ $1$…，到最后 $mod$ 出来肯定还是个 $1$，因为加了前提条件：$1$ 就是这些数里的最小值，并且 $1$ 唯一。当然有别的序列以 $2$ 为最小数且唯一，以 $3$ 为最小数且唯一 … 得到的结论同样还是这样，所以只要序列中有一个唯一的最小值，那么最终得到的模数一定非0 。
• 那如果最小值不唯一呢 ？就比如样例4：1 1 2 3 7。如果直接从前mod到最后一定是0，因为1 mod 1 = 0，在第一步就0了。但是再去看倒数第二个样例 5 2 10 10 10 2，为啥这个就是对的 ？ 假如我们只有2 10 10 10 2，没有第一个 5 ，那么就能得到：不管怎么排，到最后都只能 mod 出来个 0 ，那如果加上 5 ，2 mod 5 = 3，而 3 mod 到最后都不可能是 0 ，因为 3 和其他任何一个数都不是倍数关系，所以如果除了最小值之外如果有任何一个值是和最小值不成倍数的，那么这个序列就一定有一种方法可以排成最终模数不是0 。

来一个 不严谨 的证明:
设最小值为m，那么除了和 $m$ 相同的数之外，能够有的就只有：是 $m$ 的倍数的数，不是 $m$ 的倍数的数。

假如这里有一个序列：

m  1*m  a*m   b*m    e*(m+n)(n < m)

集结所有种类的数，那么我们肯定可以让$e\ast (m+n)$ $mod$ $m$ 得到 $e\ast n$
之后因为其他数都是m的倍数，而 $e\ast n$ 一定不是 $m$ 的倍数，所以 $e\ast n$ $mod$ 其他所有数出来都一定不是 $0$。那么最后得到的模数就一定不为0。

代码：

#include<iostream>
#include<algorithm>
#include<map>
using namespace std;
const int N = 1e5 + 10;int a[N];int main() {int t; cin >> t;while (t--) {int n; cin >> n;bool has_answer = 0;for (int i = 1; i <= n; i++) {cin >> a[i];}sort(a + 1, a + n + 1); //这里找最小值可以直接利用排序if (a[1] == a[2]) {for (int i = 2; i <= n; i++) {if (a[i] % a[1] != 0) {has_answer = 1;break;}}}else {has_answer = 1;}if (has_answer)cout << "YES" << endl;else cout << "NO" << endl;}return 0;
}

这篇关于Codeforces Round 929 (Div. 3) D. Turtle Tenacity: Continual Mods（数学，贪心）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---