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

N = int(input())
A = [int(_) for _ in input().split()]
p = set([])

y = functools.reduce(math.gcd, A)
pairwise = True

for a in A:
    if a == 1:
        continue
    if pairwise is False:
        break
    for k in range(2, int(math.sqrt(a)) + 2):
        if a % k == 0:
            if k in p:
                pairwise = False
                break
            p.add(k)
            while a % k == 0:
                a //= k
    if pairwise and a > 1:
        p.add(a)

if pairwise:
    print("pairwize coprime")
elif y == 1:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Wrong Answer

Solution code:
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter,defaultdict
from operator import mul
import copy
# ! /usr/bin/env python
# -*- coding: utf-8 -*-
import heapq
sys.setrecursionlimit(10**6)
# INF =  float("inf")
INF = 10**18
import bisect
import statistics
mod = 10**9+7
# mod = 998244353

# エラトステネスの篩による素数判定（0:非素数，1：素数）
def make_is_prime(N):
    prime = [1 for i in range(N+1)]
    prime[0] = prime[1] = 0
    for i in range(2,N+1):
        if prime[i] == 0: continue
        j = i**2
        while (j <= N):
            prime[j] = 0
            j += i
    return prime

a = make_is_prime(10**3+1)
b = []

for i in range(len(a)):
    if a[i] == 1:
        b.append(i)

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

pc = 1
sc = 1

for i in b:
    count = 0
    for j in range(N):
        if A[j]%i == 0:
            count += 1
    if count >= 2:
        pc = 0
    if count == N:
        sc = 0
        break

if pc == 1:
    print("pairwise coprime")
elif sc == 1:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Wrong Answer

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

pc = "pairwise coprime"
sc = "setwise coprime"
nc = "not coprime"

maxi=max(A)
sumi=set()

for i in range(2,maxi+1):
    if i in sumi:
        pass
    else:
        tmp=maxi//i
        for j in range(2,tmp+1):
            sumi.add(j*i)

cnt=0
for num in A:
    if num in sumi:
        cnt +=1
if cnt<=1:
    ans=pc
else:
    tmp2=A[0]
    for q in range(1,N):
        tmp2 = gcd(tmp2,A[q])
    if tmp2==1:
        ans=sc
    else:
        ans=nc

print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
# map(int, input().split())
import math
from collections import defaultdict

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

def erathostenes(limit):
    a=list(range(2,limit+1))
    p=list()
    while a[0]**2<=limit:
	    tmp=a[0]
	    p.append(tmp)
	    a=[e for e in a if e%tmp!=0]
    p.extend(a)
    return p


prime_list = erathostenes(pow(10,3))
is_large_prime_list = [True for i in range(N)]

is_pairwise = True
is_setwise = True

for prime in prime_list:
    baisuu_cnt = 0
    baisuu_list = []
    for i in range(len(A)):
        if A[i]%prime == 0:
            is_large_prime_list[i] = False
            baisuu_cnt += 1
            baisuu_list.append(A[i])

    if baisuu_cnt >= 2:
        is_pairwise = False
    if baisuu_cnt == N:
        is_setwise = False

if is_setwise or is_pairwise:
    large_primes = [A[i] for i in range(N) if is_large_prime_list[i]]

    if len(set(large_primes)) != len(large_primes):
        is_pairwise = False
        is_setwise = False


if is_pairwise:
    print('pairwise coprime')
elif is_setwise:
    print('setwise coprime') 
else:
    print('not coprime')

Submission status: Wrong Answer

Solution code:
n = int(input())
a = [int(x) for x in input().split()]
primes = [2]
A = max(a)
b = [0] * (A+1)

for L in range(3, A, 2): 
    if all(L % L2 != 0 for L2 in primes):
        primes.append(L)

def factorization(n):
    arr = 0
    temp = n
    for i in primes:
        if i**2 > n: break
        if temp%i==0:
            b[i] += 1
            arr += 1
            while temp%i==0:
                temp //= i
    if temp!=1:
        b[temp] += 1
        arr += 1

    if arr==0:
        b[n] += 1

for aa in a:
    factorization(aa)
if max(b) == 1: print('pairwise coprime')
elif max(b) < n: print('setwise coprime')
else: print('not coprime')

Submission status: Wrong Answer

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

def GCM(y, x):
  buf = y%x
  if buf==0:
    return x
  else:
    return GCM(x, buf)

A.sort()
maxA = A[-1]
for i in range(2,N+1):
  maxA %= A[-i]
  if maxA == 0:
    maxA = A[-i]
if GCM(A[0], maxA)>1:
  print("not coprime")
else:
  count = 0
  flag=False
  for i in range(N-1):
    for j in range(i+1,N):
      count += 1
      if count > 10000000:
        break
      if GCM(A[-(i+1)],A[-(j+1)]) != 1:
        flag=True
        break
  if flag:
    print("setwise coprime")
  else:
    print("pairwise coprime")

Submission status: Wrong Answer

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

def gcd_list(numbers):
    return reduce(gcd, numbers)
def lcm(x, y):
    return (x * y) // gcd(x, y)

N = int(input())
A = [int(i) for i in input().split()]

left = [0] * N
for i in range(1, N):
    left[i] = gcd(A[i - 1], left[i - 1])
right = [0] * N
for i in range(N - 2, -1, -1):
    right[i] = gcd(A[i + 1], right[i + 1])

flag = True
for a, l, r in zip(A, left, right):
    if gcd(l, a) != 1 and gcd(r, a) != 1:
        flag = False
        break

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

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import copy

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)

    return divisors


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

a2 = set(a)
pcf = True

if len(a) != len(a2):
    a = list(a2)
    pcf = False

pc = set(make_divisors(a[0]))
pcl = len(pc)
sc = copy.deepcopy(pc)

for i in a[1:]:
    d = set(make_divisors(i))
    dl = len(d) - 1
    pc = pc.union(d)
    pcl2 = len(pc)
    if pcl + dl != pcl2:
        pcf = False
    pcl = pcl2

    sc = sc.intersection(d)

if pcf:
    print("pairwise coprime")
elif len(sc) == 1:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Wrong Answer

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

n=int(input())
a=list(map(int,input().split()))
b=gcd(a[0],a[1])
res1=True
c=[1]*n
for i in range(1,n):
    c[i]=c[i-1]*a[n-i]%a[n-i-1]

for i in range(n-1):
    d=a[i];e=a[i+1];f=c[n-i-1]
    if gcd(d,f)==1:
        continue
    else:
        res1=False
        b=gcd(b,e)

if res1:
    print("pairwise coprime")
elif b==1:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Wrong Answer

Solution code:
import math
from functools import reduce
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
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 factorization(i):
      if d.get(j[0],0)==0:
        d[j[0]]=j[1]
      elif flg==0:
        print('setwise coprime')
        flg=1
  if flg==0:
    print('pairwise coprime')

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from itertools import combinations
from functools import reduce
from operator import mul
n=int(input())

cnt = defaultdict(int)
A=list(map(int,input().split()))
for n_ in range(n):
    a=A[n_]
    divisors = set()
    for i in range(1, int(a**.5)+1):
        if a % i == 0:
            divisors |= {i, a//i}
    for div in divisors:
        cnt[div] += 1
answer=0
for a in A:
    facts = set()
    for p in range(2, int(-(-a**.5//1))+1):
        while a % p == 0:
            facts.add(p)
            a //= p
    if a != 1:
        facts.add(a)

    ans = n
    for k in range(1, len(facts)+1):
        for subset in combinations(facts, k):
            x = reduce(mul, subset)
            ans += cnt[x]*(-1)**k
    answer+=ans
if answer%n==0 and answer//n==n-1:
    print('pairwise coprime')
else:
    def gcd(a, b):
        if b == 0:
            return a
        else:
            return gcd(b, a % b)


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

Submission status: Wrong Answer

Solution code:
def judge(a):
    for x, y in itertools.combinations(a, 2):
        if math.gcd(x, y) >= 2:
            break
    else:
        return 'pairwise coprime'

    g = 1
    for i in range(len(a)-1):
        # print(a[i], a[i+1])
        g = math.gcd(g, a[i+1])
        if math.gcd(g, a[i+1]) == 1:
            return 'setwise coprime'
    return 'not coprime'

import math
import itertools

n = int(input())
a = [int(each) for each in input().split()]

print(judge(a))

Submission status: Wrong Answer

Solution code:
# ===============================================================================================
# importing some useful libraries.
from __future__ import division, print_function
from fractions import Fraction
import sys
import os
from io import BytesIO, IOBase
from itertools import *
import bisect
from heapq import *
from math import *
from copy import *
from collections import deque
from collections import Counter as counter  # Counter(list)  return a dict with {key: count}
from itertools import combinations as comb  # if a = [1,2,3] then print(list(comb(a,2))) -----> [(1, 2), (1, 3), (2, 3)]
from itertools import permutations as permutate
from bisect import bisect_left as bl
# If the element is already present in the list,

# the left most position where element has to be inserted is returned.
from bisect import bisect_right as br
from bisect import bisect

# If the element is already present in the list,
# the right most position where element has to be inserted is returned

# ==============================================================================================
# fast I/O region

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None


    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


if sys.version_info[0] < 3:
    sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
else:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)

# inp = lambda: sys.stdin.readline().rstrip("\r\n")

# ===============================================================================================
### START ITERATE RECURSION ###
from types import GeneratorType


def iterative(f, stack=[]):
    def wrapped_func(*args, **kwargs):
        if stack: return f(*args, **kwargs)
        to = f(*args, **kwargs)
        while True:
            if type(to) is GeneratorType:
                stack.append(to)
                to = next(to)
                continue
            stack.pop()
            if not stack: break
            to = stack[-1].send(to)
        return to

    return wrapped_func


#### END ITERATE RECURSION ####

# ===============================================================================================
# some shortcuts

mod = 1000000007


def inp(): return sys.stdin.readline().rstrip("\r\n")  # for fast input

def out(var): sys.stdout.write(str(var))  # for fast output, always take string

def lis(): return list(map(int, inp().split()))

def stringlis(): return list(map(str, inp().split()))

def sep(): return map(int, inp().split())

def strsep(): return map(str, inp().split())


def zerolist(n): return [0] * n

def nextline(): out("\n")  # as stdout.write always print sring.

def testcase(t):
    for p in range(t):
        solve()

def printlist(a):
    for p in range(0, len(a)):
        out(str(a[p]) + ' ')

def lcm(a, b): return (a * b) // gcd(a, b)


def ncr(n, r): return factorial(n) // (factorial(r) * factorial(max(n - r, 1)))


def primesbelow(N):
    # http://stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n-in-python/3035188#3035188
    #""" Input N>=6, Returns a list of primes, 2 <= p < N """
    correction = N % 6 > 1
    N = {0:N, 1:N-1, 2:N+4, 3:N+3, 4:N+2, 5:N+1}[N%6]
    sieve = [True] * (N // 3)
    sieve[0] = False
    for i in range(int(N ** .5) // 3 + 1):
        if sieve[i]:
            k = (3 * i + 1) | 1
            sieve[k*k // 3::2*k] = [False] * ((N//6 - (k*k)//6 - 1)//k + 1)
            sieve[(k*k + 4*k - 2*k*(i%2)) // 3::2*k] = [False] * ((N // 6 - (k*k + 4*k - 2*k*(i%2))//6 - 1) // k + 1)
    return [2, 3] + [(3 * i + 1) | 1 for i in range(1, N//3 - correction) if sieve[i]]

smallprimeset = set(primesbelow(1000000))
_smallprimeset = 1000000
def isprime(n, precision=7):
    # http://en.wikipedia.org/wiki/Miller-Rabin_primality_test#Algorithm_and_running_time
    if n < 1:
        raise ValueError("Out of bounds, first argument must be > 0")
    elif n <= 3:
        return n >= 2
    elif n % 2 == 0:
        return False
    elif n < _smallprimeset:
        return n in smallprimeset

    return True

# https://comeoncodeon.wordpress.com/2010/09/18/pollard-rho-brent-integer-factorization/

smallprimes = primesbelow(1000) # might seem low, but 1000*1000 = 1000000, so this will fully factor every composite < 1000000
def primefactors(n, sort=False):
    factors = []

    for checker in smallprimes:
        while n % checker == 0:
            factors.append(checker)
            n //= checker
        if checker > n: break

    if n < 2: return factors

    return factors




from functools import reduce

n=int(inp())
ar=lis()
tt=ar.count(1)
if (n-tt)<100000:
    t=1
    for i in ar:
        k=primefactors(i)
        s=set(k)
        for temp in s:
            if temp not in smallprimeset:
                t=-1
                break
            else:
                smallprimeset.remove(temp)
    if t==1:
        print("pairwise coprime")
    else:
        k=reduce(gcd,ar)
        if k==1:
            print("setwise coprime")
        else:
            print("not coprime")
else:
    k = reduce(gcd, ar)
    if k == 1:
        print("setwise coprime")
    else:
        print("not 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')
else:
    print('not coprime')

Submission status: Wrong Answer

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


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


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==[]:  # n=1のとき、[1,1]を返す
    #     arr.append([n, 1])

    return arr


# factorization(24)
# [[2, 3], [3, 1]]
#  24 = 2^3 * 3^1

gcdall = A[0]
for i in range(1, N):
    gcdall = gcd(gcdall, A[i])

# print(gcdall)
if gcdall > 1:
    print("not coprime")
    exit()

MAX = 10 ** 6 + 1
num = [0] * MAX
A = sorted(A)[::-1]
primeset = set()
for a in A:
    # if a == 1:
    #     continue
    # if num[a]:
    #     print("setwise coprime")
    #     exit()
    fact = factorization(a)
    for p, nn in fact:
        if p in primeset:
            continue
        primeset.add(p)
        for j in range(p + p, MAX, p):
            num[j] += 1
for a in A:
    if num[a] > 1:
        print("setwise coprime")
        exit()

print("pairwise coprime")

Submission status: Wrong Answer

Solution code:
from math import gcd


def main():
    def segfunc(x, y):
        return gcd(x, y)

    def init(init_val):
        # set_val
        for i in range(n):
            seg[i + num - 1] = init_val[i]
            # built
        for i in range(num - 2, -1, -1):
            seg[i] = segfunc(seg[2 * i + 1], seg[2 * i + 2])

    def update(k, x):
        k += num - 1
        seg[k] = x
        while k:
            k = (k - 1) // 2
            seg[k] = segfunc(seg[k * 2 + 1], seg[k * 2 + 2])

    def query(p, q):
        if q <= p:
            return ide_ele
        p += num - 1
        q += num - 2
        res = ide_ele
        while q - p > 1:
            if p & 1 == 0:
                res = segfunc(res, seg[p])
            if q & 1 == 1:
                res = segfunc(res, seg[q])
                q -= 1
            p = p // 2
            q = (q - 1) // 2
        if p == q:
            res = segfunc(res, seg[p])
        else:
            res = segfunc(segfunc(res, seg[p]), seg[q])
        return res

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

    #####単位元######
    ide_ele = 0

    # num:n以上の最小の2のべき乗
    num = 2 ** (n - 1).bit_length()
    seg = [ide_ele] * 2 * num
    init(S)

    tmp = 1
    if query(0, n) != 1:
        print("not coprime")
        exit()
    for i in range(n - 1):
        if query(i, n) != 1:
            print("setwise coprime")
            exit()
    print("pairwise coprime")


if __name__ == '__main__':
    main()

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 < 2 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:
n = int(input())
m=list(map(int,input().split()))
import math


d=m[n-1]

r=0


for i in range(n-2,-1,-1):
    d=math.gcd(m[i],d)
a=[1]*1000

for i in range(2,100):
    
    
    for j in range(i*i,1001,i):
        a[j-1]=0
k=[]
for i in range(1,1000):
    if a[i]==1:
        k.append(i+1)


for i in k:
    c=0
    for j in range(n):
        
        if m[j]%i==0:
            c+=1
            while m[j]%i==0:
                m[j]//=i
    if c>1:
        r=1
        break
        
        













    
    
if d>1:
    print('not coprime')
elif r==1:
    print('setwise coprime')
else:
    print('pairwise coprime')

Submission status: Wrong Answer

Solution code:
import math
import itertools
from functools import reduce

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


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


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


def is_coprime(x, y):
    return math.gcd(x, y) == 1


allCoprime = True
allNotCoprime = True

# combi = list(itertools.combinations(A, 2))
# for x in combi:
#     if is_coprime(x[0], x[1]):
#         allNotCoprime = False
#     else:
#         allCoprime = False

if gcd_list(A) == 1:
    allNotCoprime = False


if allCoprime:
    print("pairwise coprime")
elif allNotCoprime:
    print("not coprime")
else:
    print("setwise coprime")

Submission status: Wrong Answer

Solution code:
import math

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

ans = 'setwise coprime'

for i in range(N-1):
    tmp = math.gcd(numbers[i], numbers[i + 1])
    
    if (tmp > 1):
        ans = 'not coprime'
    
print(ans)

Submission status: Wrong Answer

Solution code:
'''
Created on 2020/08/29

@author: harurun
'''
def main():
  import math
  import heapq
  import copy
  import sys
  pin=sys.stdin.readline
  pout=sys.stdout.write
  perr=sys.stderr.write
  
  N=int(pin())
  A=list(map(int,pin().split()))
  heapq.heapify(A)
  B=copy.copy(A)  
  cnt=0
  for i in range(N):
    p=heapq.heappop(A)
    C=copy.copy(B)
    for j in range(N):
      q=heapq.heappop(C)
      if math.gcd(p,q)==1:
        cnt+=1
  if cnt==0:
    print("not coprime")
  elif cnt==N*N:
    print("pairwise coprime")
  else:
    print("setwise coprime")
  return 
main()

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.3:
        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:
n = int(input())
a = list(map(int, input().split()))
primes = [int(x) for x 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 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 1009'.split()]

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


def is_pairwise_coprime():
    for p in primes:
        count = 0
        for ai in a:
            if ai % p == 0:
                count += 1
        if count > 1:
            return False
    return True


def is_setwise_coprime():
    g = a[0]
    for i in range(n - 1):
        g = gcd(g, a[i + 1])
    return g == 1


if is_pairwise_coprime():
    print('pairwise coprime')
elif is_setwise_coprime():
    print('setwise coprime')
else:
    print('not 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]

    S = [1]*(N+1)
    for i, x in enumerate(A[::-1]):
        S[i+1] = S[i]*A[i]

    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
    for i, x in enumerate(A):
        g = gcd(g, x)
        if flag and gcd(x, S[-2-i]) > 1:
            flag = False

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

    else:
        print("not coprime")


main()

Submission status: Wrong Answer

Solution code:
import sys
## io ##
def IS(): return sys.stdin.readline().rstrip()
def II(): return int(IS())
def MII(): return list(map(int, IS().split()))
def MIIZ(): return list(map(lambda x: x-1, MII()))
def gcd(x,y):
    while y: x,y = y,x%y
    return x
def prime_factor(n):
    res = []
    for i in range(2,int(n**0.5)+1):
        while n%i==0: res.append(i); n //= i
    if n != 1: res.append(n)
    return res
from functools import reduce
#======================================================#
def main():
    n = II()
    aa = MII()
    head_prime = prime_factor(aa[0])

    # print()
    # print('all prime factors')
    # for a in aa:
    #     print(prime_factor(a))
    # print()

    pw_flag = True
    nc_flag = True
    for a in aa[1:]:
        nc_tmp = False
        for p in head_prime:
            if a%p == 0:
                nc_tmp = True
                pw_flag = False
        nc_flag &= nc_tmp

    if pw_flag:
        print('pairwise coprime')
    elif reduce(gcd, aa) == 1:
        print('setwise coprime')
    elif nc_flag:
        print('not coprime')


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import math
import copy

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


dp=[0 for _ in range(1000000+1)]

sosuu = [2]
A = 1000
for L in range(3, A, 2): # 2 以外の素数は奇数なので
    for L2 in sosuu:
        if L % L2 == 0:
            break # 素数でないことがわかったらそれ以上ループする必要はない
    else: # break で抜けることがなかったら L は素数（Python 特有の制御構文）
        sosuu.append(L)

if n>=78498:
  g=a[0]
  for h in range(1,n):
    g=math.gcd(g,a[h])
  if g==1:
    print('setwise coprime')
    
  else:
    print('not coprime')
  
  
else:
  ch1=0
  ch3=0
  for w in sosuu:
    ch2=0
    for q in range(n):
      if B[q]%w==0:
        ch2+=1
        S=B[q]
        while S%w==0:
          S=S//w
        B[q]=S
    if ch2>1:
      ch3+=1
  d={}
  ch4=0
  for u in B:
      if u>1000:
        if u not in d:
          d[u]=0
        else:
          ch4+=1
  if ch3==0 and ch4==0:
    print('pairwise coprime')
    
      
  
  
    
  else:
    g=a[0]
    for h in range(1,n):
      g=math.gcd(g,a[h])
    
    if g==1:
      print('setwise coprime')
    
    else:
      print('not coprime')