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  gcd( a,  b): 
    while a != 0: 
        a, b = b % a, a
    return b
N = int(input())
A = [int(s) for s in input().split()]

def is_pw(N, A):
    prod = 1
    for a in A:
        if gcd(a, prod) == 1:
            prod *= a
        else:
            return False
    return True

def is_sw(N,A):
    n = A[0]
    for a in A:
        n = gcd(a, n) 
        if n == 1:
            return True
    return False

def main(N, A):
    if N < 10000:
        if is_pw(N, A):
            print('pairwise coprime')
            return

    if is_sw(N, A):
        print('setwise coprime')
        return 
    print('not coprime')
main(N, A)

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())
a=[int(x) for x in input().split()]

if gcd_list(a)==1:
  c=[]
  for i in range(n-1):
    if math.gcd(a[i],a[i+1])!=1:
      c.append(False)
      break
  if c==[]:
    print("pairwise coprime")
  else:
    print("setwise coprime")
else:
  print("not coprime")

Submission status: Wrong Answer

Solution code:
from math import sqrt, gcd
def factoring(k): #kを因数分解し、素因数とその個数を辞書に入れて返す。
    dic = dict()
    n = int(sqrt(k))+2
    for i in range(2, n):
        count = 0
        while k%i == 0:
            count += 1
            k = k//i
        if count != 0:
            dic[i] = count
    if k != 1: #sqrt(k)までチェックしてもkが1になっていない --> kが素因数
        dic[k] = 1
    return dic

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


from collections import defaultdict


dic = defaultdict(int)

if N <= 78498:
    count = 0
    for a in A:
        tmp = factoring(a)
        for i in tmp:
            dic[i] = max(tmp[i], dic[i])
            count += tmp[i]

    tmp = 0
    for i in dic:
        tmp += dic[i]

    if count == tmp:
        print ('pairwise coprime')
        exit()

GCD = A[0]
for a in A:
    GCD = gcd(GCD, a)
    if GCD == 1:
        break

if GCD == 1:
    print ('setwise coprime')
else:
    print ('not coprime')

Submission status: Wrong Answer

Solution code:
# coding: utf-8
from math import gcd

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

N=int(input())
A=list(map(int,input().split()))
plime_flg = [True for i in range(10**6)]
pc_flg=True

for i in range(N):
    l=factorization(A[i])
    for j in range(len(l)):
        if plime_flg[l[j][0]]:
            plime_flg[l[j][0]]=False
        else:
            pc_flg=False

x = A[-1]

for i in range(N-1):
    x=gcd(x,A[i])


if pc_flg:
    print("pairwise coprime")
elif x==1:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Wrong Answer

Solution code:
from math import gcd


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


def factorize(N):  # 素因数分解
    for p in prime_list:
        if p * p > N:
            break
        if N % p == 0 and (p in num):
            print('setwise coprime')
            exit()
        while N % p == 0:
            N //= p
            num.add(p)
    if N > 1:
        num.add(N)


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

ans = 0
for ai in a:
    ans = gcd(ans, ai)
if ans != 1:
    print('not coprime')
    exit()

prime_list = eratosthenes(10 ** 6)
num = set()
for ai in a:
    factorize(ai)
else:
    print('pairwise coprime')

Submission status: Wrong Answer

Solution code:
from bisect import *
from collections import *
from itertools import *
import functools
import sys
import math
from decimal import *
from copy import *
from heapq import *
from fractions import *
getcontext().prec = 30
MAX = sys.maxsize
MAXN = 1000010
MOD = 10**9+7
spf = [i for i in range(MAXN)]
spf[0]=-1
def sieve():
    for i in range(2,MAXN,2):
        spf[i] = 2
    for i in range(3,int(MAXN**0.5)+1):
        if spf[i]==i:
            for j in range(i*i,MAXN,i):
                if spf[j]==j:
                    spf[j]=i
def fib(n,m):
    if n == 0:
        return [0, 1]
    else:
        a, b = fib(n // 2)
        c = ((a%m) * ((b%m) * 2 - (a%m)))%m
        d = ((a%m) * (a%m))%m + ((b)%m * (b)%m)%m
        if n % 2 == 0:
            return [c, d]
        else:
            return [d, c + d]
 
def charIN(x= ' '):
    return(sys.stdin.readline().strip().split(x))
 
def arrIN(x = ' '):
    return list(map(int,sys.stdin.readline().strip().split(x)))
 
def ncr(n,r):
    num=den=1
    for i in range(r):
        num = (num*(n-i))%MOD
        den = (den*(i+1))%MOD
 
    return (num*(pow(den,MOD-2,MOD)))%MOD
 
def flush():
    return sys.stdout.flush()




'''*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*'''
sieve()

n = int(input())
a = arrIN()
d = defaultdict(list)

for i in range(n):
    d[spf[a[i]]].append(i)

g = a[0]

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

if len(set(a))<n:
    if len(set(a))==1:
        if a[0]==1:
            print('pairwise coprime')
        else:
            print('not coprime')
    elif g==1:
        print('setwise coprime')
    else:
        print('not coprime')
    exit(0)

for i in d.keys():
    if i>1 and len(d[i])>1:
        if g!=1:
            print('not coprime')
        else:
            print('setwise coprime')
        break
else:
    print('pairwise coprime')

Submission status: Wrong Answer

Solution code:
#dt = {} for i in x: dt[i] = dt.get(i,0)+1
import sys;input = sys.stdin.readline
inp,ip = lambda :int(input()),lambda :[int(w) for w in input().split()]

from fractions import gcd
n = inp()
x = ip()
ans = 'pairwise coprime'
prev = x[0]
for i in range(1,n):
    t = gcd(prev,x[i])
    #print(t)
    prev = t
    if t != 1:
        ans = 'setwise coprime'
if t != 1:
    ans = 'not coprime'
print(ans)

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):
        x=0
        for j in range(i+1,N):
            if gcd(D[i],D[j])!=1:
                print("setwise coprime")
                x+=1
                break
            elif i==N-1 and j==N:
                print("pairwise coprime")
        if x==1:
            break

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict, Counter, namedtuple, deque
import itertools
import functools
import bisect
import heapq
import math
import copy
# from fractions import gcd

MOD = 10 ** 9 + 7
# MOD = 998244353
# sys.setrecursionlimit(10**8)

n = int(input())
A = set(map(int, input().split()))
N = 10**6
furui = [True]*(N+1)

state = "pairwise coprime"
for i in range(2, N):
    if not furui[i]:
        continue
    count = 0
    k = i
    while k <= N:
        if k in A:
            count += 1
            if count == 2:
                state = "setwise coprime"
            if count == n:
                print("not coprime")
                exit()

        furui[k] = False
        k += i

print(state)

Submission status: Wrong Answer

Solution code:
from math import gcd
N = int(input())
a = list(map(int, input().split()))
ans = a[0]
flag = True
for i in range(1, N):
    ans = gcd(ans, a[i])
    if flag and ans != 1:  
      flag = False
      
if flag == False and ans == 1:
  print("setwise coprime")
elif ans != 1:
  print("not coprime")
else:
  print("pairwise coprime")

Submission status: Wrong Answer

Solution code:
from functools import reduce
from math import gcd

n = int(input())
A = list(int(x) for x in input().split())

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

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

sieve = get_sieve_of_eratosthenes(10**3)
for prime in sieve:
    count = 0
    for a in A:
        if a % prime == 0:
            count += 1
        if count > 1:
            print("setwise coprime")
            exit()

print("pairwise coprime")

Submission status: Wrong Answer

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

def calc_primes(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

primes = calc_primes(int(math.sqrt(10**6)))

def factorize(n):
    factors = set()
    for prime in primes:
        while n % prime == 0:
            n //= prime
            factors.add(prime)
    return factors

factors = factorize(A[0])
union = factors
intersection = factors

is_pairwise = True

for a in A[1:]:
    factors = factorize(a)
    if is_pairwise:
        if union.intersection(factors):
            is_pairwise = False
        union = union.union(factors)
    if intersection:
        intersection = intersection.intersection(factors)

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

Submission status: Wrong Answer

Solution code:
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 gcd(a,b):
  while b:
    a,b = b,a%b
  return a  
  
n = int(input())
A = list(map(int,input().split()))

p = A[0]
for a in A[1:]:
  p = gcd(a,p)

primes = [0]*(10**6+2)
  
for a in A:
  B = set(prime_factorize(a))
  for b in B:
    primes[b]+=1
  
  
if p == 1:
  if max(primes)==1:
    print('pairwise coprime')
  else:
    print('setwise coprime')
else:
  print('not coprime')

Submission status: Wrong Answer

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

def fact(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])

    ret = set()
    for tmp in arr:
        ret.add(tmp[0])
    return ret

from collections import defaultdict
ansand=set(fact(a[0]))
cntd=defaultdict(int)
for i in range(1,len(a)):
    lis = set(fact(a[i]))
    ansand = ansand & lis
    for i in lis:
        cntd[i]+=1

if len(ansand)!=0:
    print("not coprime")
    exit()

for c in cntd.values():
    if c>1:
        print("setwise coprime")
        exit()
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)
f=0
for i in arr:
    if i!=1 and se[i]:
        f=1
    se[i]=1

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 math
def a(n):
    arr = 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
            arr.add(i)

    if temp!=1:
        arr.add(temp)
    if arr==[]:
        arr.add(n)
    return arr
N=int(input())
L=list(map(int,input().split()))
L=range(10**6)
L=list(set(L))
gc=L[0]
for i in L:
  gc=math.gcd(i,gc)
  if gc==1:
    break
if gc!=1:
  print("not coprime")
  exit()
ans=set()
for i in L:
  if a(i)&ans!=set():
    print("setwise coprime")
    exit()
  ans=a(i)|ans
print("pairwise coprime")

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(f)
                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:
from math import gcd


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


def factorize(N):  # 素因数分解
    for p in prime_list:
        if p * p > N:
            break
        if N % p == 0 and (p in num):
            print('setwise coprime')
            exit()
        while N % p == 0:
            N //= p
            num.add(p)
    if N > 1:
        num.add(N)


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

ans = 0
for ai in a:
    ans = gcd(ans, ai)
if ans != 1:
    print('not coprime')
    exit()

prime_list = eratosthenes(10 ** 6)
num = set()
for ai in a[::-1]:
    factorize(ai)
else:
    print('pairwise coprime')

Submission status: Wrong Answer

Solution code:
from bisect import *
from collections import *
from itertools import *
import functools
import sys
import math
from decimal import *
from copy import *
from heapq import *
from fractions import *
getcontext().prec = 30
MAX = sys.maxsize
MAXN = 1000010
MOD = 10**9+7
spf = [i for i in range(MAXN)]
spf[0]=-1
def sieve():
    for i in range(2,MAXN,2):
        spf[i] = 2
    for i in range(3,int(MAXN**0.5)+1):
        if spf[i]==i:
            for j in range(i*i,MAXN,i):
                if spf[j]==j:
                    spf[j]=i
def fib(n,m):
    if n == 0:
        return [0, 1]
    else:
        a, b = fib(n // 2)
        c = ((a%m) * ((b%m) * 2 - (a%m)))%m
        d = ((a%m) * (a%m))%m + ((b)%m * (b)%m)%m
        if n % 2 == 0:
            return [c, d]
        else:
            return [d, c + d]
 
def charIN(x= ' '):
    return(sys.stdin.readline().strip().split(x))
 
def arrIN(x = ' '):
    return list(map(int,sys.stdin.readline().strip().split(x)))
 
def ncr(n,r):
    num=den=1
    for i in range(r):
        num = (num*(n-i))%MOD
        den = (den*(i+1))%MOD
 
    return (num*(pow(den,MOD-2,MOD)))%MOD
 
def flush():
    return sys.stdout.flush()




'''*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*'''
sieve()

n = int(input())
a = arrIN()
d = defaultdict(list)

for i in range(n):
    d[spf[a[i]]].append(i)

g = a[0]

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

if len(set(a))<n:
    if g==1:
        print('setwise coprime')
    else:
        print('not coprime')
    exit(0)

for i in d.keys():
    if i>1 and len(d[i])>1:
        if g!=1:
            print('not coprime')
        else:
            print('setwise coprime')
        break
else:
    print('pairwise coprime')

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
# E

import sys
from collections import defaultdict, deque
from heapq import heappush, heappop
import math
import bisect
input = sys.stdin.readline

# 再起回数上限変更
# sys.setrecursionlimit(1000000)

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

def divisor(n: int) -> list:
    res = []
    if n == 1:
        return [1]

    for i in range(1, n):
        if n % i == 0:
            res.append(i)
            if i > 1:
                dic[i]+=1
            if i != n / i:
                res.append(int(n / i))
                dic[int(n / i)] += 1
        if (i + 1) * (i + 1) > n:
            # res.sort()
            return res

for a in A:
    res = divisor(a)

flg_pair = True
flg_step = True

for a in dic.values():
    if a > 1:
        flg_pair = False
    if a == N:
        flg_step = False

if flg_pair:
    print('pairwise coprime')
elif flg_step:
    print('stepwise coprime')
else:
    print('not coprime')

Submission status: Wrong Answer

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

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

m = max(A)

n = int(m**0.5)+1
is_prime = [True]*(n+1)
is_prime[0] = 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
primes = [i for i in range(n+1) if is_prime[i]]


for p in primes:
    flag = 0
    for i in range(N):
        if A[i] % p == 0:
            if flag:
                break
            flag = 1
    else:
        continue

    # not pairwise coprime
    gcd_set = reduce(gcd, A)
    if gcd_set == 1:
        print("setwise coprime")
    else:
        print('not coprime')
    exit()

C = Counter(A)
for k, v in C.items():
    if v > 1:
        gcd_set = reduce(gcd, A)
        if gcd_set == 1:
            print("setwise coprime")
        else:
            print('not coprime')
        exit()
print('pairwise coprime')

Submission status: Wrong Answer

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

pc = True
gg = A[0]
so = defaultdict(int)

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

for a in factorization(A[0]):
    so[a] = 1

for i in range(1, N):
    for a in factorization(A[i]):
        if so[a] == 1:
            pc = False
            break
        so[a] = 1
    gg = gcd(A[i], gg)

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

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 (1 in a and a.count(1) == len(a)) or 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, math
from functools import lru_cache
import numpy as np
sys.setrecursionlimit(10**9)
MOD = 10**9+7

def input():
    return sys.stdin.readline()[:-1]

def mi():
    return map(int, input().split())

def ii():
    return int(input())

def i2(n):
    tmp = [list(mi()) for i in range(n)]
    return [list(i) for i in zip(*tmp)]


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


def main():
    N = ii()
    A = np.array(list(mi()))

    l = np.lcm.reduce(A)
    g = np.gcd.reduce(A)
    p = np.prod(A)

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

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

dp = [0] * (10**6 + 1)

for a in A:
    for i in range(2, int(math.sqrt(a)) + 1):
        if a % i == 0:
            dp[i] += 1
            if i != a // i:
                dp[a // i] += 1

    dp[a] += 1
            
ans = 0

for i in range(2, max(A) + 1):
    ans = max(ans, dp[i])

if ans == 1:
    print("pairwise coprime")

elif ans < N:
    print("setwise coprime")
    
else:
    print("not coprime")

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    A = list(map(int, input().split()))
    pairwise = True
    onef = set()
    allf = set()
    a = A[0]
    i = 2
    while i * i <= a:
        if a % i == 0:
            while a % i == 0:
                a //= i
            allf.add(i)
            onef.add(i)
        i += 1
    
    for a in A[1:]:
        thisf = set()
        i = 2
        while i * i <= a:
            if a % i == 0:
                while a % i == 0:
                    a //= i
                if i in onef:
                    pairwise = False
                else:
                    onef.add(i)
                thisf.add(i)
            i += 1
        allf &= thisf
    if pairwise:
        return 'pairwise coprime'
    if len(allf) == 0:
        return 'setwise coprime'
    return 'not coprime'

print(main())

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 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
N = int(input())
a = list(map(int, input().split()))
ans = a[0]
flag = True
for i in range(1, N):
    ans = gcd(ans, a[i])
    if flag and ans != 1:  
      flag = False
      
if flag:
  print("pairwise coprime")
elif flag == False and ans == 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
for i in range(N):
    if A[i] not in pd:
        primes = prime_decomposition(A[i])
        for p in primes:
            if p not in d:
                d[p] = 0
            else:
                ans = 1

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:
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
	M1 = len(B)
	B = list(set(B))
	M2 = len(B)
	
	if M1 != M2:
		print("setwise coprime")
		return

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