题解 CF1770C【Koxia and Number Theory】

显然，如果存在 \(a_i=a_j\)，则一定无解。

否则，考虑每一个 \(2\sim 50\) 的正整数 \(k\)，如果原数组每个数对 \(k\) 取模后，每种余数都出现至少两次，则无解。因为此时无论如何选取 \(x\)，都至少有两个数是 \(k\) 的倍数。

下面证明充分性。\(k > 50\) 的情况是无意义的，因为至少需要 \(2k > n\) 个数才能无解。对于每一个 \(k\)，找到一个数 \(y\) 使得对 \(k\) 取模余 \(y\) 的数不超过一个，那么 \(x\equiv -y\pmod{k}\) 的 \(x\) 均符合题意。由于 \(k\) 有有限个，可以使用中国剩余定理解得 \(x\)。

// Problem: Koxia and Number Theory
// Contest: Codeforces
// URL: https://m2.codeforces.com/contest/1770/problem/C
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

//By: OIer rui_er
#include <bits/stdc++.h>
#define rep(x,y,z) for(ll x=(y);x<=(z);x++)
#define per(x,y,z) for(ll x=(y);x>=(z);x--)
#define debug(format...) fprintf(stderr, format)
#define fileIO(s) do{freopen(s".in","r",stdin);freopen(s".out","w",stdout);}while(false)
using namespace std;
typedef long long ll;
const ll N = 105;

ll T, n, a[N], cnt[N];
template<typename T> void chkmin(T& x, T y) {if(x > y) x = y;}
template<typename T> void chkmax(T& x, T y) {if(x < y) x = y;}

int main() {
	for(scanf("%lld", &T); T; T--) {
		scanf("%lld", &n);
		rep(i, 1, n) scanf("%lld", &a[i]);
		sort(a+1, a+1+n);
		ll m = unique(a+1, a+1+n) - a - 1;
		if(m < n) puts("NO");
		else {
			ll ok = 1;
			rep(mod, 2, 50) {
				rep(i, 0, mod-1) cnt[i] = 0;
				rep(i, 1, n) ++cnt[a[i]%mod];
				ll now = 0;
				rep(i, 0, mod-1) now |= cnt[i] <= 1;
				ok &= now;
			}
			puts(ok ? "YES" : "NO");
		}
	}
	return 0;
}