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 numpy as np

N = int(input())
A = list(map(int, input().split()))
B = np.array(list(zip(A, A[1:])))
res = np.gcd.reduce(B, axis=1)
if res.mean() == 1:
    print('pairwise coprime')
elif np.gcd.reduce(A) == 1:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
MAX= 10**6

from math import gcd
g = A[0]
# g_list = [A[0]]
for i in range(1, N):
    g = gcd(g, A[i])
    # g_list.append(g)
if g != 1:
    print("not coprime")
    exit()
else:
    A = [a for a in A if a != 1]
    n_primes = 78498
    if N > n_primes:
        print("setwise coprime")
        exit()
    else:
        def makePrimeChecker(n):
            """
            エラトステネスの篩.
            nまでの自然数が素数かどうかを表すリストを返す.
            """
            isPrime = [True] * (n + 1)
            isPrime[0] = False
            isPrime[1] = False
            for i in range(2, int(n ** 0.5) + 1):
                if isPrime[i]:
                    for j in range(i * i, n + 1, i):
                        isPrime[j] = False
            return isPrime

        is_prime = makePrimeChecker(MAX)
        is_ok = 1
        used_prime = [0]*(MAX+1)
        primes = [n for n in range(2, MAX+1) if is_prime[n]]
        i = 0
        for p in primes:
            for a in A:
                i += 1
                if a % p == 0:
                    if used_prime[p]:
                        is_ok = 0
                        break
                    used_prime[p] = 1
            if i >= 10**6 * 5:
                break
            if not is_ok:
                break
            
        if is_ok:
            print("pairwise coprime")
        else:
            print("setwise coprime")

Submission status: Wrong Answer

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

import math
MOD=10**9+7
flg=0
temp=a[0]
temp1=a[0]
for i in range(1,n):
    temp=math.gcd(temp,a[i])
    if math.gcd(temp1,a[i]) == 1:
        temp1*=a[i]
        #temp1%=MOD
        if i==n-1:
            flg=2
    if temp!=1 and i==n-1:
        flg=1
if flg==2:
    print('pairwise coprime')
elif flg==1:
    print("not coprime")
else:
    print("setwise coprime")

Submission status: Wrong Answer

Solution code:
#from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from fractions import gcd
from itertools import combinations,permutations,accumulate, product # (string,3) 3回
#from collections import deque
from collections import deque,defaultdict,Counter
import decimal
import re
import math
import bisect
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#
# my_round_int = lambda x:np.round((x*2 + 1)//2)
# 四捨五入g
#
# インデックス系
# int min_y = max(0, i - 2), max_y = min(h - 1, i + 2);
# int min_x = max(0, j - 2), max_x = min(w - 1, j + 2);
#
#
import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7
#mod = 9982443453
#mod = 998244353
from sys import stdin
readline = stdin.readline
def readInts():
  return list(map(int,readline().split()))
def readTuples():
    return tuple(map(int,readline().split()))
def I():
  return int(readline())
n = I()
A = readInts()
all = A[0]
def soinsu(n):
    i = 2
    p = n
    while i*i <= p:
        if n%i == 0:
            return 0
        else:
            i += 1
    if p!= 1:
        return p
#print(soinsu(31))
for i in range(1,n):
    all = gcd(all,A[i])
if all != 1:
    print('not coprime')
    exit()
else:
    nya = sum(A)
    if nya == soinsu(nya):
        print('setwise coprime')
    else:
        print('pairwise coprime')

Submission status: Wrong Answer

Solution code:
import numpy as np

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

for i in range(arr.shape[0] - 1):
    if np.gcd(arr[i], arr[i + 1]) != 1:
        ans1 = False
        break
else:
    ans1 = True

ans2 = np.gcd.reduce(arr) == 1

if ans1:
    print("pairwise coprime")
elif ans2:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Wrong Answer

Solution code:
def isPrime(x :int):
    if(x == 1):
        return False

    for i in range(2, int(x**0.5)+1):
        if(x%i == 0):
            return False
    return True

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

from math import gcd
from  functools import reduce

flag = False

for i in range(n):
    if isPrime(L[i]):
        flag = True
        #print(flag)
    elif L[i] == 1:
        flag = True
    else:
        flag = False
        #print(L[i])
        break
a = reduce(gcd,L)


if flag:
    print("pairwise coprime")
elif  not flag and a == 1:
    print("setwise 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)

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:
    temp = 0
    for i in range(bisect_right(P, int(a**0.5+10))):
        if a%P[i] == 0:
            if check[P[i]] == 1:
                flag = 1
            else:
                check[P[i]] = 1
            temp = 1
    if temp == 0 and check[a] == 1:
        flag = 1
    if not temp:
        check[a] = 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:
from math import gcd
import sys

def sieve(N):
    # 昇順リストの用意
    A_list = [i for i in range(2, N+1)]
    limit = A_list[-1]

    # ふるいにかけられたかどうかを示すbooleanの辞書
    sieve = {i: True for i in A_list}

    # 順にふるいにかける
    for a in A_list:
        if not sieve[a]:
            continue
        for i in range(2*a, limit+1, a):  # 2a, 3a, 4a, ..., と調べる
            if i in sieve:
                sieve[i] = False

    # 結果をまとめる
    primes = []
    for a in A_list:
        if sieve[a]:
            primes.append(a)
    return primes


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


sorted_A = sorted(A)

is_pairwise = True  #同じ数が含まれるかどうか
global_gcd = A[0]
for i in range(1, N):
    if A[i-1] == A[i]:
        is_pairwise = False
    global_gcd = gcd(global_gcd, A[i])
    
if global_gcd > 1:
    print('not corprime')
    sys.exit()
elif not is_pairwise:
    print('setwise coprime')
    sys.exit()
else:
    if A[-1] < 4:
        print('pairwise corprime')
        sys.exit()
    # 素数列挙
    primes = sieve(A[-1]// 2)
    
    for p in primes:
        divided_once = False
        for a in sorted_A:
            if a % p == 0:
                if divided_once:
                    print('setwise corprime')
                    sys.exit()
                divided_once = True
    print('pairwise corprime')

Submission status: Wrong Answer

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

gcda = A[0]
for i in range(1,N):
    gcda = math.gcd(gcda,A[i])
    if gcda != 1:
        ans = 'not coprime'
        break
else:
    ans = 'setwise coprime'
print(ans)

Submission status: Wrong Answer

Solution code:
from functools import reduce

def gcd(a, b):
    if b==0:return a
    return gcd(b,a%b)
def isPrimeMR(n):
    d = n - 1
    d = d // (d & -d)
    L = [2]
    for a in L:
        t = d
        y = pow(a, t, n)
        if y == 1: continue
        while y != n - 1:
            y = (y * y) % n
            if y == 1 or t == n - 1: return 0
            t <<= 1
    return 1
def findFactorRho(n):
    m = 1 << n.bit_length() // 8
    for c in range(1, 99):
        f = lambda x: (x * x + c) % n
        y, r, q, g = 2, 1, 1, 1
        while g == 1:
            x = y
            for i in range(r):
                y = f(y)
            k = 0
            while k < r and g == 1:
                ys = y
                for i in range(min(m, r - k)):
                    y = f(y)
                    q = q * abs(x - y) % n
                g = gcd(q, n)
                k += m
            r <<= 1
        if g == n:
            g = 1
            while g == 1:
                ys = f(ys)
                g = gcd(abs(x - ys), n)
        if g < n:
            if isPrimeMR(g): return g
            elif isPrimeMR(n // g): return n // g
            return findFactorRho(g)
def primeFactor(n):
    i = 2
    ret = {}
    rhoFlg = 0
    while i*i <= n:
        k = 0
        while n % i == 0:
            n //= i
            k += 1
        if k: ret[i] = k
        i += 1 + i % 2
        if i == 101 and n >= 2 ** 20:
            while n > 1:
                if isPrimeMR(n):
                    ret[n], n = 1, 1
                else:
                    rhoFlg = 1
                    j = findFactorRho(n)
                    k = 0
                    while n % j == 0:
                        n //= j
                        k += 1
                    ret[j] = k

    if n > 1: ret[n] = 1
    if rhoFlg: ret = {x: ret[x] for x in sorted(ret)}
    return ret
  
N=int(input())
*A,=map(int,input().split())

l = 0
for i in range(N):
  f = set(primeFactor(A[i]).keys())
  if i == 0:
    fset = f
    l += len(f)
    continue
  fset |= f
  l += len(f)

if l == len(fset):
  print('pairwise coprime')
  exit()
  
if reduce(gcd,A)==1:
  print('setwise coprime')
else:
  print('not coprimce')

Submission status: Wrong Answer

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

MAX_N = max(A)+5
primes = list(range(MAX_N+1))
for i in range(2, int(MAX_N**0.5)+1):
    if primes[i] < i:
        continue
    for j in range(2*i, MAX_N+1, i):
        primes[j] = i

def check():
    S = set()
    for a in A:
        T = set()
        while True:
            p = primes[a]
            if p in S:
                return False
            T.add(p)
            if p == a:
                break
            a //= p
        S |= T
    return True

if check() or all(a == 1 for a in A):
    print('pairwise coprime')
elif reduce(gcd, A) == 1:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Wrong Answer

Solution code:
##https://www.codechef.com/viewsolution/20131475

from math import gcd

def main():
    n = int(input())
    A = list(map(int , input().split()))
    N = max(A)+1

    if n > 9.5*10**5 and N > 9.5*10**5:
        print("pairwise coprime")
        exit()
    sv = [i for i in range(N)]
    for i in range(2 ,int(N**2)+1) :
        if i * i >= N : break
        if sv[i] < i : continue
        for j in range(i * i , N , i) :
            sv[j] = min(sv[j] , i)

    def getPrimes(a) :
        pr = []
        if a == 1 : return pr
        pr.append(sv[a])
        while a > 1 :
            if sv[a] != pr[-1] :
                pr.append(sv[a])
            a //= sv[a]
        return pr

    np = [0] * N
    F = [0] * N

    for a in A :
        pr = getPrimes(a)
        for i in range(1 << len(pr)) :
            prod , nb = 1 , 0
            for j in range(len(pr)) :
                if i & (1<<j) :
                    prod *= pr[j]
                    nb += 1
            F[prod] += 1
            np[prod] = nb

    ans = 0
    for i in range(N) :
        cnt = F[i]
        cnt = (cnt * (cnt-1))//2
        if np[i] & 1 : ans -= cnt
        else : ans += cnt

    if ans == (n*(n-1))//2:
        print("pairwise coprime")
        exit()
    
    A.sort()
    d = A[0]

    for i in A:
        d = gcd(i,d)
        if d == 1 or d > 10**2:
            break

    if d == 1:
        print("setwise coprime")
    else:
        print("not coprime")

main()

Submission status: Wrong Answer

Solution code:
n=int(input())
A=list(map(int,input().split(" ")))
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**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(n)

    return arr

base=A[0]
condition=0
check=0
for i in range(1,len(A),1):
    arr=factorization(A[i])
    for a in arr:
        if base%a==0:
            check=1
    base*=A[i]
    if check==1:
        condition=1
        break

if condition!=0 and i==1:
    base=A[0]
    for j in range(i,len(A),1):
        base=gcd(base,A[j])
    if base!=1:
        condition=2
ans=["pairwise coprime","setwise coprime","not coprime"]
print(ans[condition])

Submission status: Wrong Answer

Solution code:
import bisect
import sys,io
import math
from collections import deque
from heapq import heappush, heappop
import functools
input = sys.stdin.buffer.readline

def sRaw():
    return input().decode("utf-8").rstrip("\n").rstrip("\r")


def iRaw():
    return int(input())

def ssRaw():
    return input().split()


def isRaw():
    return list(map(int, ssRaw()))

INF = 1 << 29

DIV = (10**9) + 7
#DIV = 998244353

def mod_inv_prime(a, mod=DIV):
    return pow(a, mod-2, mod)


def mod_inv(a, b):
    r = a
    w = b
    u = 1
    v = 0
    while w != 0:
        t = r//w
        r -= t*w
        r, w = w, r
        u -= t*v
        u, v = v, u
    return (u % b+b) % b


def CONV_TBL(max, mod=DIV):
    fac, finv, inv = [0]*max, [0]*max, [0]*max
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1
    for i in range(2, max):
        fac[i] = fac[i-1]*i % mod
        inv[i] = mod - inv[mod % i] * (mod//i) % mod
        finv[i] = finv[i-1]*inv[i] % mod

    class CONV:
        def __init__(self):
            self.fac = fac
            self.finv = finv
            pass

        def ncr(self, n, k):
            if(n < k):
                return 0
            if(n < 0 or k < 0):
                return 0
            return fac[n]*(finv[k]*finv[n-k] % DIV) % DIV

    return CONV()


def cumsum(As):
    s = 0
    for a in As:
        s += a
        yield s


sys.setrecursionlimit(200005)


def dijkstra(G,start=0):
    heap = []
    cost = [INF]*len(G)
    heappush(heap,(0,start))
    while len(heap)!=0:
        c,n = heappop(heap)
        if cost[n] !=INF:
            continue
        cost[n]=c
        for e in G[n]:
            ec,v = e
            if cost[v]!=INF:
                continue
            heappush(heap,(ec+c,v))
    return cost

def gcd_list(As):
    return functools.reduce(math.gcd, As)

def lcm_div(x, y):
    return ((x * y) // math.gcd(x, y))%DIV

def lcm_div_list(numbers):
    return functools.reduce(lcm_div, numbers, 1)%DIV

def primes_by_eratos(n):
    data = [i for i in range(2, n + 1)]
    for d in data:
        data = [x for x in data if (x == d or x % d != 0)]
    return data

def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

def main():
    N = iRaw()
    As = isRaw()
    gcds = gcd_list(As)
    if gcds!=1:
        print("not coprime")
        return
    lcms = lcm_div_list(As)
    mul_d = 1
    lcm_d = 1
    primes = primes_by_eratos(1000)
    lcm_yakus = {}
    if len(set(As))!= len(As):
        print("setwise coprime")
        return
    for a in As:
        yakus = set(prime_factorize(a))
        for y in yakus:
            if y in lcm_yakus:
                print('setwise coprime')
                return
            else:
                lcm_yakus[y]=1
    print("pairwise coprime")
    return
    
main()

Submission status: Wrong Answer

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

import math
MOD=10**9+7
flg=0
temp=a[0]
temp1=a[0]
for i in range(1,n):
    temp=math.gcd(temp,a[i])
    if math.gcd(temp1,a[i]) == 1:
        temp1*=a[i]
        temp1%=MOD
        if i==n-1:
            flg=2
    if temp!=1 and i==n-1:
        flg=1
if flg==2:
    print('pairwise coprime')
elif flg==1:
    print("not coprime")
else:
    print("setwise coprime")

Submission status: Wrong Answer

Solution code:
import math

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

primes = [0]*(10**6+1)
small_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]
 
def prime_fac(n):
  temp = n
  Flag = True
  for i in small_primes:
    if temp % i == 0:
      cnt = 0
      while temp % i == 0:
        cnt += 1
        temp //= i
      primes[i] += 1
      Flag = False
  if temp != 1:
    primes[temp] += 1
  if Flag:
    primes[n] += 1

for a in A:
  prime_fac(a)

#print(primes[:15])

Flag = max(primes)

if Flag == 1:
  print("pairwise coprime")
elif Flag < N:
  print("setwise coprime")
else:
  print("not coprime")

Submission status: Wrong Answer

Solution code:
n = int(input())
arr = [int(a) for a in input().split()]

max_elem = max(arr)
duplicate_mode = None
sett = set([])

for elem in arr:
    if elem in sett and elem != 1:
        duplicate_mode = True
    sett.add(elem)

if not duplicate_mode:
    pos = True
    pos2 = True
    for cand in range(2, max_elem+1):
        cnt = 0
        for cand_ in range(cand, max_elem+1, cand):
            if cand_ in sett:
                cnt += 1

        if cnt == 0 or cnt == 1:
            continue
        elif cnt == n:
            print("not coprime")
            pos2 = False
            break
        else:  # cnt >= 2
           pos &= False

    if pos2:
        if pos:
            print("pairwise coprime")
        else:
            print("setwise coprime")
else:
    pos = True
    for cand in range(2, max_elem+1):
        cnt = 0
        factor = 1
        for cand_ in range(cand, max_elem+1, cand):
            if cand_ in sett:
                cnt += 1

        if cnt == n:
            print("not coprime")
            pos = False
            break
    if pos:
        print("setwise coprime")

Submission status: Wrong Answer

Solution code:
import itertools
import collections
n=int(input())
a=list(map(int,input().split()))
l=[]

def fermat(limit):
    n = 0
    for k in range(2, limit+1):
        if k % 2 == 0 and k != 2:
            continue
            
        if pow(2, k-1, k) == 1:
            n += 1
            
    return n

for i in range(n):
    k=fermat(a[i])
    l.append(k)


#l=list(itertools.chain.from_iterable(l))
c=len(l)
cl = collections.Counter(l)
cl1=cl.most_common()[0][1]
if c==n:print('pairwise coprime')
elif cl1<n:print('setwise coprime')
else:print('not coprime')

Submission status: Wrong Answer

Solution code:
from math import gcd

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

pre = a[0]
g = a[0]
flg = True
for idx, i in enumerate(a):
    if idx == 0:
        continue
    g = gcd(g, i)
    if flg:
        if gcd(pre, i) == 1:
            pre = pre * i % 1000000
        else:
            flg = False
if flg:
    print('pairwise coprime')
else:
    if g == 1:
        print('setwise coprime')
    else:
        print('not coprime')

Submission status: Wrong Answer

Solution code:
import sys
from math import gcd

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 19
MOD = 10 ** 9 + 7
EPS = 10 ** -10

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

N = INT()
A = LIST()

se = set(A)
if len(se) != len(A):
    print('not coprime')
    exit()

is_pc = 1
l = 1
for a in A:
    g = gcd(l, a)
    if g != 1:
        is_pc = 0
        break
    l = lcm(l, a)

is_sc = 1
g = 0
for a in A:
    g = gcd(g, a)
if g != 1:
    is_sc = 0

if is_pc:
    print('pairwise coprime')
elif is_sc:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 8)
from itertools import accumulate
from itertools import permutations
from itertools import combinations
from collections import defaultdict
from collections import Counter
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
import heapq
from copy import deepcopy
from decimal import Decimal
alf = list("abcdefghijklmnopqrstuvwxyz")
ALF = list("ABCDEFGHIJKLMNOPQRSTUVWXYZ")
#import numpy as np
INF = float("inf")
#d = defaultdict(int)
#d = defaultdict(list)
N = int(input())
def primes(n):#nまでの素数を列挙0は入れちゃダメ
    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 is_prime
A = list(map(int,input().split()))
MAX = max(A)
prime = primes(MAX)
pri = [i for i in  range(2,MAX+1) if prime[i]]
n = len(pri)
cnt = defaultdict(int)
def factorization(n): #2以上の整数n => [[素因数, 指数], ...]の2次元リストを返す
    arr = []
    temp = n
    for i in pri:
        if i > int(n**0.5):
            break
        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 factorization1(n): #2以上の整数n => [[素因数, 指数], ...]の2次元リストを返す
    arr = []
    temp = n
    for i in pri:
        if i > int(n**0.5) or i > MAX/(N-1):
            break
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        if temp > int(n**0.5) or temp >= MAX/(N-1):
            arr.append([temp, 1])
    if arr==[]:
        arr.append([n, 1])
    return arr
flag1 = 0
flag2 = 0
if N >= n+2:
    flag1 = 1
    for i in range(N):
        a = A[i]
        li = factorization1(a)
        for tu in li:
            b = tu[0]
            cnt[b] += 1
    for i in pri:
        a = cnt[i]
        if a == N:
            flag2 = 1
            break
    if flag2 == 1:
        print("not coprime")
    else:
        print("setwise coprime")
else:
    for i in range(N):
        a = A[i]
        li = factorization(a)
        for tu in li:
            b = tu[0]
            cnt[b] += 1
    for i in pri:
        a = cnt[i]
        if a == N:
            flag2 = 1
        if a >= 2:
            flag1 = 1
    if flag1 == 0:
        print("pairwise coprime")
    elif flag2 == 1:
        print("not coprime")
    else:
        print("setwise coprime")

Submission status: Wrong Answer

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

import itertools
import math
#
# ans_list = 1
not_pair = False
not_set = False
#
# for combi in itertools.combinations(A, 2):
#     ans = math.gcd(combi[0], combi[1])
#     if ans != 1:
#         not_pair = True
#         if ans_list == 1:
#             ans_list = ans
#         else:
#             ans_list = math.gcd(ans, ans_list)
#             if ans_list != 1:
#                 not_set = True
#                 break
#
# if not not_pair:
#     print("pairwise coprime")
# elif not not_set:
#     print("setwise coprime")
# else:
#     print("not coprime")

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

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

    return arr

fact_list = []
all_fact = []
set_fact = set(factorization(A[0]))
for a in A:
    fact = factorization(a)
    fact_list.append(fact)
    all_fact += fact
    set_fact = set_fact & set(fact)
# print(set_fact)

if len(all_fact) == len(set(all_fact)):
    print("pairwise coprime")
elif set_fact == set():
    print("setwise coprime")

else:
    print("not 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)
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:
                # vis.add(mul)
                d[p]=d.get(p,0)+1
    p+=1
g=a[0]
for factor,freq in d.items():
    if freq>1:
        not_pairwise = 1
        break
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:
def gcd(u, v):
    if u == v:
        return u
    elif u == 0:
        return v
    elif v == 0:
        return u
    # u is even
    elif u & 1 == 0:
        # v is even
        if v & 1 == 0:
            return 2*gcd(u >> 1, v >> 1)
        # v is odd
        else:
            return gcd(u >> 1, v)
    # u is odd
    elif u & 1 != 0:
        # v is even
        if v & 1 == 0:
            return gcd(u, v >> 1)
        # v is odd and u is greater than v
        elif u > v and v & 1 != 0:
            return gcd((u-v) >> 1, v)
        # v is odd and u is smaller than v
        else:
            return gcd((v-u) >> 1, u)

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

out = ""
num = 1
for i in range(N-1):
    if out != "not coprime" and gcd(As[i],As[i+1]) == 1:
        out = "pairwise coprime"
    elif gcd(num, As[i+1]) == 1 and i+1 == N:
        out = "setwise coprime"
    else:
        out = "not coprime"
    num = gcd(num, As[i])

print(out)

Submission status: Wrong Answer

Solution code:
import math
from collections import deque
N=int(input())
A=[int(x) for x in input().split()]
gcd=A[0]
for i in range(1,N):
    gcd=math.gcd(gcd,A[i])
if gcd!=1:
    print("not coprime")
else:
    flag=1
    maxA=max(A)
    minA=min(A)
    if minA*2>maxA:
        flag=0
    else:
        primeornot=[1]*(maxA+1)
        A=sorted(A)
        deA=deque(A)
        while(len(deA)!=0):
            now=deA.popleft()
            if primeornot[now]==0:
                flag=0
                break
            index=now
            while(index<maxA+1):
                primeornot[index]=0
                index+=now

    if flag==0:
        print("pairwise coprime")
    else:
        print("setwise coprime")

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
import collections
from math import gcd
from functools import reduce

from random import randint

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

def find_gcd(list):
    x = reduce(gcd, list)
    return x

def find_lcm(list):
    x = reduce(lambda a,b: lcm(a,b)% MOD, list)
    return x

MOD = 10**9 + 7
def solve(N: int, A: "List[int]"):



    # q2 = True
    # for a in A:
    #     for b in A:
    #         if a!=b and gcd(a, b) != 1:
    #             q2 = False
    #             break

    prod = 1
    for a in A:
        prod *= a 
        prod = prod % MOD

    q1 = reduce(gcd, A) == 1
    q2 = find_lcm(A) == prod

    if q1 and q2:
        print('pairwise coprime')
    elif q1:
        print('setwise coprime')
    else:
        print('not coprime')
    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"

    solve(N, A)

if __name__ == '__main__':
    main()