Koxia and Number Theory (Codeforces 1770C)
Tags: Math, chinese remainder theorem

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.

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.

Sample Inputs:
2
3
5 7 10
3
3 3 4

Sample Outputs:
YES
NO

Solution (Python):
import math

def is_prime(num):
    if num < 2:
        return False
    for i in range(2, int(num ** 0.5) + 1):
        if num % i == 0:
            return False
    return True

def check(n, list2):
    list1 = []
    for i in range(0, n):
        list1.append(0)
    for i in range(2, n // 2 + 1):
        if is_prime(i):
            for j in range(0, n):
                list1[list2[j] % i] += 1
            fl = 0
            for j in range(0, i):
                if list1[j] <= 1:
                    fl = 1
                list1[j] = 0
            if fl == 0:
                return 'NO'
    return 'YES'
t = int(input())
while t:
    t -= 1
    n = int(input())
    str = input()
    array = str.split(' ')
    for i in range(0, n):
        array[i] = int(array[i])
    flag = 0
    dict = {}
    for i in range(0, n):
        for j in range(i + 1, n):
            if array[i] == array[j]:
                flag = 1
                break
        if flag == 1:
            break
    if flag == 1:
        result = 'NO'
    else:
        result = check(n, array)
    print(result)

Solution (Python):
t = int(input())
for _ in range(t):
    a = int(input())
    b = list(map(int, input().split()))
    ans = 1
    if len(set(b)) != a:
        ans = 0
    sushu = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59]
    qq = [0] * 50
    for i in range(15):
        if ans == 0:
            break
        for j in range(sushu[i]):
            qq[j] = 2
        for l in b:
            j = l % sushu[i]
            qq[j] = qq[j] - 1 if qq[j] - 1 > 0 else 0
        if sum(qq) == 0:
            ans = 0
        qq = [0] * 50
    if ans == 1:
        print('YES')
    else:
        print('NO')

Solution (Python):
def sieve_of_eratosthenes(n):
    primes = [True] * (n - 1)
    primes_list = []
    for i in range(2, n + 1):
        if primes[i - 2]:
            primes_list.append(i)
            for x in range(i ** 2, n + 1, i):
                primes[x - 2] = False
    return primes_list
primes = sieve_of_eratosthenes(120)

def number(arr):
    if len(arr) != len(set(arr)):
        return 'no'
    for prime in primes:
        compartments = {i: 0 for i in range(prime)}
        for element in arr:
            compartments[element % prime] += 1
        if min(compartments.values()) > 1:
            return 'no'
    return 'yes'
testcases = range(int(input()))
for case in testcases:
    input()
    print(number([int(i) for i in input().split(' ')]))