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:
def examA():
    D,T,S = LI()
    if (D-1)//S<T:
        ans = "Yes"
    else:
        ans = "No"
    print(ans)
    return

def examB():
    S = SI()
    T = SI()
    s = len(S)
    t = len(T)
    ans = t
    for i in range(s-t+1):
        cnt = 0
        for j in range(t):
            if S[i+j]!=T[j]:
                cnt += 1
        ans = min(ans,cnt)

    print(ans)
    return

def examC():
    N = I()
    A = LI()
    S = sum(A)
    cnt = 0
    for a in A:
        cnt += (S-a)*a
        cnt %= mod
    ans = cnt * pow(2,mod-2,mod) % mod
    print(ans)
    return

def examD():
    class UnionFind():
        def __init__(self, n):
            self.parent = [-1 for _ in range(n)]
            # 正==子: 根の頂点番号 / 負==根: 連結頂点数

        def reset(self):
            self.parent = [-1] * len(self.parent)

        def find(self, x):
            # 要素xが属するグループの根を返す
            if self.parent[x] < 0:
                return x
            else:
                self.parent[x] = self.find(self.parent[x])
                return self.parent[x]

        def unite(self, x, y):
            # 要素xが属するグループと要素yが属するグループとを併合する
            x, y = self.find(x), self.find(y)
            if x == y:
                return False
            else:
                if self.size(x) < self.size(y):
                    x, y = y, x
                self.parent[x] += self.parent[y]
                self.parent[y] = x

        def same(self, x, y):
            # 要素x, yが同じグループに属するかどうかを返す
            return self.find(x) == self.find(y)

        def size(self, x):
            # 要素xが属するグループのサイズ（要素数）を返す
            x = self.find(x)
            return -self.parent[x]

        def is_root(self, x):
            # 要素の根をリストで返す
            return self.parent[x] < 0

        def roots(self):
            # すべての根の要素をリストで返す
            return [i for i, x in enumerate(self.parent) if x < 0]

        def members(self, x):
            # 要素xが属するグループに属する要素をリストで返す
            root = self.find(x)
            return [i for i in range(self.n) if self.find(i) == root]

        def group_count(self):
            # グループの数を返す
            return len(self.roots())

        def all_group_members(self):
            # {ルート要素: [そのグループに含まれる要素のリスト], ...}の辞書を返す
            return {r: self.members(r) for r in self.roots()}
    N, M = LI()
    uf = UnionFind(N)
    for _ in range(M):
        a, b = LI()
        a -= 1; b -= 1
        uf.unite(a,b)
    cnt = 0
    for i in range(N):
        cnt = max(cnt,uf.size(i))

    ans = cnt
    print(ans)
    return

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

    def isPrime(n):
        if n == 1: return False

        for k in range(2, int(math.sqrt(n)) + 1):
            if n % k == 0:
                return False

        return True

    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 = I()
    A = LI()
    cur = A[0]
    for i in range(1,N):
        cur = gcd(cur,A[i])
        if cur==1:
            break
    if cur!=1:
        print("not coprime")
        return

    n = max(A)

    P = primes(n)

    #print(P)

    D = [False]*(n+1)
    for a in A:
        if a==1:
            continue
        if D[a]:
            print("setwise coprime")
            return
        D[a] = True

    for p in P:
        flag = False
        for i in range(1,1+n//p):
            cur = i
            while(cur*p<=n):
                if D[cur]:
                    if flag:
                        print("setwise coprime")
                        return
                    flag = True

                cur += 1
    print("pairwise coprime")
    return

def examF():
    ans = 0
    print(ans)
    return

from decimal import getcontext,Decimal as dec
import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def DI(): return dec(input())
def LDI(): return list(map(dec,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = dec("0.000000000001")
alphabet = [chr(ord('a') + i) for i in range(26)]
alphabet_convert = {chr(ord('a') + i): i for i in range(26)}

getcontext().prec = 28

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examE()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
"""

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7) #再帰関数の上限,10**5以上の場合python
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque, defaultdict
#deque(l), pop(), append(x), popleft(), appendleft(x)
#q.rotate(n)で → にn回ローテート
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate,combinations,permutations,product#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
from functools import reduce,lru_cache#pypyでもうごく
#@lru_cache(maxsize = None)#maxsizeは保存するデータ数の最大値、2**nが最も高効率
from decimal import Decimal
from argparse import ArgumentParser

args=ArgumentParser()
args.add_argument('-loc', '--local', type=bool,default=False)
LOCAL=args.parse_args().local

def input(): 
    x=sys.stdin.readline(); 
    if x[-1]=="\n": 
        return x.rstrip() 
    return x
    
def printe(*x):_=print("## ",*x,file=sys.stderr) if LOCAL else 0
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def binr(x): return bin(x)[2:]
def bitcount(x): #xは64bit整数
    x= x - ((x >> 1) & 0x5555555555555555)
    x= (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x= (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f 
    x+= (x >> 8); x+= (x >> 16); x+= (x >> 32) 
    return x & 0x7f

def main():
    mod = 1000000007
    #w.sort(key=itemgetter(1),reverse=True)  #二個目の要素で降順並び替え

    N = int(input())
    #N, K = map(int, input().split())
    A = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列
    tot=0
    def primes(n):
        a = set()
        while n % 2 == 0:
            a.add(2)
            n //= 2
        f = 3
        while f * f <= n:
            if n % f == 0:
                a.add(n)
                n //= f
            else:
                f += 2
        if n != 1:
            a.add(n)
        return a

    for a in A:
        tot=math.gcd(tot,a)
    if tot!=1:
        print("not coprime")
        return
    if N>78498:
        print("setwise coprime")
        return 
    cur=set()
    for a in A:
        s=primes(a)
        if len(s&cur)!=0:
            print("setwise coprime")
            return 
        cur|=s
    print("pairwise coprime")


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

    for i in range(2, n + 1):
        if is_prime[i - 1]:
            j = i
            f = 0
            while j <= n:
                if f and j in b:
                    return False
                if j in b:
                    f = True
                is_prime[j - 1] = False
                j += i
    return True


from math import gcd
from functools import reduce


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


n = int(input())
a = list(map(int, input().split()))
b = set(a)
if not (1 in a and a.count(1) < len(a)) and sieve(10 ** 6):
    print("pairwise coprime")
elif gcd_list(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()))

a = 1
result = []
for x in arr:
    result.append(gcd(a, x))
    a *= x

if result.count(1) == len(arr):
    ans = "pairwise coprime"
elif min(result) == 1:
    ans = "setwise coprime"
else:
    ans = "not coprime"

print(ans)

Submission status: Wrong Answer

Solution code:
import math
N = int(input())
A = list(map(int,input().rstrip().split(" ")))
M = int(math.sqrt(max(A))) + 1
sosuu = [2]
for i in range(3,M,2):
    for j in sosuu:
        if i % j == 0:
            break
    else:
        sosuu.append(i)

lis = [0 for i in range(1000)]
for i in A:
    for j in sosuu:
        if i % j == 0:
            lis[j] += 1
pair = True
setw = True
for i in sosuu:
    if lis[i] == len(A):
        setw = False
    if lis[i] >= 2:
        pair = False
if pair:
    print("pairwise coprime")
elif setw:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
p = [0 for _ in range(10**6)]
pr = []
pr2 = [0 for _ in range(10**3)]
for i in range(2,10**3):
  if pr2[i] == 0:
    pr.append(i)
    now = i
    while True:
      try:
        pr2[now] = 1
        now += i
      except:
        break
#print(pr)
for x in a:
  d = int(x)
  for y in pr:
    if d % y == 0:
      p[y] += 1
      while d % y == 0:
        d //= y
  if d != 1:
    p[d] += 1
  #print(p)
if max(p) == 1:
  print('pairwise coprime')
  exit()
now = int(a[0])
for x in a:
  big,sml = x,now
  while big % sml != 0:
    #print(big,sml)
    big,sml = sml,big%sml
  now = sml
  #print(now)
if now == 1:
  print('setwise coprime')
else:
  print('no coprime')
  #print(now)

Submission status: Wrong Answer

Solution code:
import sys
from math import gcd
input = sys.stdin.buffer.readline

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


def primes(n):
    ass = []
    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
    for i in range(len(is_prime)):
        if is_prime[i]:
            ass.append(i)
    return ass

p = primes(1003)



g = a[0]

for e in a:
    g = gcd(g,e)


if g != 1:
    print("not coprime")
else:
    s = set()
    for e in a:
        if e == 1:
            continue
        if e in s:
            print("setwise coprime")
            exit()
        for d in p:
            if e < d:
                break
            if e%d == 0:
                if d in s:
                    print("setwise coprime")
                    exit()
                s.add(d)
        s.add(e)
    print("pairwise coprime")

Submission status: Wrong Answer

Solution code:
from math import gcd


def pairwise_coprime(a):
    check = [set() for _ in range(10 ** 6 + 10)]
    for i, aa in enumerate(a):
        now = aa
        while now % 2 == 0:
            if i > 0 and len(check[2]) > 0 and i not in check[2]:
                return False
            now //= 2
            check[2].add(i)
        f = 3
        while f * f <= now:
            if now % f == 0:
                if i > 0 and len(check[f]) > 0 and i not in check[f]:
                    return False
                now //= f
                check[f].add(i)
            else:
                f += 2
        if now != 1:
            check[now].add(i)
    return True


def main():
    n = int(input())
    a = list(map(int, input().split()))
    ac_gcd = [a[-1] for _ in range(n)]
    for i in range(n - 2, -1, -1):
        ac_gcd[i] = gcd(a[i], ac_gcd[i + 1])
    is_pc = pairwise_coprime(a)
    if set(ac_gcd[:-1]) == {1} and is_pc:
        print("pairwise coprime")
    elif ac_gcd[0] == 1:
        print("setwise coprime")
    else:
        print("not coprime")


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from math import gcd
from functools import reduce
def osa_k(n=10**6):
  p=list(range(n+1))
  for i in range(2,int(n**.5)):
    if p[i]<i:continue
    for j in range(i*i,n+1,i):
      if p[j]==j:p[j]=i
  return p
def fact_o(n):
  a=[]
  f=0
  while n>1:
    if f!=p[n]:ans[p[n]]+=1
    f=p[n]
    n//=p[n]
  return 0
p=osa_k()
n=int(input())
a=list(map(int,input().split()))
ans=[0]*(10**6+1)
for i in a:
  fact_o(i)
if max(ans)==1:print('pairwise coprime')
elif reduce(gcd,a)==1:print('setwise coprime')
else:print('not coprime')

Submission status: Wrong Answer

Solution code:
from math import gcd
n=int(input())
arr=list(map(int,input().split()))
p=[i for i in range(10**6+1)]
se=[0]*(10**6+1)
for i in arr:
    se[i]=1
f=0
for i in range(2,10**3+1):
    if p[i]==i:
        c=0
        if se[i]:
            c += 1
        for j in range(i*i,10**6+1,i):
            if p[j]==j:
                if se[j]:
                    c+=1
                if c>=2:
                    f=1
                    break
        if f:
            break
if f==0:
    print("pairwise coprime")
else:
    gc=arr[0]
    for i in arr[1:]:
        gc=gcd(i,gc)
    if gc==1:
        print("setwise coprime")
    else:
        print("not coprime")

Submission status: Wrong Answer

Solution code:
import os
import sys

import numpy as np


def solve(inp):
    aaa = inp[1:]
    aaa = aaa[aaa != 1]
    n = len(aaa)
    if n > 78498:
        return -1
    if n == 0:
        return 1
    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]
    pairwise = 1
    for p in PRIMES:
        cp = (aaa % p == 0).sum()
        if cp == n:
            return -1
        if cp > 1:
            pairwise = 0
    return pairwise


if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC

    cc = CC('my_module')
    cc.export('solve', '(i8[:],)')(solve)
    cc.compile()
    exit()

if os.name == 'posix':
    # noinspection PyUnresolvedReferences
    from my_module import solve
else:
    from numba import njit

    solve = njit('(i8[:],)', cache=True)(solve)
    print('compiled', file=sys.stderr)

inp = np.fromstring(sys.stdin.read(), dtype=np.int64, sep=' ')
ans = solve(inp)
print(['setwise coprime', 'pairwise coprime', 'not coprime'][ans])

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    *A, = map(int, input().split())

    B = [0] * (10 ** 6 + 1)
    for x in A:
        B[x] += 1

    setwise = False

    d = 2
    e = d
    cnt = 0
    while e <= 10 ** 6:
        if B[e]:
            cnt += 1
        e += d
    if cnt == N:
        print('not coprime')
        return
    elif cnt > 1:
        setwise = True

    d = 3
    while d <= 10 ** 6:
        e = d
        cnt = 0
        while e <= 10 ** 6:
            if B[e]:
                cnt += 1
            e += d
        if cnt == N:
            print('not coprime')
            return
        elif cnt > 1:
            setwise = True
        d += 2

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


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import math
N = int(input())
A = list(map(int,input().split()))
ls = []
ls.append(A[0])
now = A[0]
for i in range(1,N):
    ls.append(math.gcd(now,A[i]))
    now = math.gcd(now,A[i])
if ls[1:N].count(1) == N-1:
    print("pairwise coprime")
else:
    if ls[N-1] == 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

g = a[0]
l = 1
f = True
for i in range(n):
    if gcd(a[i],l)!=1:
        f = False
    x = gcd(g,a[i])
    l = g*a[i]//x
    g = x

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

Submission status: Wrong Answer

Solution code:
from math import *
n = int(input())
a = list(map(int,input().split()))
g = 0
for i in range(n):
    g = gcd(g,a[i])
    
if g == 1:
    a = list(set(a))
    a = sorted(a)
    m = len(a)
    
    if m != n:
        print("setwise coprime")
        
    else:
    
        b = [True]*(10**6+1)

        for i in range(m):
            b[a[i]] = False

        sw = 1
        
        for i in range(2, 5*10**5+1):
            q = 0
            j = 1
            while i*j <= 10**6:
                if b[i*j] == False:
                    q += 1
                j += 1
            if q >= 2:
                sw = 0
                break

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

Submission status: Wrong Answer

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

d = {}
g = a[0]

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

f = 1

for ai in a:
    g = gcd(g, ai)
    for n, cnt in factorization(ai):
        if n in d:
            f = 0
            break
        else:
            d[n] = 1

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

Submission status: Wrong Answer

Solution code:
import math
from functools import reduce

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

def gcd_list(numbers):
    return reduce(math.gcd, numbers)
N=int(input())
D=[int(s) for s in input().split()]
if gcd_list(D)!=1:
    print("not coprime")
else:
    for i in range(N-1):
        for j in range(i+1,N):
            if gcd(D[i],D[j])!=1:
                print("setwise coprime")
                break
            elif i==N-1 and j==N:
                print("pairwise coprime")

Submission status: Wrong Answer

Solution code:
import sys; input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**7)
from collections import defaultdict
con = 10 ** 9 + 7; INF = float("inf")

from math import gcd

def getlist():
	return list(map(int, input().split()))

#処理内容
def main():
	N = int(input())
	A = getlist()
	GCD = A[0]
	for i in range(N):
		GCD = gcd(GCD, A[i])

	if GCD != 1:
		print("not coprime")
		return

	B = []
	jud = 0
	for i in A:
		if i != 1:
			B.append(i)
		else:
			jud = 1

	B = list(set(B))
	if jud == 1:
		B.append(1)
	M = len(B)
	if M <= 10 ** 3:
		for i in range(M):
			for j in range(i + 1, M):
				if gcd(B[i], B[j]) != 1:
					print("setwise coprime")
					return
		print("pairwise coprime")
	else:
		print("setwise coprime")

if __name__ == '__main__':
	main()

Submission status: Wrong Answer

Solution code:
import sys
from math import gcd
input = sys.stdin.buffer.readline

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


def primes(n):
    ass = []
    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
    for i in range(len(is_prime)):
        if is_prime[i]:
            ass.append(i)
    return ass

p = primes(1003)



g = a[0]
for e in a:
    g = gcd(g,e)

if g != 1:
    print("not coprime")
else:
    s = set()
    for e in a:
        if e in s:
            print("setwise coprime")
            exit()
        for d in p:
            if e < d:
                break
            if e%d == 0:
                if d in s:
                    print("setwise coprime")
                    exit()
                s.add(d)
        s.add(e)
    print("pairwise coprime")

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
p = [0 for _ in range(10**6)]
for x in a:
  d = int(x)
  for y in range(2,10**3):
    if d % y == 0:
      p[y] += 1
      while d % y == 0:
        d //= y
  if d != 1:
    p[d] += 1
  #print(p)
if max(p) == 1:
  print('pairwise coprime')
  exit()
now = int(a[0])
for x in a:
  big,sml = x,now
  while big % sml != 0:
    #print(big,sml)
    big,sml = sml,big%sml
  now = sml
  #print(now)
if now == 1:
  print('setwise coprime')
else:
  print('no coprime')
  #print(now)

Submission status: Wrong Answer

Solution code:
from itertools import groupby

class Osa_k:
    def __init__(self, n_max):
        self.min_factor = min_factor = list(range(n_max+1))
        for i in range(2, int(n_max**0.5)+1):
            if min_factor[i] == i:
                for j in range(i*i, n_max+1, i):
                    if min_factor[j] == j:
                        min_factor[j] = i

    def __call__(self, n):
        min_factor = self.min_factor
        n_twoes = (n & -n).bit_length() - 1  # 最悪ケースでは速くなる
        res = [2] * n_twoes
        n >>= n_twoes
        while n > 1:
            p = min_factor[n]
            res.append(p)
            n //= p
        return res

def main():
    N = int(input())
    A = list(map(int, input().split()))
    osa_k = Osa_k(1010101)
    Factors = [osa_k(a) for a in A]
    factors = Factors[0]
    st0 = set(factors)  # 0 になれば setwize
    st1 = set(factors)  # 重複しなければ pairwise
    pairwise = True
    for factors in Factors[1:]:
        for f, _ in groupby(factors):
            if f in st1:
                pairwise = False
            else:
                st1.add(f)
            if f in st0:
                st0.remove(f)
    if pairwise:
        print("pairwise coprime")
    elif not st0:
        print("setwise coprime")
    else:
        print("not coprime")

main()

Submission status: Wrong Answer

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

    for i in range(2, n + 1):
        if is_prime[i - 1]:
            j = i
            f = 0
            while j <= n:
                if f and j in b:
                    return False
                if j in b:
                    f = True
                is_prime[j - 1] = False
                j += i
    return True


from math import gcd
from functools import reduce


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


n = int(input())
a = list(map(int, input().split()))
b = set(a)
if sieve(10 ** 6):
    print("pairwise coprime")
elif gcd_list(a) == 1:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Wrong Answer

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import accumulate, permutations, combinations, product, groupby, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
A = LIST()

if reduce(gcd, A) != 1:
    print("not coprime")
    exit()

def primes_for(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, n + 1):
        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]]

l = primes_for(10**3+1)

for x in l:
    cnt = 0
    for y in A:
        if y%x == 0:
            cnt += 1
    if cnt >= 2:
        print("setwise coprime")
        break
else:
    print("pairwise coprime")

Submission status: Wrong Answer

Solution code:
from math import gcd
n=int(input())
arr=list(map(int,input().split()))
p=[i for i in range(10**6+1)]
se=[0]*(10**6+1)
for i in arr:
    se[i]=1
f=0
for i in range(2,10**3+1):
    if p[i]==i:
        c=0
        for j in range(i*i,10**6+1,i):
            if p[j]==j:
                if se[j]:
                    c+=1
                if c>=2:
                    f=1
                    break
        if f:
            break
if f==0:
    print("pairwise coprime")
else:
    gc=arr[0]
    for i in arr[1:]:
        gc=gcd(i,gc)
    if gc==1:
        print("setwise coprime")
    else:
        print("not coprime")

Submission status: Wrong Answer

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def enum_primes(n):
    flag_num = (n + 1) // 2
    prime_flag = [True] * flag_num

    for num in range(3, int(n ** 0.5) + 1, 2):
        idx = (num - 1) // 2 - 1
        if prime_flag[idx]:
            for j in range(idx + num, flag_num, num):
                prime_flag[j] = False

    primes = [2]
    temp = [(i + 1) * 2 + 1 for i in range(flag_num) if prime_flag[i]]
    primes.extend(temp)

    return primes


def main():
    N = int(readline())
    A = list(map(int, readline().split()))
    primes = enum_primes(10 ** 6 + 1)

    def judge():
        seq = [False] * (10 ** 6 + 1)
        A.sort()

        for x in A:
            if seq[x]:
                return False
            seq[x] = True

        for prime in primes:
            cnt = 0
            for i in range(prime, 10 ** 6 + 1, prime):
                if seq[i]:
                    cnt += 1
            if cnt > 1:
                return False
        return True

    if judge():
        print("pairwise coprime")
    else:
        from math import gcd
        cur = A[0]
        for x in A[1:]:
            cur = gcd(cur, x)

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


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:

import sys
input = sys.stdin.buffer.readline
from math import gcd

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

# Mまでの素数全列挙(エラトステネスの篩)
def primes(M):
    B = set(A)
    if len(A) != len(B): return False
    ok = True
    is_prime = [-1 for _ in range(M+1)]
    for m in range(2, M+1):
        if is_prime[m] == -1:
            is_prime[m] = 1
            cnt = 0
            if m in B: cnt += 1
            l = 2
            while m*l <= M:
                if m*l in B:
                    cnt += 1
                is_prime[m*l] = 0
                l += 1
            if cnt > 1:
                ok = False
                break
    return ok

def check():
    k = A[0]
    for a in A:
        k = gcd(a, k)
    return k == 1

if primes(10**6):
    ans = "pairwise coprime"
elif check():
    ans = "setwise coprime"
else:
    ans = "not coprime"
print(ans)

Submission status: Wrong Answer

Solution code:
import math

def solve(arr,n):
    flag = True

    for i in range(1,n):
        if math.gcd(arr[i-1],arr[i]) != 1:
            flag = False
    
    if flag == True:
        return "pairwise coprime"

    elif flag != True:
        res = arr[0]
        for i in arr[1:]:
            res = math.gcd(res, i)
        if res != 1:
            return "not coprime"
        else:
            return "setwise coprime"



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

print(solve(arr,n))