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:
from sys import stdin, setrecursionlimit
#input = stdin.buffer.readline
setrecursionlimit(10 ** 7)

from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
from collections import deque, defaultdict, Counter
from itertools import combinations, permutations, combinations_with_replacement
from itertools import accumulate
from math import ceil, sqrt, pi, radians, sin, cos

MOD = 10 ** 9 + 7
INF = 10 ** 18

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

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 = [2]
    limit = int(n**0.5)
    data = [i + 1 for i in range(2, n, 2)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]

data = get_sieve_of_eratosthenes(1000001)
data2 = get_sieve_of_eratosthenes(2000)

# 1~1000000の素数リストを作成
check = [0] * (10 ** 6 + 1)
for d in data:
    check[d] = 1

def is_pairwise(arr):
    # 同じ数があったらアウト
    len_A = len(arr)
    A = list(set(arr))
    if len_A != len(arr):
        return 0
    
    # 非素数が168個以上あったらアウト
    non_prime = []
    for a in arr:
        if check[a] == 0:
            non_prime.append(a)
    #print(non_prime)
    
    if len(non_prime) > 200:
        return 0
    
    cnt = [0] * 1000001
    for np in non_prime:
        tmp = np
        for d2 in data2:
            if np % d2 == 0:
                cnt[d2] += 1
                while np % d2 == 0:
                    np //= d2
        cnt[np] += 1
    if max(cnt[1:]) >= 2:
        return 0
    
    return 1
    
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

def is_setwise(arr):
    
    tmp = arr[0]
    for a in arr:
        tmp = gcd(tmp, a)
    if tmp == 1:
        return 1
    else:
        return 0
        
ip = is_pairwise(A)
iss = is_setwise(A)

if ip:
    print("pairwise coprime")
else:
    if iss:
        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()))

pc = True
sc = True
M = {}
MAX = 0
for i,A in enumerate(A_s):
    for p in factorization(A):
        if p[0] in M:
            M[p[0]] += 1
            pc = False
        else:
            M[p[0]] = 1
        MAX = max(MAX, M[p[0]])
if MAX == N:
    sc = False

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

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 gcd(a, b):
    if a == b: return a
    while b > 0: a, b = b, a % b
    return a

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



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



import random

def power(x, y, p):
    res = 1  # Initialize result
    x = x % p  # Update x if it is more , than or equal to p
    if (x == 0):
        return 0
    while (y > 0):
        if ((y & 1) == 1):  # If y is odd, multiply, x with result
            res = (res * x) % p

        y = y >> 1  # y = y/2
        x = (x * x) % p
    return res

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(100000))
_smallprimeset = 100000
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


    d = n - 1
    s = 0
    while d % 2 == 0:
        d //= 2
        s += 1

    for repeat in range(precision):
        a = random.randrange(2, n - 2)
        x = power(a, d, n)

        if x == 1 or x == n - 1: continue

        for r in range(s - 1):
            x = power(x, 2, n)
            if x == 1: return False
            if x == n - 1: break
        else: return False

    return True

# https://comeoncodeon.wordpress.com/2010/09/18/pollard-rho-brent-integer-factorization/
def pollard_brent(n):
    if n % 2 == 0: return 2
    if n % 3 == 0: return 3

    y, c, m = random.randint(1, n-1), random.randint(1, n-1), random.randint(1, n-1)
    g, r, q = 1, 1, 1
    while g == 1:
        x = y
        for i in range(r):
            y = (power(y, 2, n) + c) % n

        k = 0
        while k < r and g==1:
            ys = y
            for i in range(min(m, r-k)):
                y = (power(y, 2, n) + c) % n
                q = q * abs(x-y) % n
            g = gcd(q, n)
            k += m
        r *= 2
    if g == n:
        while True:
            ys = (power(ys, 2, n) + c) % n
            g = gcd(abs(x - ys), n)
            if g > 1:
                break

    return g

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

    while n > 1:
        if isprime(n):
            factors.append(n)
            break
        factor = pollard_brent(n) # trial division did not fully factor, switch to pollard-brent
        factors.extend(primefactors(factor)) # recurse to factor the not necessarily prime factor returned by pollard-brent
        n //= factor

    if sort: factors.sort()

    return factors

def factorization(n):
    factors = {}
    for p1 in primefactors(n):
        try:
            factors[p1] += 1
        except KeyError:
            factors[p1] = 1
    return factors


from functools import reduce

n=int(inp())
ar=lis()
if n<79000:
    temp=set()
    temps=0
    t=1
    for i in ar:
        k=factorization(i)
        s=set(k.keys())
        l=len(s)
        temp=temp.union(s)
        if len(temp)!=l+temps:
            t=-1
            break
        temps+=l
    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:
import math
import functools

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

A.sort()

pairwise = True
for a in A:
    # print(a)
    if a == 1:
        continue
    if pairwise is False:
        break
    for k in range(2, int(math.sqrt(a) + 1)):
        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)
    # print(p)

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

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

Submission status: Wrong Answer

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

def gcdall(a):
	rt = 0
	for i in a:
		rt = math.gcd(rt, i)
		if rt == 1:
			break
	return rt

#GCD(ai, aj)=1 がすべてとは, aの中の素因数に共通のものがないということ

def makediv(n):
	lower_divisors , upper_divisors = [], []
	i = 1
	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 sieve(n):
	ret = set()
	divlis = [-1]*(n+1)  # 何で割ったかのリスト(初期値は-1)
	flag = [True]*(n+1)
	flag[0] = False
	flag[1] = False
	ind = 2
	while ind <= n:
		if flag[ind]:
			ret.add(ind)
			ind2 = ind**2
			while ind2 <= n:
				flag[ind2] = False
				divlis[ind2] = ind
				ind2 += ind
		ind += 1
	#何で割ったかのリストを取得したいとき, divlisも出力する
	return ret

targ = sieve(n)

def pairwise(a):
	t = set()
	mint = n
	mode = True
	for i in a:
		if i == 1:
			continue
		mint = min(i, mint)
		if i in targ:
			for j in range(i, mint+1, i):
				if j not in t:
					t.add(j)
				else:
					mode = False
					break
		else:
			k = makediv(i)
			for j in k:
				if j == 1:
					continue
				if j not in t:
					t.add(j)
				else:
					mode = False
					break
		if not mode:
			break
	return mode

if gcdall(a) == 1:
	if pairwise(a):
		print("pairwise coprime")
	else:
		print("setwise coprime")
else:
	print("not coprime")

Submission status: Wrong Answer

Solution code:
gcd=lambda x,y:gcd(y,x%y) if y!=0 else x
def f(a):
    p=a[0]
    for i in range(1,len(a)):
        p=gcd(p,a[i])
    if p==1:
        print("setwise coprime")
    else:
        print("not coprime")

n=int(input())
a=list(map(int,input().split()))
if 1 in a:
    print("not coprime")
l=[0 for i in range(2*10**6)]
for i in a:
    l[i]+=1
for i in range(2,2*10**6):
    p=0
    for j in range(i*i,2*10**6,i):
        p+=l[j]
    if p>1:
        f(a)
        exit()
print("pairwise coprime")

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(1 << 25)
readline = sys.stdin.buffer.readline
read = sys.stdin.readline  # 文字列読み込む時はこっち
ra = range
enu = enumerate


def exit(*argv, **kwarg):
    print(*argv, **kwarg)
    sys.exit()


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))
# 受け渡されたすべての要素からsubだけ引く.リストを*をつけて展開しておくこと


def a_int(): return int(readline())


def ints(): return list(map(int, readline().split()))


def read_col(H):
    '''H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) #一列の場合'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, readline().split())))
    return tuple(map(list, zip(*ret)))


def read_tuple(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, readline().split())))
    return ret


def read_matrix(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, readline().split())))
    return ret
    # return [list(map(int, read().split())) for _ in range(H)] # 内包表記はpypyでは遅いため


def factorization(n: int):
    if n == 1:
        return []  # 1は素数ではない
    # 素因数分解
    arr = []
    temp = n
    for i in range(2, int(n**0.5) + 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 can_factorization(n: int):
    if n == 1:
        return []  # 1は素数ではない
    # 素因数分解
    arr = []
    temp = n
    for i in range(2, int(n**0.5) + 1):  # ここにバグがないか心配
        if temp % i == 0:
            arr.append(i)

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

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

    return arr


MOD = 10**9 + 7
INF = 2**31  # 2147483648 > 10**9
# default import
from collections import defaultdict, Counter, deque
from operator import itemgetter, xor, add
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  # , insort_left, insort_right
from functools import reduce
from math import gcd


N = a_int()
A = ints()

# setかはすぐわかる
# setでなければ not coprime
# pairは互いに素かをみればいいのか
# つまり因数分解して足してったときにすべての素数のべき数が1以下であれば良い

g_set = 0
cnt = defaultdict(lambda: 0)
flg = 1  # pairwiseであるフラグ
if N > 2 * (10**5):
    flg = 0
    for a in A:
        g_set = gcd(g_set, a)
else:
    for a in A:
        g_set = gcd(g_set, a)
        for p, n in factorization(a):
            if cnt[p] != 0:
                flg = 0
            cnt[p] += n


# print(cnt)
# for v in cnt.values():
#     if v > 1:
#         flg = 0
#         break

if g_set > 1:
    print('not coprime')
elif flg:
    print('pairwise coprime')
else:
    print('setwise coprime')

Submission status: Wrong Answer

Solution code:
from random import randint
N = randint(0,2)
if N==0:
  print("pairwise coprime")
elif N==1:
  print("setwise coprime")
else:
  print("not coprime")

Submission status: Wrong Answer

Solution code:
def eratosthenes(n):
    prime = []
    limit = n**0.5
    numbers = [i for i in range(2,n+1)]
    while True:
        p = numbers[0]
        if limit <= p:
            return prime + numbers
        prime.append(p)
        numbers = [i for i in numbers if i%p != 0]
    return prime

def prime_decomposition(n):
  i = 2
  d = {}
  while i * i <= n:
    while n % i == 0:
      n //= i
      if i not in d:
          d[i] = 0
      d[i] += 1
    i += 1
  if n > 1:
    if n not in d:
        d[n] = 1
  return d

pl = eratosthenes(10**6)
pd = {}
for p in pl:
    pd[p] = 0

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


A.sort()

d = {}
ans = 0
if len(set(A)) != N:
    ans = 1
for i in range(N):
    if A[i] in d:
        ans = 1
        break
    if A[i] not in pd:
        primes = prime_decomposition(A[i])
        for p in primes:
            if p not in d:
                for j in range(1,(10**6)//p+1):
                    d[j*p] = 0
            else:
                ans = 1
                break
    d[A[i]] = 0



if ans == 0:
    print('pairwise coprime')
else:
    def gcd(a, b):
    	while b:
    		a, b = b, a % b
    	return a
    a = A[0]
    for i in range(N):
        a = gcd(a,A[i])
    if a==1:
        print('setwise coprime')
    else:
        print('not coprime')

Submission status: Wrong Answer

Solution code:
MOD=67280421310721
import sys
import math
N=int(input())
alist=list(map(int,input().split()))
alist.sort()

all_GCD=alist[0]
for i in range(1,N):
  all_GCD=math.gcd(all_GCD,alist[i])
  if all_GCD==1:
    break
else:
  print("not coprime")
  sys.exit(0)
  
lcm_MOD=1
prod_MOD=1
for i in range(N):
  lcm_MOD=lcm_MOD*alist[i]//math.gcd(lcm_MOD,alist[i])
  lcm_MOD%=MOD
  prod_MOD*=alist[i]
  prod_MOD%=MOD
#print(lcm_MOD,prod_MOD)

if lcm_MOD==prod_MOD:
  print("pairwise coprime")
else:
  print("setwise coprime")

Submission status: Wrong Answer

Solution code:
import math
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]]
n = int(input())
a = list(map(int, input().split()))
b = a[0]
for i in range(1, n): b = math.gcd(b, a[i])
if b != 1: print("not coprime")
else:
    data = primes(10**3)
    count = [0]*(len(data))
    for i in range(n):
        for j in range(len(data)):
            if a[i]%data[j] == 0: count[j] += 1
    x = 0
    for i in range(1, len(count)):
        x = max(x, count[i])
    print("setwise coprime") if x > 1 else print("pairwise coprime")

Submission status: Wrong Answer

Solution code:
from math import gcd
(_,),a  = [list(map(int, s.split())) for s in open(0)]

ans = 'pairwise coprime'

l = g = a.pop()
for x in a:
    g, l = gcd(g, x), l * x
    if g != 1:
        ans = 'setwise coprime'
        l //= g
    print(l,g)
if g != 1:
    ans = 'not coprime'
print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int, input().split()))
A=sorted(A)
import math
if A==[1]*N:
  print('pairwise coprime')
  exit()
a=A[0]
if A[0]!=1:
  b=max(A)
  D=[0]*(b+1)
  x,y=0,0
  for i in range(N):
    d=math.gcd(a,A[i])
    c=A[i]
    if D[c]==0:
      while c<=b:
        D[c]=1
        c+=A[i]
    else:
      x=1
      #互いに素じゃない二組がある  
    
  if x==1 and d==1:
    print('setwise coprime')
  elif x==0 and d==1:
    print('pairwise coprime')
  else:
    print('not coprime')
else:
  b=max(A)
  a=A[-1]
  D=[0]*(b+1)
  x=0
  for i in range(N):
    if A[i]!=1:
      d=math.gcd(a,A[i])
      c=A[i]
      if D[c]==0:
        while c<=b:
          D[c]=1
          c+=A[i]
      else:
        x=1
        #互いに素じゃない二組がある  
    
  if x==1:
    print('setwise coprime')
  else:
    print('pairwise coprime')

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)
# input = sys.stdin.readline    ####
def int1(x): return int(x) - 1
def II(): return int(input())
def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())
def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def MS(): return input().split()
def LS(): return list(input())
def LLS(rows_number): return [LS() for _ in range(rows_number)]
def printlist(lst, k=' '): print(k.join(list(map(str, lst))))
INF = float('inf')
# from math import ceil, floor, log2
# from collections import deque, defaultdict
# from itertools import combinations as comb, combinations_with_replacement as comb_w, accumulate, product, permutations
# from heapq import heapify, heappop, heappush
# import numpy as np    # cumsum
# from bisect import bisect_left, bisect_right

# from fractions import gcd
from math import gcd
# def lcm(x, y):
#   return x // gcd(x, y) * y

def solve():
    N = II()
    A = LI()
    mx = max(A)
    A = sorted(A, reverse=True)
    # print(A)
    g = A[0]
    flag_pc = True
    for a in A[1:]:
        g = gcd(g, a)
        # print(g)
        if g != 1:
            flag_pc = False

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


if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
def abc177_e():
    n = int(input())
    A = list(map(int, input().split()))
    from math import gcd
    cumf = [1]*n
    cumr = [1]*n
    cumf[0] = A[0]
    cumr[-1] = A[-1]
    for i in range(1, n):
        cumf[i] = gcd(cumf[i-1], A[i])
    for i in range(n-2, -1, -1):
        cumr[i] = gcd(cumr[i+1], A[i])

    if cumr[0] > 1:
        return print('not coprime')
    setwise = False
    for i in range(1, n-1):
        fr = gcd(cumf[i-1], cumr[i+1])
        if fr > 1:
            setwise = True
            break
    ans = 'setwise coprime' if setwise else 'pairwise coprime'
    return print(ans)

if __name__ == '__main__':
    abc177_e()

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

baisuu_dict = defaultdict(list)
for a in A:
    yakusuu = [y[0] for y in factorization(a)]
    for y in yakusuu:
        baisuu_dict[y].append(a)

is_pairwise = True
is_setwise = True
for prime, baisuu_list in baisuu_dict.items():
    if len(baisuu_list) >= 2:
        is_pairwise = False
    if len(baisuu_list) == len(A):
        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:
import sys
input = lambda: sys.stdin.readline().rstrip("\r\n")

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

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

from collections import Counter

c = Counter(a)

if max(c.values()) > 1:
    print('not coprime')
    sys.exit()

if max_gcd_pair(a) <= 1:
    print('pairwise coprime')
    sys.exit()

import math
from functools import reduce

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

if gcd(*a) == 1:
    print('setwise coprime')
    sys.exit()

else:
    print('not coprime')

Submission status: Wrong Answer

Solution code:
import math
n = int(input())
a = list(map(int,input().split()))
k = math.gcd(a[0],a[1]) #最大公約数
m = a[0]*a[1]//math.gcd(a[0],a[1]) #最小公倍数
j = a[0]*a[1]#漱石

for i in range(2,n):
    j*=a[i]
    m = m*a[i]//math.gcd(a[i],m)
    k = math.gcd(k,a[i])
    
if(k==1):
    if(m==j):
        print("setwise coprime")
    else:
        print("pairwise coprime")
else:
    print("not coprime")

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)


P=[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]

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

check = [0]*1000
flag = 0
for a in A:
    for i in range(bisect_right(P, int(a**0.5)+1)):
        if a%P[i] == 0 and flag == 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")