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
import math

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

tin=lambda : map(int, input().split())
lin=lambda : list(tin())
mod=1000000007

#+++++

def gcd(a, b):
	return math.gcd(a, b)
	
def is_pc(al):
	mm=((10**6)+5)
	dd = [0]* mm
	kk = [-1]* mm
	
	for v in al:
		dd[v] = 1
	
	for i, _ in enumerate(kk):
		if i <= 1:
			continue
		if kk[i]==-1:
			n=1
			nd = 0
			while i*n < mm:
				kk[i*n]=1
				nd += dd[i*n]
				n+=1
		if nd >= 2:
			return False
	return True

def main():
	n = int(input())
	#b , c = tin()
	#s = input()	
	al = lin()
	
	pc = 'pairwise coprime'
	sc = 'setwise coprime'
	nc = 'not coprime'
	if is_pc(al):
		return pc
	v=al[0]
	for vv in al:
		v = gcd(v, vv)
	if v == 1:
		return sc
	return nc
	
				
		
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Wrong Answer

Solution code:
from math import gcd

def primes(n,als):
    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
        cnt = 0
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
            if als[j]: cnt += 1
        if cnt >= 2:
            return False
    else:
        return True


def main():
    n = int(input())
    al = list(map(int, input().split()))
    als = [False]*(10**6+1)
    for a in al:
        if als[a]:
            break
        als[a] = True
    else:
        ans = primes(10**6,als)
        if ans: 
            print('pairwise coprime')
            exit()

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


    # no_flag = False
    # for a in al:
    #     for p in ps:
    #         if a%p == 0:
    #             if p in pset:
    #                 no_flag = True
    #                 break
    #             else:
    #                 pset.add(p)
    #     if no_flag:
    #         break
    # else:
    #     print('pairwise coprime')
    #     exit()

    # pset = set()
    # for p in ps:
    #     if al[0]%p == 0:
    #         pset.add(p)

    # for a in al[1:]:
    #     apset = set()
    #     for p in ps:
    #         if a%p == 0:
    #             apset.add(p)
    #     pset = pset&apset
    #     if len(pset) == 0:
    #         print('setwise coprime')
    #         break
    # else:
    #     print('not coprime')



if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())
a = [int(x) for x in input().split()]
import math
b = 0
if N <= 1000:
    for i in range(N-1):
        for j in range(i+1,N):
            m = math.gcd(a[i],a[j])
            if m != 1:
                b = 1
    if b == 0:
        print("pairwise coprime")
        exit()
ans = a[0]
for i in range(1,N):
    ans = math.gcd(ans,a[i])
if ans == 1:
    print("setwise coprime")
else:
    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 random

N = int(input())
# A_s = list(map(int, input().split()))
A_s = [(i+1)*2 for i in range(N//2)]
pc = True
sc = True
M = {}
MAX = 0

for i,A in enumerate(A_s):
    for p in factorization(A):
        if p[0] == 1:
            continue
        if p[0] in M:
            # print()
            M[p[0]] += 1
            pc = False
        else:
            M[p[0]] = 1
        MAX = max(MAX, M[p[0]])
    if not pc and MAX <= i:
        break
else:
    sc = False

if pc:
    print('pairwise coprime')
elif sc:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Wrong Answer

Solution code:
from math import gcd
def lcm(a):
    x = a[0]
    for i in range(1, len(a)):
        x = (x * a[i]) // gcd(x, a[i])
    return x

n = int(input())
a = list(map(int, input().split()))
lenn = n
na = a
flag = 0
for i in range(n):
    templ = []
    for j in range(0, lenn, 2):
        if(j + 1 >= lenn):
            templ.append(a[j])
        else:
            temp = gcd(a[j], a[j+1])
            if(temp == 1):
                templ.append(a[j]*a[j+1]//temp)
                flag = 1
            else:
                ans = na[0]
                for k in range(1, n):
                    ans = gcd(ans, na[k])
                if(ans == 1):
                    flag = 1
                else:
                    flag = 0
                break
    a = templ
    lenn = len(templ)
    if(lenn == 1):
        flag = 2
        break
if(flag == 2):
    print("pairwise coprime")
elif(flag == 1):
    print("setwise coprime")
else:
    print("not comprime")

Submission status: Wrong Answer

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

A = sorted(A,reverse = True)
prime = [0] * (10**6+1)
ans = 'pairwise coprime'

for a in A:
  if prime[a]:
    ans = 'setwise coprime'
    continue
  else:
    prime[a] += 1
    if a%2==0:
      if prime[2]:
        ans = 'setwise coprime'
      prime[2] += 1
      a//=2
      if (prime[a])and(a!=2):
        ans = 'setwise coprime'
      prime[a] += 1
    
    for i in range(3,int((a)**(1/2))+1,2):
      if a%i==0:
        if prime[i]:
          ans = 'setwise coprime'
        prime[i] += 1
        
if max(prime[2:])==N:
  print('not coprime')
else:
  print(ans)

Submission status: Wrong Answer

Solution code:
import itertools
import collections
def prime_factor_table(n):
    table = [0] * (n + 1)
    
    for i in range(2, n + 1):
        if table[i] == 0:
            for j in range(i + i, n + 1, i):
                table[j] = i
    
    return table

def prime_factor(n, prime_factor_table):
    prime_count = dict()
    
    while prime_factor_table[n] != 0:
        prime_count[prime_factor_table[n]] = 1
        n //= prime_factor_table[n]
    prime_count[n] = 1
    
    return prime_count

pp = prime_factor_table(10**6)
#n = 18
#y = prime_factor(n, pp)
#print(y)
N, = map(int, input().split())
X = list(map(int, input().split()))
d = dict()
f = 0
for x in X:
    y = prime_factor(x, pp)
#    print(y)
    for k in y:
        if k in d:
            f = 1
            d[k] += 1
        else:
            d[k] = 1
#            continue
#        d.add(k)
#    if f:
#        break
if f:
    m = 0
#    print(d)
    for k in d:
        m = max(m, d[k])
    if m != N:
        print("setwise coprime")
    else:
        print("not coprime")
else:
    print("pairwise coprime")

Submission status: Wrong Answer

Solution code:
import math

N = int(input())

A = list(set(list(map(int, input().split()))))
A.sort()
gcdAll = A[0]
isPairwise = True
if len(A) != N:
    isPairwise = False

if len(A) > (10**6/2):
    gcdAll = 0
    isPairwise = False
else:
    for j in range(1, len(A)):
        gcdAll = math.gcd(gcdAll, A[j])
        if not isPairwise:
            continue
        for i in range(0, j):
            gcdNow = math.gcd(A[i], A[j])
            if gcdNow != 1:
                isPairwise = False
                break

if isPairwise:
    print('pairwise coprime')
elif gcdAll == 1:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Wrong Answer

Solution code:
ma = lambda :map(int,input().split())
lma = lambda :list(map(int,input().split()))
tma = lambda :tuple(map(int,input().split()))
ni = lambda:int(input())
yn = lambda fl:print("Yes") if fl else print("No")
import collections
import itertools
import random
def factorize(n):
    b = 2
    fct = []
    while b * b <= n:
        cnt =0
        while n % b == 0:
            n //= b
            cnt +=1
        if cnt >=1:
            fct.append((b,cnt))
        b = b + 1
    if n > 1:
        fct.append((n,1))
    return fct
def solve():
    n = ni()
    A = lma()
    d=collections.Counter()
    r = random.random()
    if n==10**6 and r<0.5:
        print("setwise coprime")
        exit()

    for i in range(n):
        a = A[i]
        fct = factorize(a)
        for fc,cnt in fct:
            d[fc]+=1
            if d[fc]==n:
                break

    f1=True # pp or sp
    f2=True # sp or other
    for num,cnt in d.items():
        if cnt==n:
            f2=False #other
            break
        else:
            if cnt==1:
                pass
            else:
                f1=False
    if f2==False:
        print("not coprime")
        exit()
    elif f1 and f2:
        print("pairwise coprime")
    elif f1==False:
        print("setwise coprime")
solve()

Submission status: Wrong Answer

Solution code:
def gcd(a,b):
  if b==0:
    return a
  else:
    return gcd(b,a%b)
n=int(input())
l=list(map(int,input().split())) 
c=0
for i in range(0,n):
  t=l[i%n]
  y=l[(i+1)%n]
  s=min(t,y)
  p=max(t,y)
  f=gcd(p,s)
  if f==1:
      c=c+1
r=0
z=0
if c==3:
    print('pairwise  coprime')
else:
    f=l[0]
    y=l[1]
    a=max(f,y)
    b=min(f,y)
    r=gcd(a,b)
    for w in range(2,len(l)):
        r=gcd(r,l[w])
        if r!=1:
            print('not coprime')
            z=1
            break
if z==0:
  print('setwise coprime')

Submission status: Wrong Answer

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

g = 0
for a in A:
    g = gcd(g,a)
if g > 1:
    print('not coprime')
    exit()

sa = set(A)
if len(sa) < N:
    print('setwise coprime')
    exit()

MAXN = 10**6+10
sieve = [0,0] + [1]*MAXN
p = 2
small_primes = []
while p*p <= MAXN:
    if sieve[p]:
        small_primes.append(p)
        c = 0
        if p in sa: c += 1
        for q in range(2*p,MAXN+1,p):
            sieve[q] = 0
            if q in sa:
                c += 1
                if c > 1:
                    print('setwise coprime')
                    exit()
    p += 1

st = set()
for a in A:
    for p in small_primes:
        while a%p==0:
            a //= p
        if a==1: break
    else:
        assert a > 1000 and sieve[a]
        if a in st:
            print('setwise coprime')
            exit()
        st.add(a)

print('pairwise coprime')

Submission status: Wrong Answer

Solution code:
from math import gcd
from collections import defaultdict
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 [a[0] for a in arr]

N = int(input())
A = sorted([int(i) for i in input().split()])
dict_A = defaultdict(int)
dep_flag = False
for a in A:
  dict_A[a] += 1
  if a != 1 and dict_A[a] >= 2:
    dep_flag=True
if dep_flag == False:  
  all_flag = True
  devisors = set()
  for n in range(N-1):
      if n == 0:
          g = gcd(A[n],A[n+1])
      else:
          g = gcd(A[n+1],g)
      temp = factorization(A[n])
      if temp == [1]:
        pass
      else:
        for t in temp:
            if t in devisors:
                all_flag=False
            else:
                devisors.add(t)
  if all_flag and g == 1:
      print('pairwise coprime')
  elif g==1:
      print('setwise coprime')
  else:
      print('not coprime')
      print(g)
else:
    print('not coprime')

Submission status: Wrong Answer

Solution code:
import numpy as np

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

gx=list()

jud=0

for i in range(n):
    j=1
    while True:
        if i+j>=n:
            break
        elif np.gcd(a[i],a[i+j])!=1:
            jud=1
            break
        j+=1
    else:
        continue
    break

if jud==0:
    print("pairwise coprime")
elif np.gcd.reduce(a)==1:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Wrong Answer

Solution code:
from fractions import gcd

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

x = 1
result = []
for i in range(len(arr)):
    y = gcd(arr[i], x)
    result.append(y)
    x = x * arr[i] // y

if result.count(1) == len(arr):
    print("pairwise coprime")
elif result[1:].count(result[1]) == len(arr) - 1:
    print("not coprime")
else:
    print("setwise coprime")

Submission status: Wrong Answer

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7


def main():
    N = int(readline())
    A = list(map(int, readline().split()))
    setwise = True
    pairwise = True
    primes = [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, 101, 103,
              107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223,
              227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347,
              349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463,
              467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607,
              613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743,
              751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883,
              887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997]
    for p in primes:
        if not setwise and not pairwise:
            break
        tmp = 0
        for a in A:
            if a % p == 0:
                tmp += 1
        if tmp >=2:
            pairwise = False
            if tmp == N:
                setwise = False
        else:
            continue

    if pairwise:
        print('pairwise coprime')
    else:
        if setwise:
            print('setwise coprime')
        else:
            print('not coprime')


if __name__ == '__main__':
    main()

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=sum(be)
    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
from functools import reduce

def gcd_lis(num_lis):
    return reduce(math.gcd, num_lis)

N = int(input())
lis = list(map(int, input().split()))
c1 = True
c2 = True
for i in range(N-1):
  if math.gcd(lis[i], lis[i+1]) != 1:
    c1 = False

if gcd_lis(lis) != 1:
  c2 = False

if c1:
  print("pairwise coprime")
elif c2:
  print("setwise coprime")
else:
  print("not coprime")

Submission status: Wrong Answer

Solution code:
from functools import reduce
from itertools import combinations
from math import gcd


def func(A):
    is_A = [False] * (10**6+1)
    for a in A:
        is_A[a] = True
    if all(x < 1 for x in is_A[2:]):
        return False
    n = 0
    for i in range(2, 10**6+1, 2):
        if is_A[i]:
            n += 1
    if n > 1:
        return False
    for i in range(3, 10**6+1, 2):
        n = 0
        for j in range(i, 10**6+1, i):
            if is_A[j]:
                n += 1
        if n > 1:
            return False
    return True


def solve():
    N = int(input())
    A = list(map(int, input().split()))
    if func(A):
        # if not all(gcd(i, j)==1 for i, j in combinations(A, 2)):
        #     raise NameError
        print('pairwise coprime')
    elif reduce(gcd, A) == 1:
        print('setwise coprime')
    else:
        print('not coprime')
    

if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
from collections import Counter
import sys
import numpy as np
n = int(input())
ls = list(map(int,input().split()))
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
            for _ in range(cnt):
                arr.append(i)

    if temp!=1:
        arr.append(temp)

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

    return arr
if len(list(set(ls))) != len(ls):
    print("not coprime")
    sys.exit()
c = Counter(ls)
s = list(set(ls))
if np.gcd.reduce(ls) == 1:
    fi = [True]*(10**6+1)
    for y in s:
        l = list(set(factorization(y)))
        l.sort()
        for q in l:
            u = q * 2
            while u <= 10**6:
                if u in s and u > y:
                    fi[u] = False
                u += q
    cnt = 0
    for z in ls:
        if fi[z] == True:
            cnt += 1
    if cnt == len(ls):
        print("pairwise coprime")
    else:
        print("setwise coprime")
else:
    print("not coprime")

Submission status: Wrong Answer

Solution code:
import math
N = int(input())
A = [int(x) for x in input().split()]
P = [2]
for L in range(3, 1000, 2): 
    if all(L % L2 != 0 for L2 in P):  
        P.append(L)
lst = [0] * len(P)
for i, p in enumerate(P):
    cnt = 0
    for a in A:
        cnt += a % p == 0
    lst[i] = cnt
tmp = max(lst)
if tmp == 1:
    print('pairwise coprime')
elif tmp == N:
    print('not coprime')
else:
    print('setwise coprime')

Submission status: Wrong Answer

Solution code:
import sys
import resource
from collections import defaultdict

s=set()
sys.setrecursionlimit(100000)

def gcd(a,b):
    if a%b==0: return b
    return gcd(b,a%b)

i,k=2,10**6
pri=set()
while k>=i*i:
    while k%i==0:
        k//=i
        pri.add(i)
    i+=1
if k!=1: pri.add(k)

n=int(input())
a=list(map(int,input().split()))
visi=set()
s=a[0]
flag=1
for i in a:
    s=gcd(s,i)
    for c in pri:
        if i%c==0:
            if c in visi:
                flag=0
                break
            visi.add(c)
if flag: print("pairwise coprime")
elif s==1: print("setwise coprime")
else: print("not coprime")

Submission status: Wrong Answer

Solution code:
import math
import copy
from functools import reduce

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

for i in range(2, a_list[n - 2] + 1):
    damy = copy.deepcopy(a_list)
    damy = list(map(lambda x: x % i, damy))
    damy.sort()
    if damy[0] == 0 and damy[1] == 0:
        if reduce(math.gcd, a_list) == 1:
            print("setwise coprime")
            exit()
        else:
            print("not coprime")
            exit()
print("pairwise coprime")

Submission status: Wrong Answer

Solution code:
from sys import stdin,stdout
from math import gcd
n=int(stdin.readline())
a=list(map(int,stdin.readline().split()))
s=set(a)
if len(s)<n:
    print('not coprime')
    exit(0)
p=2;d={}
N=max(a)+2
primes=[1]*N;not_pairwise=0
vis=set()
while p*p<=N:
    if primes[p]:
        for mul in range(p,N,p):
            primes[mul]=0
            if mul in s and mul not in vis:
                vis.add(mul)
                d[p]=d.get(p,0)+1
                if d[p]>=2:not_pairwise=1;break;
        if not_pairwise:break
    p+=1
g=a[0]
for v in a:
    g=gcd(g,v)
if not_pairwise==0:print('pairwise coprime')
elif g==1:print('setwise coprime')
else:print('not coprime')

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int, input().split()))
A=sorted(A)
import math
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
if A==[1]*N:
  print('pairwise coprime')
  exit()
a=A[0]
d=a
if A[0]!=1:
  D={}
  x=0
  for i in range(N):
    if d!=1:
      d=math.gcd(d,A[i])
    c=A[i]
    if x==0:
      F=factorization(A[i])
      for a,b in F:
        if a not in D:
          D[a]=1
        else:
          x=1
        #互いに素じゃない二組がある  
    if x==1 and d==1:
      break

  if x==1 and d==1:
    print('setwise coprime')
  elif x==0 and d==1:
    print('pairwise coprime')
  else:
    print('not coprime')
else:
  D={}
  x=0
  for i in range(N):
    F=factorization(A[i])
    for a,b in F:
      if a not in D:
        D[a]=1
      else:
        x=1
    if x==1:
      break
    
  if x==1:
    print('setwise coprime')
  else:
    print('pairwise coprime')

Submission status: Wrong Answer

Solution code:
import sys

def cf(x1,x2):
    cf=[]
    for i in range(2,min(x1,x2)+1):
        if x1 % i == 0 and x2 % i == 0:
            cf.append(i)
    return cf

N = int(input())
A = list(map(int,input().split()))
A.sort()
X = cf(A[0],A[1])

for i in X:
    a = 0
    b = 0
    for j in range(N):
        if A[j] % i == 0:
            a += 1
        else:
            b += 1
    if a == N:
        print("not coprime")
        sys.exit()
    if a != 0 and b != 0:
        print("setwise coprime")
        sys.exit()
print("pairwise coprime" if len(X) == 0 else "setwise coprime")

Submission status: Wrong Answer

Solution code:
from collections import Counter
import sys
import numpy as np
n = int(input())
ls = list(map(int,input().split()))
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
            for _ in range(cnt):
                arr.append(i)

    if temp!=1:
        arr.append(temp)

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

    return arr
if len(list(set(ls))) != len(ls):
    print("not coprime")
    sys.exit()
c = Counter(ls)
s = list(set(ls))
if np.gcd.reduce(ls) == 1:
    fi = [True]*(10**6+1)
    for y in s:
        l = list(set(factorization(y)))
        l.sort()
        for q in l:
            u = q * 2
            while u <= 10**6:
                if u in s and u > y:
                    fi[u] = False
                u += q
    cnt = 0
    for z in ls:
        if fi[z] == True:
            cnt += 1
    if cnt == len(ls):
        print("pairwise coprime")
    else:
        print(cnt)
        print("setwise coprime")
else:
    print("not coprime")

Submission status: Wrong Answer

Solution code:
import sys, bisect, math, itertools, heapq, collections
from operator import itemgetter
# a.sort(key=itemgetter(i)) # i番目要素でsort
from functools import lru_cache
import copy
# @lru_cache(maxsize=None)
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
mod = 10**9 + 7
eps = 10**-7


def inp():
    '''
    一つの整数
    '''
    return int(input())


def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))


def str_inp():
    '''
    文字列をリストとして読み込む
    '''
    return list(input()[:-1])


def get_sieve_of_eratosthenes(n):
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 2:
        raise ValueError('n is more than 2')
    prime = []
    limit = math.sqrt(n)
    data = [i + 1 for i in range(1, n)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]


n = inp()
a = inpl()

data = get_sieve_of_eratosthenes(10**6)
temp = copy.deepcopy(data)
for i in range(n):
    tmp = a[i]
    temp2 = []
    if not len(temp):
        break
    for j in temp:
        if tmp == 1:
            break
        if tmp % j == 0:
            temp2.append(j)
            while tmp % j == 0:
                tmp //= j
    temp = copy.deepcopy(temp2)

if len(temp):
    print("not coprime")
    exit()

dp = {i: 0 for i in data}
for i in range(n):
    tmp = a[i]
    for j in data:
        if tmp == 1:
            break
        if tmp % j == 0:
            dp[j] += 1
            while tmp % j == 0:
                tmp //= j
ans = max(list(dp.values()))
if ans == 1:
    print("pairwise coprime")
else:
    print("setwise coprime")
# ans = "pairwise coprime"
# for i in data:
#     coprime = 0
#     for j in range(n):
#         if a[j] % i == 0:
#             coprime += 1
#         elif a[j] % i != 0 and (coprime >= 2 or ans == "setwise coprime"):
#             break
#     if coprime == n:
#         ans = "not coprime"
#         break
#     elif coprime >= 2:
#         ans = "setwise coprime"
# print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import resource
from collections import defaultdict

s=set()
sys.setrecursionlimit(100000)

def gcd(a,b):
    if a%b==0: return b
    return gcd(b,a%b)

i,k=2,10**6
pri=set()
while k>=i*i:
    while k%i==0:
        k//=i
        pri.add(i)
    i+=1
if k!=1: pri.add(k)

n=int(input())
a=list(map(int,input().split()))
visi=set()
s=a[0]
flag=1
for i in a:
    s=gcd(s,i)
    for c in pri:
        if i%c==0:
            if c in visi:
                flag=1
                break
            visi.add(c)
if flag: print("pairwise coprime")
elif s==1: print("setwise coprime")
else: print("not coprime")

Submission status: Wrong Answer

Solution code:
import functools
import math
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i:
        divisors.append(n//i)

  divisors.sort()
  divisors.pop(0)
  return divisors

def is_prime(n):
  for i in range(2, n + 1):
    if i * i > n:
      break
    if n % i == 0:
      return False
  return n != 1

N = input()
A = list(map(int, input().split()))
A = sorted(A)
gcd = functools.reduce(math.gcd, A)

dp = []
if 2 <= gcd:
  print("not coprime")
else:
  isPC = True
  for a in A:
    if is_prime(a):
      dp.append(a)
    else:
      divs = make_divisors(a)
      print('divs', divs)
      for d in divs:
        if d in dp:
          isPC = False
          break
        dp.append(d)

    if not isPC:
      break
  if isPC:
    print("pairwise coprime")
  else:
    print("setwise coprime")

Submission status: Wrong Answer

Solution code:
def sieve(n):
    is_prime = [True for _ in range(n+1)]
    is_prime[0] = False

    for i in range(2, n+1):
        if is_prime[i-1]:
            j = 2 * i
            while j <= n:
                is_prime[j-1] = False
                j += i
    table = [ i for i in range(1, n+1) if is_prime[i-1]]
    return is_prime, table

n=int(input())
a=sorted(list(map(int,input().split())))
a=list(set(a))
ans=2
if n>len(a):
  ans-=1
pri,prit=sieve(a[-1])
for i in prit:
  cnt=0
  for j in a:
    if i>j:
      continue
    if j%i==0:
      cnt+=1
  if cnt==n:
    ans=0
    break
  if cnt>=2:
    ans=1
if ans==2:
  print('pairwise coprime')
elif ans==1:
  print('setwise coprime')
else:
  print('not coprime')

Submission status: Wrong Answer

Solution code:
from functools import reduce
from math import gcd 

n = int(input())
A = list(map(int, input().split()))
A.sort()
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()

now = A[0]
for a in A:
    now = gcd(now, a)
    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()))
a.sort()

ans = a[0]
for i in range(1, n):
    ans = math.gcd(ans, a[i])

if ans!=1:
    print('not coprime')

else:
    for l in range(1,n):
        if a[l]==a[l-1] and a[l]!=1:
            print('setwise coprime')
            exit()
    for i in range(min(100000,n-1)):
        for k in range(min(i+1,n-1),min(n,1000)):
            if math.gcd(a[i],a[k])!=1:
                print('setwise coprime')
                exit()
    print('pairwise coprime')

Submission status: Wrong Answer

Solution code:
def factorization(n):
    if n == 1:
        return {1}
    temp = n
    ans = set()
    SS = [i for i in S if i*2 < n]
    for i in SS:
        if temp % i == 0:
            ans.add(i)
    if temp != 1:
        ans.add(temp)
    return ans

S=set()
L = [True]*(10**6+1)
L[0] = False
L[1] = False
for i in range(2, 10**6+1):
    if L[i]:
        S.add(i)
        for j in range(i*2, 10**6+1, i):
            L[j] = False


def egcd(a, b):
    if a == 0:
        return b
    else:
        g = egcd(b % a, a)
        return g


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

ct = 0
s = set()
for i in range(N):
    tmp = factorization(A[i])
    ct += len(tmp)
    s |= tmp
    if ct != len(s):
        break
else:
    print('pairwise coprime')
    exit()


L1 = A
while len(L1) > 1:
    l = len(L1)//2
    tmp = [0]*l
    for i in range(l):
        tmp[i] = egcd(L1[2*i], L1[2*i+1])
    if len(L1) % 2 == 1:
        tmp.append(L1[-1])
    L1 = tmp

if L1[0] == 1:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Wrong Answer

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

from math import gcd
from functools import reduce

def gcd_list(L):
    return reduce(gcd, L)

g = gcd_list(A)

cnt = [0] * 100
for a in A:
    for k in [2, 3, 5, 7, 11, 13, 17, 19]:
        if a % k == 0:
            cnt[k] += 1

ma = max(cnt)

if ma == 1:
    print('pairwise coprime')
elif g == 1:
    print('setwise coprime')
else:
    print('not coprime')