Serval and Mocha's Array (Codeforces 1789A)
Tags: Math, number theory

Mocha likes arrays, and Serval gave her an array consisting of positive integers as a gift.Mocha thinks that for an array of positive integers $$$a$$$, it is good iff the greatest common divisor of all the elements in $$$a$$$ is no more than its length. And for an array of at least $$$2$$$ positive integers, it is beautiful iff all of its prefixes whose length is no less than $$$2$$$ are good. For example:  $$$[3,6]$$$ is not good, because $$$\gcd(3,6)=3$$$ is greater than its length $$$2$$$.  $$$[1,2,4]$$$ is both good and beautiful, because all of its prefixes whose length is no less than $$$2$$$, which are $$$[1,2]$$$ and $$$[1,2,4]$$$, are both good.  $$$[3,6,1]$$$ is good but not beautiful, because $$$[3,6]$$$ is not good. Now Mocha gives you the gift array $$$a$$$ of $$$n$$$ positive integers, and she wants to know whether array $$$a$$$ could become beautiful by reordering the elements in $$$a$$$. It is allowed to keep the array $$$a$$$ unchanged.

Input: Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1\leq t\leq 500$$$). The description of the test cases follows.The first line of each test case contains a single integer $$$n$$$ ($$$2\leq n\leq 100$$$) — the length of array $$$a$$$.The second line of each test case contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$1\leq a_1,a_2,\ldots,a_n\leq 10^6$$$) — the elements of array $$$a$$$.

Output: For each test case, print Yes if it is possible to reorder the elements in $$$a$$$ to make it beautiful, and print No if not.You can output Yes and No in any case (for example, strings yEs, yes, Yes and YES will be recognized as a positive response).

Note: In the first test case, neither $$$[3,6]$$$ nor $$$[6,3]$$$ are beautiful, so it's impossible to obtain a beautiful array by reordering the elements in $$$a$$$.In the second test case, $$$[1,2,4]$$$ is already beautiful. Keeping the array $$$a$$$ unchanged can obtain a beautiful array.

Sample Inputs:
6
2
3 6
3
1 2 4
3
3 6 1
3
15 35 21
4
35 10 35 14
5
1261 227821 143 4171 1941

Sample Outputs:
No
Yes
Yes
No
Yes
Yes

Solution (Python):
def gcd(x, y):
    if x % y == 0:
        return y
    else:
        return gcd(y, x % y)
t = int(input())
for i in range(t):
    n = int(input())
    a = sorted(set(map(int, input().split())))
    n1 = len(a)
    if n1 == 1:
        if a[0] < 3:
            print('YES')
        else:
            print('NO')
        continue
    d = dict()
    r = False
    for j in range(n1 - 1):
        v = gcd(a[n1 - 1], a[j])
        if v < 3:
            r = True
            break
        if v not in d:
            d[v] = [a[j]]
        else:
            d[v].append(a[j])
    if r == True:
        print('YES')
        continue
    k1 = list(d.keys())
    nk1 = len(k1)
    for j in range(nk1):
        for j1 in range(j + 1, nk1):
            v = gcd(k1[j], k1[j1])
            if v > 2:
                continue
            l1 = d[k1[j]]
            l2 = d[k1[j1]]
            for x1 in l1:
                for x2 in l2:
                    v = gcd(x1, x2)
                    if v < 3:
                        r = True
                        break
                if r == True:
                    break
            if r == True:
                break
        if r == True:
            break
    if r == True:
        print('YES')
    else:
        print('NO')

Solution (Python):
from math import gcd
t = int(input())

def is_good(numlist):
    g = numlist[0]
    for i in range(len(numlist)):
        g = gcd(g, numlist[i])
    return g <= len(numlist)

def can_beautiful(numlist):
    for i in range(len(numlist)):
        for j in range(i, len(numlist)):
            if gcd(numlist[i], numlist[j]) <= 2:
                return 1
    return 0
for i in range(t):
    n = int(input())
    a_list = list(map(int, input().split()))
    if is_good(a_list) == 1:
        if can_beautiful(a_list):
            print('YES')
        else:
            print('NO')
    else:
        print('NO')

Solution (Python):
import math
trynum = int(input())
for i in range(0, trynum):
    listLen = int(input())
    numList = list(map(int, input().split()))
    gcd = numList[0]
    for j in range(0, listLen - 1):
        gcd = math.gcd(gcd, numList[j + 1])
    if gcd <= listLen:
        isGood = 1
    else:
        print('No')
        continue
    br = 0
    for k in range(0, listLen - 1):
        for r in range(k + 1, listLen):
            if math.gcd(numList[k], numList[r]) <= 2:
                print('Yes')
                br = 1
                break
        if br == 1:
            break
    if br == 0:
        print('No')