Joi has an array $a$ of $n$ positive integers. Koxia wants you to determine whether there exists a positive integer $x > 0$ such that $\gcd(a_i+x,a_j+x)=1$ for all $1 \leq i < j \leq n$.

Here $\gcd(y, z)$ denotes the

greatest common divisor (GCD)

of integers $y$ and $z$.


-----Input-----

Each test consists of multiple test cases. The first line contains a single integer $t$ ($1 \le t \le 100$) — the number of test cases. The description of test cases follows.

The first line of each test case contains an integer $n$ ($2 \leq n \leq 100$) — the size of the array.

The second line of each test case contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \leq a_i \leq {10}^{18}$).

It is guaranteed that the sum of $n$ over all test cases does not exceed $1000$.


-----Output-----

For each test case, output "YES" (without quotes) if there exists a positive integer $x$ such that $\gcd(a_i+x,a_j+x)=1$ for all $1 \leq i < j \leq n$, and "NO" (without quotes) otherwise.

You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.


-----Examples-----

Input
2
3
5 7 10
3
3 3 4
Output
YES
NO


-----Note-----

In the first test case, we can set $x = 4$. This is valid because:

When $i=1$ and $j=2$, $\gcd(a_i+x,a_j+x)=\gcd(5+4,7+4)=\gcd(9,11)=1$.

When $i=1$ and $j=3$, $\gcd(a_i+x,a_j+x)=\gcd(5+4,10+4)=\gcd(9,14)=1$.

When $i=2$ and $j=3$, $\gcd(a_i+x,a_j+x)=\gcd(7+4,10+4)=\gcd(11,14)=1$.

In the second test case, any choice of $x$ makes $\gcd(a_1 + x, a_2 + x) = \gcd(3+x,3+x)=3+x$. Therefore, no such $x$ exists.

Difficulty: MEDIUM_HARD
Tags: Number theory

Mathematics

Complete search
Skill types: Complete search

Starter code:

Solutions:
def prime(x):
	return all((x % i for i in range(2, min(x, int(x ** 0.5) + 5))))
pr = [x for x in range(2, 1001) if prime(x)]
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = sorted(a)
	if any((b[i] == b[i + 1] for i in range(n - 1))):
		print('NO')
		continue
	ok = True
	for x in pr:
		if x > n:
			break
		rm = [False] * x
		for t in a:
			rm[t % x] += 1
		if all((y > 1 for y in rm)):
			ok = False
			break
	print('YES' if ok else 'NO')


T = int(input())
for _ in range(T):
	n = int(input())
	a = sorted(list(map(int, input().split())))
	isSuccess = True
	for i in range(1, n):
		if a[i - 1] == a[i]:
			print('NO')
			isSuccess = False
			break
	if not isSuccess:
		continue
	for x in range(2, int(n // 2) + 1):
		cnt = [0 for i in range(x)]
		for i in range(n):
			cnt[a[i] % x] += 1
		isLowThan2 = False
		for i in range(x):
			if cnt[i] < 2:
				isLowThan2 = True
		if not isLowThan2:
			print('NO')
			isSuccess = False
			break
	if isSuccess:
		print('YES')


k = int(input())
p = [2]
for i in range(3, 102):
	t = True
	for j in range(2, i):
		if i % j == 0:
			t = False
			break
	if t:
		p.append(i)
for _ in range(k):
	n = int(input())
	lst = [int(i) for i in input().split()]
	e = sum([1 for i in lst if i % 2 == 0])
	o = len(lst) - e
	if len(lst) != len(list(set(lst))):
		print('NO')
	else:
		t = True
		for j in p:
			f = [0] * j
			for (i, el) in enumerate(lst):
				f[el % j] += 1
			if min(f) >= 2:
				t = False
				break
		if t:
			print('YES')
		else:
			print('NO')


P = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]
for s in [*open(0)][2::2]:
	a = [*map(int, s.split())]
	if len(a) != len({*a}):
		print('NO')
		continue
	for p in P:
		cnt = [0] * p
		for x in a:
			cnt[x % p] += 1
		if min(cnt) >= 2:
			print('NO')
			break
	else:
		print('YES')


from itertools import groupby
print(*map(lambda a: ['NO', 'YES'][len(a) == len({*a}) and all((sum((1 for (_, v) in groupby(sorted((x % p for x in a))) if len([*v]) > 1)) < p for p in (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97)))], map(lambda s: [*map(int, s.split())], [*open(0)][2::2])), sep='\n')


def solve(a, n):
	a = sorted(a)
	for j in range(n - 1):
		if a[j] == a[j + 1]:
			print('NO')
			return
	for m in range(2, int(n / 2) + 3):
		mod = [0] * m
		for a_i in a:
			mod[a_i % m] += 1
		if min(mod) > 1:
			print('NO')
			return
	print('YES')
T = int(input())
for t in range(T):
	s = input()
	n = int(s)
	a = [int(si) for si in input().split()]
	solve(a, n)


for _ in range(int(input())):
	x = int(input())
	y = list(map(int, input().split()))
	z = set(y)
	primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83]
	countodd = 0
	counteven = 0
	for element in y:
		if element % 2 == 0:
			counteven += 1
		else:
			countodd += 1
	if min(countodd, counteven) == 2 or len(y) != len(z):
		print('NO')
	else:
		flag = False
		for p in primes:
			if flag:
				break
			L = [0] * p
			for element in y:
				rem = element % p
				L[rem] += 1
			alpha = min(L)
			if alpha >= 2:
				flag = True
		if flag:
			print('NO')
		else:
			print('YES')


import sys

def fn(a, l):
	repeat_check = set(a)
	if len(repeat_check) != l:
		return 'NO'
	for i in range(2, l):
		mask = [0] * i
		for item in a:
			mask[item % i] += 1
		if min(mask) >= 2:
			return 'NO'
	return 'YES'
input = sys.stdin.readlines()
for i in range(int(input[0].strip('\n'))):
	l = int(input[2 * i + 1].strip('\n'))
	a = [int(x) for x in input[2 * i + 2].strip('\n').split(' ')]
	print(fn(a, l))


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	if len(set(a)) != n:
		print('NO')
	else:
		flag = False
		for i in range(2, n // 2 + 1):
			ost = [0] * i
			for j in a:
				ost[j % i] += 1
			ans = 0
			for j in ost:
				if j > 1:
					ans += 1
			if ans == i:
				flag = True
				break
		if flag:
			print('NO')
		else:
			print('YES')


tests = int(input())
for i in range(tests):
	length = int(input())
	arr = list(map(int, input().split()))
	ans = 'YES'
	if length != len(set(arr)):
		ans = 'NO'
	else:
		for j in range(2, length // 2 + 1):
			freq = [0] * j
			for k in arr:
				rem = k % j
				freq[rem] += 1
			if min(freq) >= 2:
				ans = 'NO'
	print(ans)


from itertools import groupby
print(*map(lambda a: ['NO', 'YES'][len(a) == len({*a}) and all((sum((1 for (_, v) in groupby(sorted((x % p for x in a))) if len([*v]) > 1)) < p for p in (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47)))], map(lambda s: [*map(int, s.split())], [*open(0)][2::2])), sep='\n')


t = int(input(''))
mx = 0
inputs = []
arrays = []
for _ in range(t):
	n = int(input(''))
	a = [int(x) for x in input('').split(' ')]
	inputs.append(n)
	arrays.append(a)
	mx = max(mx, n // 2)
p = [1] * (mx + 1)
p[0] = 0
p[1] = 0
i = 2
while i * i <= mx:
	if p[i]:
		j = i * i
		while j <= mx:
			p[j] = 0
			j += i
	i += 1
v = [0] * (mx + 1)
for s in range(t):
	n = inputs[s]
	a = arrays[s]
	h = set(a)
	good1 = len(h) == len(a)
	good2 = True
	for i in range(n // 2 + 1):
		if p[i]:
			for x in a:
				v[x % i] += 1
			good3 = False
			for x in range(i):
				if v[x % i] <= 1:
					good3 = True
					break
			for x in a:
				v[x % i] -= 1
			if not good3:
				good2 = False
				break
	print(['NO', 'YES'][good1 and good2])


T = int(input())
for _ in range(T):
	n = int(input())
	a = list(map(int, input().split()))
	if len(a) != len({*a}):
		print('NO')
		continue
	ans = True
	for i in range(2, 55):
		cnt = [0] * i
		for x in a:
			cnt[x % i] += 1
		if min(cnt) >= 2:
			ans = False
	print('YES' if ans else 'NO')


from collections import Counter as ct
from collections import defaultdict as dd
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	f = 1
	c = ct(l)
	for x in c.values():
		if x >= 2:
			f = 0
			break
	for x in range(2, n + 1):
		d = dd(int)
		for y in l:
			d[y % x] += 1
		if len(d.keys()) == x:
			f1 = 0
			for y in d.values():
				if y == 1:
					f1 = 1
					break
			if f and f1 == 0:
				f = 0
		if f == 0:
			break
	if f:
		print('YES')
	else:
		print('NO')


M = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

def g(X):
	for j in X:
		if j < 2:
			return False
	return True

def f(L, n):
	x = 0
	while x < 25 and M[x] <= n // 2 + 1:
		x += 1
	for i in range(x):
		c = M[i]
		S = [0] * c
		for b in L:
			v = b % c
			S[v] += 1
		if g(S):
			return 'NO'
	L.sort()
	for i in range(n - 1):
		if L[i] == L[i + 1]:
			return 'NO'
	return 'YES'
n = int(input())
for i in range(n):
	x = int(input())
	L = list(map(int, input().split()))
	print(f(L, x))


from collections import defaultdict
k = int(input())
primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53]
for _ in range(k):
	_ = input()
	ar = list(map(int, input().split()))
	ost = defaultdict(lambda : defaultdict(int))
	if len(ar) > len(set(ar)):
		print('NO')
		continue
	for x in ar:
		for pr in primes:
			ost[pr][x % pr] += 1
	glob = False
	for pr in primes:
		if pr * 2 > len(ar):
			break
		if len(ost[pr]) < pr:
			continue
		flag = False
		for x in ost[pr]:
			if ost[pr][x] <= 1:
				flag = True
				break
		if not flag:
			glob = True
			break
	if glob:
		print('NO')
	else:
		print('YES')


primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	if len(set(a)) != len(a):
		print('NO')
		continue
	cnt = {p: {} for p in primes}
	for x in a:
		for p in primes:
			if x % p not in cnt[p]:
				cnt[p][x % p] = 0
			cnt[p][x % p] += 1
	for p in primes:
		if len(cnt[p]) == p and all((x > 1 for x in cnt[p].values())):
			print('NO')
			break
	else:
		print('YES')


import os
import math
import collections
import bisect
import functools
import itertools
import heapq

def solve(a, n):
	if len(set(a)) != n:
		return 'NO'
	if n == 2:
		return 'YES'
	a.sort()
	for i in range(2, 101):
		c = [0] * i
		for j in a:
			c[j % i] += 1
		if min(c) >= 2:
			return 'NO'
	return 'YES'
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	print(solve(a, n))


from typing import List
from math import gcd

def exists_x(k, n, l):
	v = [0] * k
	for i in range(n):
		v[l[i] % k] += 1
	for i in range(k):
		if v[i] <= 1:
			return True
	return False
t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	l.sort()
	ans = 'YES'
	for i in range(1, n):
		if l[i] == l[i - 1]:
			ans = 'NO'
			break
	if ans == 'NO':
		print('NO')
	else:
		temp = True
		final = 'YES'
		for i in range(2, n + 1):
			temp = exists_x(i, n, l)
			if temp == False:
				final = 'NO'
				break
		if final == 'NO':
			print('NO')
		else:
			print('YES')


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	wefucked = 'YES'
	for i in range(2, n):
		cnt = [0] * i
		for j in range(n):
			cnt[a[j] % i] += 1
		if min(cnt) >= 2:
			wefucked = 'NO'
			break
	for i in range(n):
		for l in range(i + 1, n):
			if a[i] == a[l]:
				wefucked = 'NO'
				break
	print(wefucked)


import sys
T = int(sys.stdin.readline().strip())
for t in range(0, T):
	n = int(sys.stdin.readline().strip())
	a = list(map(int, sys.stdin.readline().strip().split()))
	ans = True
	if len(set(a)) != n:
		ans = False
	for i in range(2, n):
		c = set()
		d = set()
		for x in a:
			if x % i in c:
				d.add(x % i)
			c.add(x % i)
		if len(d) == i:
			ans = False
	if ans:
		print('YES')
	else:
		print('NO')


t = int(input())
count = [[0] * 51 for _ in range(51)]
while t > 0:
	for i in range(51):
		for j in range(51):
			count[i][j] = 0
	n = int(input())
	A = list(map(int, input().split()))
	ans = True
	for i in range(n):
		for j in range(i + 1, n):
			if A[j] == A[i]:
				ans = False
				break
		if ans == False:
			break
	if ans:
		for i in A:
			for j in range(2, 51):
				count[j][i % j] += 1
	if ans:
		for i in range(2, 51):
			ans = False
			for j in range(i):
				if count[i][j] < 2:
					ans = True
					break
			if ans == False:
				break
	if ans:
		print('YES')
	else:
		print('NO')
	t -= 1


from collections import defaultdict
t = int(input())
for i in range(t):
	n = int(input())
	a = [int(x) for x in input().split()]
	if n != len(set(a)):
		print('NO')
		continue
	fail = 0
	for mod in range(2, 100):
		d = defaultdict(lambda : 0)
		for i in a:
			d[i % mod] += 1
		exit = 0
		for j in range(mod):
			if d[j] < 2:
				exit = 1
				continue
		if exit == 1:
			continue
		fail = 1
		break
	if fail == 1:
		print('NO')
	else:
		print('YES')


T = int(input())
prime = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
for t in range(T):
	n = int(input())
	a = list(map(int, input().split()))
	cnt = {}
	flag = True
	for k in prime:
		cnt[k] = set()
		for i in range(n - 1):
			for j in range(i + 1, n):
				if (a[i] - a[j]) % k == 0:
					cnt[k].add(a[i] % k)
		if len(cnt[k]) == k:
			flag = False
	if len(set(a)) == n and flag:
		print('YES')
	else:
		print('NO')