Problem:


Score : 500 points

Problem Statement

We have N integers. The i-th number is A_i.

\{A_i\} is said to be pairwise coprime when GCD(A_i,A_j)=1 holds for every pair (i, j) such that 1\leq i < j \leq N.

\{A_i\} is said to be setwise coprime when \{A_i\} is not pairwise coprime but GCD(A_1,\ldots,A_N)=1.

Determine if \{A_i\} is pairwise coprime, setwise coprime, or neither.

Here, GCD(\ldots) denotes greatest common divisor.

Constraints

2 \leq N \leq 10^6

1 \leq A_i\leq 10^6

Input

Input is given from Standard Input in the following format:

N
A_1 \ldots A_N

Output

If \{A_i\} is pairwise coprime, print pairwise coprime; if \{A_i\} is setwise coprime, print setwise coprime; if neither, print not coprime.

Sample Input 1

3
3 4 5

Sample Output 1

pairwise coprime

GCD(3,4)=GCD(3,5)=GCD(4,5)=1, so they are pairwise coprime.

Sample Input 2

3
6 10 15

Sample Output 2

setwise coprime

Since GCD(6,10)=2, they are not pairwise coprime. However, since GCD(6,10,15)=1, they are setwise coprime.

Sample Input 3

3
6 10 16

Sample Output 3

not coprime

GCD(6,10,16)=2, so they are neither pairwise coprime nor setwise coprime.



Sample input:
3
3 4 5


Sample output:
pairwise coprime

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict


def factorization(n):

    arr = defaultdict(int)
    tmp = n
    for i in range(2, int(-(-n**0.5 // 1)) + 1):  # sqrt(n) まで

        # i で割れるだけ割る、を繰り返す
        if tmp % i == 0:
            cnt = 0

            while tmp % i == 0:
                cnt += 1
                tmp //= i

            arr[i] = cnt  # 結果を追加

    if tmp != 1:
        arr[tmp] = 1  # まだ余っていれば追加しておく

    if arr == {}:
        arr[n] = 1  # このブロック、必要か？

    return arr


N = int(sys.stdin.readline().rstrip())
A = [int(x) for x in sys.stdin.readline().rstrip().split()]


pc = True
sp = True

maxlist = factorization(A[0])
minlist = factorization(A[0])

for i in range(1, N):
    d = factorization(A[i])
    for p in maxlist.keys():

        if min(maxlist[p], d[p]) != 0:
            pc = False
        maxlist[p] = max(maxlist[p], d[p])

    for p in minlist.keys():
        minlist[p] = min(minlist[p], d[p])


for p in minlist.keys():
    if minlist[p] != 0:
        sp = False


if pc:
    print("pairwise coprime")
elif sp:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Wrong Answer

Solution code:
import sys
import math
import collections
import bisect
import itertools
import decimal

# import numpy as np

# sys.setrecursionlimit(10 ** 6)
INF = 10 ** 20
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline().rstrip())
ns = lambda: map(int, sys.stdin.readline().rstrip().split())
na = lambda: list(map(int, sys.stdin.readline().rstrip().split()))
na1 = lambda: list(map(lambda x: int(x) - 1, sys.stdin.readline().rstrip().split()))


# ===CODE===


def main():
    n = ni()
    a = na()

    seta = set(a)
    if len(seta) == 1:
        print("not coprime")
        exit(0)


    # 素因数分解　10**12でもOK
    def prime_factorize(n):
        a = set()
        while n % 2 == 0:
            a.add(2)
            n //= 2
        f = 3
        while f * f <= n:
            if n % f == 0:
                a.add(f)
                n //= f
            else:
                f += 2
        if n != 1:
            a.add(n)
        return a

    gcd = [set() for _ in range(n)]
    for i, ai in enumerate(a):
        gcd[i] = prime_factorize(ai)

    total = set()

    pc = True
    for i in range(n):
        flg = True
        for td in gcd[i]:
            if td in total:
                flg = False
                break
            else:
                total.add(td)
        if not flg:
            pc = False
            break

    tc = True
    if len(gcd[0]) == 0:
        tc = True

    for td in gcd[0]:
        flg = True
        for i in range(1, n):
            if td not in gcd[i]:
                flg = False
                break
        if flg:
            tc = False
            break

    if pc:
        print("pairwise coprime")
    elif tc:
        print("setwise coprime")
    else:
        print("not coprime")


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from math import *
n=int(input())
l=list(map(int,input().split()))
l.sort()
g=l[0]
for i in range(1,n):
    g=gcd(g,l[i])
if(g!=1):
    print("not coprime")
else:
    f=0
    p=l[-1]
    for i in range(n-2,-1,-1):
        p*=l[i]
    for i in range(n):
        if(p%(l[i]*l[i])==0):
            f=1
            break
    if(f==1):
        print('setwise coprime')
    else:
        print('pairwise coprime')

Submission status: Wrong Answer

Solution code:
### ----------------
### ここから
### ----------------

import sys
from io import StringIO
import unittest
import copy

def resolve():
    readline=sys.stdin.readline
    n=int(readline())
    arr=list(map(int, readline().rstrip().split()))
    n=len(arr)
    be=[0]*(10**6+1)
    xxx=0
    for i in range(n):
        be[arr[i]]=1
        xxx+=1
    is1=True
    is2=True
    for i in range(2,10**6+1):
        x = i
        found=0
        while x <= 10**6:
            found+=be[x]
            x += i
        if found >= 2:
            is1=False
        if found == xxx:
            is2=False
    if is1==True:
        print("pairwise coprime")
    elif is2==True:
        print("setwise coprime")
    else:
        print("not coprime")

    return

if 'doTest' not in globals():
    resolve()
    sys.exit()

### ----------------
### ここまで 
### ----------------

Submission status: Wrong Answer

Solution code:
import  math

n = int(input())
A = list(map(int, input().split()))
ans = A[0]
flag_for = 0
flag = 0

for i in range(n-1):
    ans = math.gcd(ans, A[i+1])
    if ans != 1:
        flag = 1
    if flag_for == 0:
        for j in range(i+1, n):
            if math.gcd(A[i], A[j]) != 1:
                flag_for = 1
                break

# for i in range(1, n):
#     ans = math.gcd(ans, A[i])
#     if ans != 1:
#         flag = 1

if ans == 1 and flag == 0:
    print('pairwise coprime')
elif ans == 1:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
import math
gcd_list = []
for i,j in zip(a,a[1:]):
    gcd = math.gcd(i,j)
    gcd_list.append(gcd)

g = gcd_list[0]
for gcd in gcd_list[1:]:
    g = math.gcd(g, gcd)

if all([i==1 for i in gcd_list]):
    print('pairwise coprime')
elif g == 1:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Wrong Answer

Solution code:
from math import gcd
def g(a):
    al=len(a)
    if al==2:
        return gcd(a[0],a[1])
    elif al==1:
        return a[0]
    return gcd(g(a[:al//2]),g(a[al//2+1:]))
n=int(input())
a=list(map(int,input().split()))
if g(a)!=1:
    print("not coprime")
    exit()
one=a.count(1)
if len(a)-one>168:
    print("setwise coprime")
    exit()
a=[i for i in a if i!=1]
for i in range(len(a)-1):
    for j in range(i+1,len(a)):
        if gcd(a[i],a[j])!=1:
            print("setwise coprime")
            exit()
print("pairwise coprime")

Submission status: Wrong Answer

Solution code:
from math import gcd, sqrt


def Calc_Divisors(num):
    divisors = []
    for i in range(1, int(sqrt(num)) + 1):
        if num % i == 0:
            if i != 1:
                divisors.append(i)
            if i != num // i:
                divisors.append(num//i)
    # divisors.sort()
    return divisors


def main():
    N = input()
    A = list(map(int, input().split()))

    s_tmp = A[0]
    p_flag = True
    p_dic = [0] * (10**6+1)
    for a in A:
        s_tmp = gcd(s_tmp, a)
        if p_flag:
            tmp = Calc_Divisors(a)
            for t in tmp:
                if p_dic[t] == 0:
                    p_dic.append(t)
                else:
                    p_flag = False
                    continue

    if p_flag:
        print('pairwise coprime')
    elif s_tmp == 1:
        print('setwise coprime')
    else:
        print('not coprime')


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from math import gcd
N = int(input())
A = list(map(int, input().split()))
max_A = max(A)
happend_numbers = [False]*(max_A+1)  # 0~NのN+1個
for a in A:
    happend_numbers[a] = True

if len(A) == len(set(A)):
    for i in range(2, max_A+1):
        true_count = 0
        for j in range(i, max_A+1, i):
            if happend_numbers[j]:
                true_count += 1
        if true_count >= 2:
            break
    else:
        print("pairwise coprime")
        exit()

now = A[0]
for a in A[1:]:
    now = gcd(a, now)
if now == 1:
    print("setwise coprime")
    exit()
print("not coprime")

Submission status: Wrong Answer

Solution code:
import math
N = int(input())
A = list(map(int, input().split()))

tmp = A[0]
for i in range(1, N):
    tmp = math.gcd(tmp, A[i])
print('not coprime')

Submission status: Wrong Answer

Solution code:
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

import fractions
N = int(input())
A = list(map(int, input().split()))
ans = A[0]
primes = [x for (x, y) in factorization(A[0])]
flag = True
for i in range(1, N):
    for p in factorization(A[i]):
        if p not in primes:
            primes.append(p)
        else:
            flag = False
    ans = fractions.gcd(ans, A[i])
if ans == 1:
    if flag:
        print("pairwise coprime")
    else:
        print("setwise coprime")
else:
    print("not coprime")

Submission status: Wrong Answer

Solution code:
import math
from functools import reduce
def make_divisors(n):
  lower_divisors , upper_divisors = [], []
  i = 2
  while i*i <= n:
    if n % i == 0:
      lower_divisors.append(i)
      if i != n // i:
        upper_divisors.append(n//i)
    i += 1
  return lower_divisors + upper_divisors[::-1]
def gcd(*numbers):
  return reduce(math.gcd, numbers)
n=int(input())
a=list(map(int,input().split()))
d={}
flg=0
if gcd(*a)!=1:
  print('not coprime')
else:
  for i in a:
    for j in make_divisors(i):
      if d.get(j,0)==0:
        d[j]=1
      elif flg==0:
        print('setwise coprime')
        flg=1
  if flg==0:
    print('pairwise coprime')

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    input = sys.stdin.buffer.readline
    from math import gcd
    N = int(input())
    A = list(map(int, input().split()))
    g = A[0]

    def factorization(n):
        ret = set()
        temp = n
        for i in range(2, int(-(-n**0.5//1))+1):
            if temp % i == 0:
                cnt = 0
                while temp % i == 0:
                    cnt += 1
                    temp //= i
                ret.add(i)

        if temp != 1:
            ret.add(temp)

        if len(ret) == 0 and n != 1:
            ret.add(n)

        return ret
    flag = False
    s = set()
    for x in A:
        s |= factorization(x)

    if flag:
        print("pairwise coprime")
    elif g == 1:
        print("setwise coprime")

    else:
        print("not coprime")


main()

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
s = set()
for i in a:
    ns = set()
    for j in range(2, 10**3):
        if i%j!=0:
            continue
        while i%j==0:
            i//=j
        ns.add(j)
        if i==1:
            break
    else:
        ns.add(i)
    if len(ns&s)>0:
        break
    s |= ns
else:
    print('pairwise coprime')
    exit(0)

def gcd_base(a, b):
    while b!=0:
        a, b = b, a%b
    return a

def gcd(num_list):
    ans = 0
    for i in num_list:
        ans = gcd_base(ans, i)
    return ans

if gcd(a)==1:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Wrong Answer

Solution code:
from math import gcd

N = int(input())
A = list(map(int, input().split()))
MOD = 10 ** 9 + 7

g = A[0]
for i in range(1, N):
	g = gcd(g, A[i])
	
if g != 1:
	print("not coprime")
else:
	l = A[0]
	prod = A[0]
	for i in range(1, N):
		l = ((l * A[i]) // gcd(l, A[i])) % MOD
		prod = (prod * A[i]) % MOD
		if l != prod:
			print("setwise coprime")
			exit()
	print("pairwise coprime")

Submission status: Wrong Answer

Solution code:
import numpy
n = int(input())
arr = list(map(int,input().split()))
x = 1
for i in range(n-1):
  if all(filter(lambda j: numpy.gcd(arr[i],j) == 1, arr[i+1:])):
      x = 0
      break
    
if x == 0:
  if numpy.gcd.reduce(arr) == 1: print('setwise coprime')
  else: print('not coprime')
else : print('pairwise coprime')

Submission status: Wrong Answer

Solution code:
from functools import reduce
from math import gcd


def primes(n):
    is_prime = [i % 2 != 0 and i % 3 != 0 and i % 5 != 0 and i % 7 != 0 for i in range(n + 1)]
    is_prime[1] = False
    is_prime[2] = is_prime[3] = is_prime[5] = is_prime[7] = True
    for p in range(3, int(n**0.5) + 1, 2):
        if not is_prime[p]:
            continue
        for i in range(p**2, n + 1, p):
            is_prime[i] = False
    return [i for i, p in enumerate(is_prime) if p]


def main():
    n = int(input())
    a = set(int(i) for i in input().split())
    if len(a) < n or reduce(gcd, a) > 1:
        print("not coprime")
        return
    is_prime = [False] * n
    p = primes(max(max(a), 10))
    for i, ai in enumerate(a):
        for pi in p:
            if ai % pi == 0:
                break
        else:
            is_prime[i] = True
    comp = [ai for ai, isp in zip(a, is_prime) if not isp]
    for ci in comp:
        div = set()
        for i in range(2, int(-(-n ** 0.5 // 1)) + 1):
            if ci % i == 0:
                div.add(i)
                div.add(ci // i)
        # print(ci, div, a)
        for d in div:
            if d in a:
                print("setwise coprime")
                return
        a |= div
    print("pairwise coprime")


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    sys.setrecursionlimit(10**6)
    input = sys.stdin.readline
    N = int(input())
    A = [int(x) for x in input().strip().split()]
    maxA = max(A)
    if maxA == 1:
        print('pairwise coprime')
        return
    prime = [i % 2 != 0 for i in range(maxA+1)]
    prime[2] = True
    f = [False] * (maxA+1)
    for i in range(3, int(maxA**.5)+1):
        if prime[i] == False:
            continue
        p = i * 2
        while p <= maxA:
            prime[p] = False
            p += i

    def gcd(x, y):
        if y == 0:
            return x
        return gcd(y, x % y)

    pairwise_coprime = A[0]
    setwise_coprime = A[0]
    for An in A[1:]:
        setwise_coprime = gcd(setwise_coprime, An)
        if setwise_coprime == 1:
            break
    
    for An in A:
        if An == 1:
            continue
        # print('An = {}'.format(An))
        if f[An]:
            break
        elif prime[An]:
            f[An] = True
        else:
            for i in range(2, An // 2 + 1):
                if prime[An]:
                    if f[An]:
                        if setwise_coprime == 1:
                            print('setwise coprime')
                            return
                        else:
                            print('not coprime')
                            return
                    else:
                        f[An] = True
                        break
                if f[An]:
                    if setwise_coprime == 1:
                        print('setwise coprime')
                        return
                    else:
                        print('not coprime')
                        return
                elif An % i == 0:
                    # print('i={}'.format(i))
                    if f[i]:
                        if setwise_coprime == 1:
                            print('setwise coprime')
                            return
                        else:
                            print('not coprime')
                            return
                    f[i] = True
                    while An % i == 0:
                        An //= i
                    if An == 1:
                        break
        # print(f)
    print('pairwise coprime')

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    from math import gcd
    MINFact = [-1] * (10**6 + 10)
    MINFact[0] = 0
    MINFact[1] = 1

    def Eratosthenes(sup: int) -> set:
        primes = [True for i in range(sup+1)]
        primes[0] = False
        primes[1] = False
        for i in range(2, sup+1):
            if sup < i*i:
                break
            if primes[i]:
                MINFact[i] = i
                mul = 2
                while i*mul <= sup:
                    primes[i*mul] = False
                    if MINFact[i*mul] == -1:
                        MINFact[i*mul] = i
                    mul += 1

    def prime_factor(n):
        while n != 1:
            prime = MINFact[n]
            if prime <= 1:
                break
            n %= prime
            B[prime] += 1

    _ = int(input())
    A = [int(i) for i in input().split()]
    g = A[0]
    for a in A:
        g = gcd(g, a)
    Eratosthenes(10**6 + 5)
    B = [0]*(10**6 + 5)
    for a in A:
        prime_factor(a)
    # 素因数分解したのをBにいれる
    # 1より大きいのがあったら gcd != 1 のペアが存在する
    if g != 1:
        print("not coprime")
    elif max(B) <= 1:
        print("pairwise coprime")
    else:
        print("setwise coprime")


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from math import gcd
from itertools import zip_longest, islice

N = int(input())
A = list(map(int, input().split()))

npcf = False
while True:
    B = []
    for x, y in zip_longest(islice(A, 0, len(A)//2), islice(A, len(A)//2, len(A)), fillvalue=1):
        if gcd(x, y) != 1:
            npcf = True
            break
        B.append(x*y)
    if npcf:
        break
    if len(B) == 1:
        break
    A = B

if not npcf:
    print('pairwise coprime')
    exit()

buf = A[0]
for a in A[1:]:
    buf = gcd(buf, a)
if buf == 1:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Wrong Answer

Solution code:
import math

n =int(input())
a= list(map(int,input().split()))

ans = a[0]
A = []

for x in a[1:]:
    ans = math.gcd(ans,x)
    A.append(ans)
#print(ans)
#print(A)

if A.count(1) == len(A):
    print('pairwise coprime')
elif ans == 1:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Wrong Answer

Solution code:
import math
N = int(input())
A = list(map(int, input().split()))
a = A[0]
s = 0
t = 0
for i in range(1,N):
    a = math.gcd(A[i],a)
    b = math.gcd(A[i-1],A[i])
    if b > 1:
        t = 1
if a > 1:
    print("not coprime")
elif t == 1:
    print("setwise coprime")
else:
    print("pairwise coprime")

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3

import sys
from math import gcd
from collections import Counter
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

N = int(input())
A = list(map(int, input().split()))

dup = False
counter = Counter(A)
for val in counter.values():
    if val > 1:
        dup = True


def max_gcd_pair(S):
    # Assumption 1: S is the list of numbers
    # Assumption 2: There are no duplicates in S
    s = set(S)
    m = max(S)
    res = 0
    i = m
    while i > 0:
        a = i
        cnt = 0
        while a <= m: # a maxed at max of the list
            if a in s:
                cnt += 1
            a += i

        if cnt >= 2:  # we have found the result
            res = i
            break

        i = i - 1
    return res


pair = max_gcd_pair(A)
if pair == 1 and not dup:
    print('pairwise coprime')
    sys.exit()

setw = A[0]
for j in range(N):
    setw = gcd(setw, A[j])

if setw == 1:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Wrong Answer

Solution code:
from math import gcd, sqrt, cos, radians, pi, factorial as f
from collections import defaultdict as d

n = int(input())
arr = list(map(int, input().split()))

primes = d(int)

for i in arr:
	
	if i % 2 == 0:
		primes[2] += 1
		while i % 2 == 0:
			i //= 2
	for j in range(3, int(sqrt(i))+1, 2):
		if i % j == 0:
			primes[j] += 1
			while i % j == 0:
				i //= j
	if i > 1:
		primes[i] += 1

count = 0
no = 0	
for i in primes.keys():
	if primes[i] == 1:
		count += 1
	if primes[i] == n:
		no = 1
		
if count == n:
	print("pairwise coprime")
elif not no:
	print("setwise coprime")
else:
	print("not coprime")

Submission status: Wrong Answer

Solution code:
from math import gcd

# 10**3まで素数列挙
N = 1000
L = list(range(2,N+1))
p = list()
while L[0]**2<=N:
    tmp = L[0]
    p.append(tmp)
    L = [e for e in L if e%tmp!=0]
p = p + L


def function(n):
    memo = set()
    for i in p:
        if n % i == 0:
            c = 0
            while n % i == 0:
                c += 1
                n //= i
            memo.add(i)
    if n > 1:
        memo.add(n)
    return memo

n = int(input())
A = list(map(int, input().split()))

# n個の数のgcd
total_gcd = A[0]
for a in A:
    total_gcd = gcd(total_gcd, a)
    if total_gcd == 1:
        break


if total_gcd == 1:  # pairwiseか setwise
    setA = set(A)
    if len(setA) > len(p)+10: # 固有の
        print("setwise coprime")
        exit()
    total = set()
    cnt = 0
    seki = set(p)
    for a in A:
        s = function(a)
        total = total | s
        seki = seki & s
        cnt += len(s)

    if seki == set():  # 全部に共通する素因数はない
        if len(total) != cnt:  # どこかに共通あり
            print("setwise coprime")
        else:
            print("pairwise coprime")

else: # setwiseかnot
    print("not coprime")
    exit()

Submission status: Wrong Answer

Solution code:
from sys import stdin, setrecursionlimit
from collections import Counter, deque, defaultdict
from math import floor, ceil, gcd
from bisect import bisect_left
import random
from itertools import combinations, accumulate
setrecursionlimit(100000)

INF = int(1e10)
MOD = int(1e9 + 7)

def generate_primes(n):
    primes = []
    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False
    for p in range(2, n + 1):
        if is_prime[p]:
            primes.append(p)
            for i in range(p, n + 1, p):
                is_prime[i] = False
    return primes

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])
    if arr==[]:
        arr.append([n, 1])
    return arr

class UnionFind(object):
    def __init__(self, n):
        self.par = [-1] * n
    
    def find(self, x):
        if self.par[x] < 0:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        
        if x == y:
            return False
        else:
            if self.par[x] > self.par[y]:
                x, y = y, x
            self.par[x] += self.par[y]
            self.par[y] = x
            return True

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def size(self, x):
        return -self.par[self.find(x)]

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.par) if x < 0]

    def group_count(self):
        return len(self.roots())

def main():
    from builtins import int, map
    N = int(input())
    A = list(map(int, input().split()))
    primes = generate_primes(max(A) + 1)
    elems = defaultdict(list)

    for ida, a in enumerate(A):
        for (p, pc) in factorization(a):
            elems[p].append(ida)

    uf = UnionFind(N)
    for key in elems:
        lkey = elems[key]
        for i in range(len(lkey) - 1):
            uf.unite(lkey[i], lkey[i + 1])

    flag = True
    for n in range(N):
        if uf.size(n) > 1:
            flag = False
            break

    # 共通gcd
    prod = A[0]
    for k in range(1, N):
        prod = gcd(prod, A[k])
    flag2 = prod == 1

    if flag:
        print("pairwise coprime")
    elif flag2:
        print("setwise coprime")
    else:
        print("not coprime")

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import math

N = int(input())
numbers = list(map(int, input().split()))

for i in range(N-1):
    tmp=math.gcd(numbers[i],numbers[i+1])

Submission status: Wrong Answer

Solution code:
from functools import reduce
from math import gcd 

n = int(input())
A = list(map(int, input().split()))
pr = [True]*(10**6+5)
for a in A:
    vals = [i for i in range(2, a) if a % i == 0]
    for v in vals:
        for i in range(v, 10**6+2, v):
            if not pr[i]:
                break
            pr[i] = False
        else:
            continue
        break
    else:
        continue
    break
else:
    print('pairwise coprime')
    exit()

for a in A:
    if a%2 == 0: continue
    print('setwise coprime')
    exit()
print('not coprime')

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil,pi,factorial
    from operator import itemgetter
    def I(): return int(input())
    def MI(): return map(int, input().split())
    def LI(): return list(map(int, input().split()))
    def LI2(): return [int(input()) for i in range(n)]
    def MXI(): return [[LI()]for i in range(n)]
    def SI(): return input().rstrip()
    def printns(x): print('\n'.join(x))
    def printni(x): print('\n'.join(list(map(str,x))))
    inf = 10**17
    mod = 10**9 + 7
#main code here!
    n=I()
    lis=LI()
    nums=[i for i in range(10**6+1)]
    spf=[-1 for i in range(10**6+1)]
    i=2
    while i<=10**3:
        if spf[i]>=0:
            i+=1
        for j in range(1,(10**6)//i+1):
            if spf[i*j]==-1:
                spf[i*j]=i
        i+=1
    #print(spf)
    dic=defaultdict(lambda :0)
    for i in range(n):
        x=lis[i]
        key=set()
        while x>1:
            u=spf[x]
            x//=u
            key.add(u)
        for z in key:
            dic[z]+=1
    flag=True
    #print(dic)
    for z in dic.keys():
        if dic[z]==n:
            print("not coprime")
            sys.exit()
        if dic[z]>1:
            flag=False
        
    if flag==True:
        print("pairwise coprime")
        sys.exit()
    print("setwise coprime")
                
        
            
        
            
            

            
            
            

    
            
            
            
            
        
        
        
    
        
            
        
if __name__=="__main__":
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
from bisect import bisect_right

import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

def gcd_list(numbers):
    return reduce(math.gcd, numbers)

def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]

P = primes(10**6)

N = int(input())
A = list(map(int, input().split()))

check = [0]*(10**6)
flag = 0
for a in A:
    for i in range(bisect_right(P, a**0.8)):
        if a%P[i] == 0:
            if check[P[i]] == 1:
                flag = 1
            else:
                check[P[i]] = 1
    if flag:
        break

if gcd_list(A) > 1:
    print("not coprime")
elif flag:
    print("setwise coprime")
else:
    print("pairwise coprime")

Submission status: Wrong Answer

Solution code:
import math
n=int(input())
a=list(map(int,input().split()))
mxa=max(a)

def sieve(num):
    input_list = [False if i % 2 == 0 or i % 3 == 0 or i % 5 == 0 else True for i in range(num)]
    input_list[0] = input_list[1] = False
    input_list[2] = input_list[3] = input_list[5] = True
    sqrt = math.sqrt(num)
    for serial in range(3, num, 2):
        if serial >= sqrt:
            return input_list
        for s in range(serial ** 2, num, serial): 
            input_list[s] = False
            
def fact(num):
    arr = []
    temp = num
    for i in range(2, int(-(-num**0.5//1))+1):
        if temp%i==0:
            while temp%i==0:
                temp //= i
            arr.append(i)
    if temp!=1:
        arr.append(temp)
    if arr==[]:
        arr.append(num)
    return arr

flg=True
#prim=sieve(mxa+5)
table=[0]*(mxa+1)
for i in a:
  fc=fact(i)
  for j in fc:
    if table[j]==1:
      flg=False
    table[j]+=1

if flg:
  print("pairwise coprime")
elif n in table:
  print("not coprime")
else:
  print("setwise coprime")

Submission status: Wrong Answer

Solution code:
from math import gcd
def g(a):
    al=len(a)
    if al==2:
        return gcd(a[0],a[1])
    elif al==1:
        return a[0]
    return gcd(g(a[al//2:]),g(a[:al//2+1]))
n=int(input())
a=list(map(int,input().split()))
if g(a)!=1:
    print("not coprime")
    exit()
one=a.count(1)
if len(a)-one>167:
    print("setwise coprime")
    exit()
a=[i for i in a if i!=1]
for i in range(len(a)-1):
    for j in range(i+1,len(a)):
        if gcd(a[i],a[j])!=1:
            print("setwise coprime")
            exit()
print("pairwise coprime")

Submission status: Wrong Answer

Solution code:
import numpy
import collections
n=int(input())
l=list(map(int,input().split()))
num=numpy.gcd(l[0],l[1])
for i in l:
    num=numpy.gcd(num,i)
if num!=1:
    print('not coprime')
else:
    ll=collections.Counter(l)
    if max(ll.values())!=1:
        print('setwise coprime')
    else:
        if len(l)>=8*10**4:
            print('setwise coprime')
        else:
            flag=True
            for i in range(n-1):
                for j in range(i+1,n):
                    if numpy.gcd(l[i],l[j])!=1:
                        flag=False
                        break
            if flag==True:
                print('pairwise coprime')
            else:
                print('setwise coprime')