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:
# coding: utf-8
from math import gcd
import math
# 素数判定関数
def isPrime(num):
    # 2未満の数字は素数ではない
    if num < 2: return False
    # 2は素数
    elif num == 2: return True
    # 偶数は素数ではない
    elif num % 2 == 0: return False

    # 3 ~ numまでループし、途中で割り切れる数があるか検索
    # 途中で割り切れる場合は素数ではない
    for i in range(3, math.floor(math.sqrt(num))+1, 2):
        if num % i == 0:
            return False

    # 素数
    return True

# 素数判定
def callIsPrime(input_num=1000):
    numbers = []
    # ループしながら素数を検索する
    for i in range(1, input_num):
        if isPrime(i):
            numbers.append(i)

    # 素数配列を返す
    return numbers

# 関数の呼び出し
prime_list = callIsPrime(10**3+100)

N=int(input())
A=list(map(int,input().split()))
prime_flg = [True for i in range(10**3+100)]
pc_flg=True

cnt_one=0
for i in range(N):
    if A[i]==1:
        cnt_one+=1

if len(A)!=len(set(A)):
    pc_flg=False

if cnt_one!=0:
    if len(A)==len(set(A))+cnt_one-1:
        pc_flg=True



x = A[0]

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

A = list(set(A))

if pc_flg:
    for i in range(len(A)):
        for j in range(len(prime_list)):
            p=prime_list[j]
            if A[i]%p == 0:
                if prime_flg[p]:
                    prime_flg[p]=False
                else:
                    pc_flg=False
            if not(pc_flg):
                break
        if not(pc_flg):
            break


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

Submission status: Wrong Answer

Solution code:
MOD = 10**9+7
lim = 200000
inv_t = [-1 for i in range(lim+1)]
factrial = [-1 for i in range(lim+1)]
factrial_inv = [-1 for i in range(lim+1)]


def mod_inv(x, mod=MOD):
    y, u, v, _x = mod, 1, 0, x
    while y:
        t = _x//y
        _x -= t*y
        _x, y = y, _x
        u -= t*v
        u, v = v, u
    u %= mod
    if u < 0:
        u += mod
    return u


def mod_pow(a, n, mod=MOD):
    res = 1
    while n:
        if n & 1:
            res = res*a % mod
        a = a*a % mod
        n >>= 1
    return res


def COMinit(max=lim, mod=MOD):
    factrial[0] = factrial_inv[0] = 1
    factrial[1] = factrial_inv[1] = 1
    inv_t[0] = inv_t[1] = 1
    for i in range(2, max):
        factrial[i] = factrial[i-1]*i % mod
        inv_t[i] = -inv_t[mod % i]*(mod//i) % mod
        factrial_inv[i] = factrial_inv[i-1]*inv_t[i] % mod


def comb(a, b, mod=MOD):
    if a < b:
        return 0
    if factrial[0] == -1:
        COMinit()
    return (factrial[a]*factrial_inv[b]*factrial_inv[a-b]) % mod


def prime_factor(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 = [int(_) for _ in input().split()]
p = [2]

for i in range(3, 10**3+100):
    for P in p:
        if i % P == 0:
            break
    else:
        p.append(i)

dic = {}
for P in p:
    dic[P] = 0

for i in range(n):
    if a[i] == 1:
        print("pairwise coprime")
        exit(0)
    temp = a[i]
    for P in p:
        if temp % P == 0:
            dic[P] += 1
            # while temp % P == 0:
            #     temp //= P
        if temp == 1:
            break
    if temp != 1:
        if temp in dic.keys():
            dic[temp] += 1
        else:
            dic[temp] = 1

# print(ans[0:10])

ans = dic.values()
print(ans)
# print(p, len(p))
# print(dic)
if max(ans) == n:
    print("not coprime")
elif max(ans) == 1:
    print("pairwise coprime")
else:
    print("setwise 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
while p*p<=N:
    if primes[p]:
        for mul in range(p,N,p):
            primes[mul]=0
            if mul in s:
                d[p]=d.get(p,0)+1
                if d[p]>=2:not_pairwise=1;break;
        if not_pairwise:break
    p+=1
g=a[0]
for v in a:
    g=gcd(g,v)
if not_pairwise==0 and g==1:print('pairwise coprime')
elif g==1:print('setwise coprime')
else:print('not coprime')

Submission status: Wrong Answer

Solution code:
MAXN = 1000001
spf = [i for i in range(MAXN)] 
hash1 = [0 for i in range(MAXN)] 
def sieve(): 
    for i in range(4, MAXN, 2): 
        spf[i] = 2

    for i in range(3, MAXN): 

        if i * i < MAXN: 
            break
        if (spf[i] == i): 
            for j in range(i * i, MAXN, i): 
                if (spf[j] == j): 
                    spf[j] = i  
def getFactorization(x): 
    while (x != 1): 
        temp = spf[x] 
        if (x % temp == 0): 
            hash1[spf[x]] += 1
            x = x // spf[x] 
        while (x % temp == 0): 
            x = x // temp 
def check(x): 

    while (x != 1): 
        temp = spf[x] 
        if (x % temp == 0 and hash1[temp] > 1): 
            return False
        while (x % temp == 0): 
            x = x //temp 
	
    return True

def hasValidNum(arr, n): 
    sieve() 

    for i in range(n): 
        getFactorization(arr[i]) 
    f=0;
    for i in range(n): 
        if (check(arr[i])==False):
            #print(arr[i])
            f=1
    if(f==1):
        return False
    return True;

n=int(input())
arr=list(map(int,input().split()))
if (hasValidNum(arr, n)): 
    print("pairwise coprime")
else:
    f=0
    for i in hash1:
        if i==n:
            print("not coprime")
            f=1
            break
    if f==0:
        print("setwise coprime")

Submission status: Wrong Answer

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7


def main():
    N = int(readline())
    A = list(map(int, readline().split()))
    setwise = True
    pairwise = True
    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]
    for p in primes:
        tmp = 0
        for a in A:
            if a % p == 0:
                tmp += 1
        if tmp <= 1:
            continue
        else:
            setwise = False
            if tmp == N:
                pairwise = False
    if pairwise:
        print('pairwise coprime')
    else:
        if setwise:
            print('setwise coprime')
        else:
            print('not coprime')


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import math
import sys
from collections import defaultdict

N_MAX = 200000 + 5
INF = 10**9 + 7
sys.setrecursionlimit(N_MAX)
MOD = 10**9 + 7


def factorization(n):

    arr = defaultdict(int)
    tmp = n
    for i in range(2, int(-(-n**0.5 // 1)) + 1):  # sqrt(n) まで

        # i で割れるだけ割る、を繰り返す
        if tmp % i == 0:
            cnt = 0

            while tmp % i == 0:
                cnt += 1
                tmp //= i

            arr[i] = cnt  # 結果を追加

    if tmp != 1:
        arr[tmp] = 1  # まだ余っていれば追加しておく

    if arr == {}:
        arr[n] = 1  # このブロック、必要か？

    return arr


N = int(sys.stdin.readline().rstrip())
A = [int(x) for x in sys.stdin.readline().rstrip().split()]


pc = True
sp = True

maxlist = factorization(A[0])
minlist = factorization(A[0])

for i in range(1, N):
    d = factorization(A[i])
    for p in d.keys():

        if min(maxlist[p], d[p]) != 0:
            pc = False
        maxlist[p] = max(maxlist[p], d[p])

    for p in minlist.keys():
        minlist[p] = min(minlist[p], d[p])


for p in minlist.keys():
    if minlist[p] != 0:
        sp = False

# print(maxlist)
# print(minlist)

if pc:
    print("pairwise coprime")
elif sp:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import collections as cl
import sys


def II():
    return int(sys.stdin.readline())


def MI():
    return map(int, sys.stdin.readline().split())


def LI():
    return list(map(int, sys.stdin.readline().split()))


def main():
    N = II()
    targets = LI()
    MAX_INT = max(targets) + 1
    counter = cl.Counter(targets)
    targets = set(targets)
    is_pw = True

    num_1 = counter[1]
    N -= num_1

    if len(targets) != N:
        is_pw = False

    if len(targets) == 1:
        if 1 in targets:
            print("setwise coprime")
            return
        print("not coprime")
        return

    for i in range(2, MAX_INT):
        origin = i
        kosuu = 0
        while origin <= MAX_INT:
            if origin in targets:
                kosuu += 1
            origin += i

        if kosuu <= 1:
            continue
        elif kosuu < len(targets):
            is_pw = False
        else:
            print("not coprime")
            return

    if is_pw:
        print("pairwise coprime")
        return
    print("setwise coprime")


main()

Submission status: Wrong Answer

Solution code:
import math
from functools import reduce
n=int(input())
a=list(map(int, input().split()))
q=0
size=10**6

judge=[0]*(size)

for i in range(len(a)):
    num=a[i]
    for j in range(2,int(num**0.5)+1):
        if num%j==0:
            if judge[j-1]==-1:
                q=1
            elif judge[num//j-1]==-1:
                q=1
            else:
                judge[j-1]=-1
                judge[num//j-1]=-1

    if judge[num-1]==-1:
        q=1
    else:
        judge[num-1]=-1

m=min(a)
for i in range(2,int(m**0.5)+1):
    if m%i==0:
        m=i
        break

if q>0:
    for i in range(n):
        if a[i]%m!=0:
            q=2

if q==0:
    print('pairwise coprime')

elif q==2:
    print('setwise coprime')
        
else:
    print('not coprime')

Submission status: Wrong Answer

Solution code:
import math
from functools import reduce

def gcd_list(numbers):
  return reduce(math.gcd, numbers)
  
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(" ")))
check = [False for i in range(10 ** 6 + 1)]
pairwise = True
for i in a:
  temp = (factorization(i))
  for j, _ in temp:
    if check[j] == True:
      pairwise = False
      break
    else:
      check[j] = True
  else:
    continue
  break
if pairwise:
  print("pairwise coprime")
else:
  if gcd_list(a) == 1:
    print("setwise coprime")
  else:
    print("not coprime")

Submission status: Wrong Answer

Solution code:
import math

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

ans = a[0]
A = []

for x in a[1:]:
    ans = math.gcd(ans,x)
    A.append(ans)
#print(ans)
#print(A)
if A.count(1) != len(A) and ans == 1:
    print('setwise coprime')
if A.count(1) == len(A):
    print('pairwise coprime')
else:
    print('not coprime')

Submission status: Wrong Answer

Solution code:
import sys

def cf(x1,x2):
    cf=[]
    for i in range(2,min(x1,x2)+1):
        if x1 % i == 0 and x2 % i == 0:
            cf.append(i)
    return cf

N = int(input())
A = list(map(int,input().split()))
A.sort()
X = cf(A[0],A[1])

for i in X:
    a = 0
    b = 0
    for j in range(N):
        if A[i] % i == 0:
            a += 1
        else:
            b += 1
    if a == N:
        print("not coprime")
        sys.exit()
    if a != 0 and b != 0:
        print("setwise coprime")
        sys.exit()
print("pairwise coprime" if len(X) == 0 else "setwise coprime")

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
mod=10**9+7
import sys
import math
def setwise_coprime(a):
  ans=a[0]
  for i in range(1,n):
    ans=math.gcd(ans,a[i])
  return ans

ruiseki=1
for i in range(n):
  ruiseki=ruiseki*a[i]%mod

for i in range(n):
    num=math.gcd(a[i],(ruiseki+mod)//a[i])
    if num!=1:
      if setwise_coprime(a)==1:
        print("setwise coprime")
        sys.exit()
      else:
        print("not coprime")
        sys.exit()
print("pairwise coprime")

Submission status: Wrong Answer

Solution code:
import sys
import bisect
from functools import lru_cache
from collections import defaultdict
inf = float('inf')
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10**6)
def input(): return sys.stdin.readline().rstrip()
def read():
  return int(readline())
def reads():
  return map(int, readline().split())
class UnionFind():
    def __init__(self, n):
        self.n=n
        self.parents=[-1]*n # 親(uf.find()で経路圧縮して根)の番号。根の場合は-(そのグループの要素数)
    def find(self,x):
        #グループの根を返す
        if self.parents[x]<0:return x
        else:
            self.parents[x]=self.find(self.parents[x])
            return self.parents[x]
    #def members(self, x):
    #    root = self.find(x)
    #    return [i for i in range(self.n) if self.find(i) == root]
    def unite(self,x,y):
        #要素x,yのグループを併合
        x,y=self.find(x),self.find(y)
        if x==y:return
        if self.parents[x]>self.parents[y]:#要素数の大きい方をxに
            x,y=y,x
        self.parents[x]+=self.parents[y]
        self.parents[y]=x #要素数が大きい方に併合
    def roots(self):
        #全ての根の要素のリスト
        return [i for i, x in enumerate(self.parents) if x<0]
    def group_count(self):
        #グループの数
        return len(self.roots())
    def members(self, x):
        root = self.find(x)
        return len([i for i in range(self.n) if self.find(i) == root])
    #def __str__(self):
    #   return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

N=read()
A=list(reads())
import math
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 = []
    limit = math.sqrt(n)
    data = [i + 1 for i in range(1, n)]
    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(10**3)
def factorization(n):
    arr = []
    temp = n
    for i in data:
        if i>math.sqrt(n):
            break
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append(i)

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

    if arr==[]:
        arr.append(n)

    return arr
dic=defaultdict(int)
res=["" for i in range(N)]
for i in range(N-1,-1,-1):
  ls=factorization(A[i])
  for lval in ls:
      dic[lval]+=1
  if i!=N-1:
      for j in range(len(ls)):
          if dic[ls[j]]!=1: 
              break
          if j==len(ls)-1:
              res="pairwise coprime"
              print(res)
              exit()
for val in dic.values():
    if val==N:
        res="not coprime"
        print(res)
        exit()
print("setwise coprime")

Submission status: Wrong Answer

Solution code:
from math import gcd
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(1000)
c = [0]*1001
# print(len(p))

n = int(input())
a = list(map(int,input().split()))
a = [1] * (1 in a) + [i for i in a if i != 1]
# print(a)
n = len(a)

if n>80000:
    print("not coprime")
    exit()
g = 0
f = 1
c1 = 0
for i in a:
    g = gcd(g,i)
    if f == 1:
        for j in p:
            if i%j == 0:
                c[j] += 1
                if c[j] > 1:
                    f = 0
if g == 1:
    if f == 1:
        print("pairwise coprime")
    else:
        print("setwise coprime")
else:
    print("not coprime")
# print(a,g,f)

Submission status: Wrong Answer

Solution code:
import math

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

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

if ans!=1:
    print('not coprime')

else:
    for l in range(1,n):
        if a[l]==a[l-1]:
            print('setwise coprime')
            exit()
    for i in range(min(1000,n-1)):
        for k in range(min(i+1,n-1),min(n,1000)):
            if math.gcd(a[i],a[k])!=1:
                print('setwise coprime')
                exit()
    print('pairwise coprime')

Submission status: Wrong Answer

Solution code:
import functools
import math
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i:
        divisors.append(n//i)

  divisors.sort()
  divisors.pop(0)
  return divisors

def is_prime(n):
  for i in range(2, n + 1):
    if i * i > n:
      break
    if n % i == 0:
      return False
  return n != 1

N = input()
A = list(map(int, input().split()))
A = sorted(A)
gcd = functools.reduce(math.gcd, A)

dp = []
if 2 <= gcd:
  print("not coprime")
else:
  isPC = True
  for i, a in enumerate(A):
    if is_prime(a):
      dp.append(a)
    else:
      divs = make_divisors(a)
      for d in divs:
        if d in dp:
          isPC = False
        dp.append(d)
        break

    if not isPC:
      break
  if isPC:
    print("pairwise coprime")
  else:
    print("setwise coprime")

Submission status: Wrong Answer

Solution code:
def factorization(n):
    if n==1:
        return {1}
    temp=n
    ans=[]
    SS=[i for i in S if i*2<n]
    for i in SS:
        if temp % i ==0:
            ct=0
            while temp % i == 0:
                temp //= i
                ct += 1
            ans.append([i, ct])
    if temp != 1:
        ans.append([temp, 1])
    return {ans[i][0] for i in range(len(ans))}

S = set()
L = [True]*(10**6+1)
L[0] = False
L[1] = False
for i in range(2, 10**6+1):
    if L[i]:
        S.add(i)
        for j in range(i*2, 10**6+1, i):
            L[j] = False

def egcd(a, b):
    if a == 0:
        return b
    else:
        g= egcd(b % a, a)
        return g

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

ct=0
s=set()
for i in range(N):
    tmp=factorization(A[i])
    ct+=len(tmp)
    s|=tmp
    if ct!=len(s):
        break
else:
    print('pairwise coprime')
    exit()


L1=A
while len(L1)>1:
    l=len(L1)//2
    tmp=[0]*l
    for i in range(l):
        tmp[i]=egcd(L1[2*i],L1[2*i+1])
    if len(L1)%2==1:
        tmp.append(L1[-1])
    L1=tmp

if L1[0]==1:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Wrong Answer

Solution code:
import itertools
from functools import reduce
import math

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

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


pair = list(itertools.combinations(A, 2))

for i in range(len(pair)):
    print(pair[i])
    if(math.gcd(pair[i][0], pair[i][1]) != 1):
        if(gcd_list(A) == 1):
            print("setwise coprime")
            break
        else:
            print("not coprime")
            break
    else:
        print("pairwise coprime")
        break

Submission status: Wrong Answer

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

r = [0] * (n+1)

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

flg = False
for i in range(n-1):
  if r[i+2] > 1:
    flg = True

if r[-1] == 1:
  if flg == False:
    print ('pairwise coprime')
  else:
    print ('setwise coprime')
else:
  print ('not coprime')

Submission status: Wrong Answer

Solution code:
import functools
import math

n=int(input())
values=list(map(int,input().split()))
setgcd = functools.reduce(math.gcd, values)
values.sort()

flag=True

sqrtn=int(values[-1]**0.5)
prime = {i for i in range(2,sqrtn+1)}
for i in range(2,sqrtn+1):
    if i in prime:
        for j in range(i*2,sqrtn+1,i):
            if j in prime:
                prime.remove(j)

flag=True
for i in prime:
  cnt=0
  if flag==False:
    break
  for j in values:
    if j%i==0:
      cnt+=1
      if cnt==2:
        flag=False
        break

if flag:
  print("pairwise coprime")
elif setgcd==1:
  print("setwise coprime")
else:
  print("not coprime")

Submission status: Wrong Answer

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

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

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

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

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

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

Submission status: Wrong Answer

Solution code:
from math import gcd

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

pair = True
for j in range(1, n):
    for i in range(j):
        if gcd(A[i], A[j]) != 1:
            pair = False
            break
    if pair == False:
        break
if pair:
    print('pairwize coprime')
    exit()

a = 1
for i in range(n):
    a = gcd(a, A[i])
    if a != 1:
        print('not coprime')
        exit()
print('setwise coprime')

Submission status: Wrong Answer

Solution code:
def isPrime(x :int):
    if(x == 1):
        return False
    if (x== 2):
        return True
    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)
    else:
        flag = False
        break
a = reduce(gcd,L)
#print(a,flag)

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

Submission status: Wrong Answer

Solution code:
mod=10**9+7
import math
N=int(input())
A=list(map(int,input().split()))
ans=['pairwise coprime','setwise coprime','not coprime']
k=0
s,g=A[-1],A[-1]
for i in range(2,N+1):
    g=math.gcd(g,A[-i])
    if math.gcd(s,A[-i])!=1:
        k=-1
    s*=A[-i]
    s%=mod
if k==-1:
    if g==1:
        k=1
    else:
        k=2
print(ans[k])

Submission status: Wrong Answer

Solution code:
from functools import reduce
import math
def gcd(x,y):
    if x%y==0:
        return y
    else:
        return (gcd(y, x%y))

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)

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

    if arr==[]:
        arr.append(n)

    return arr

def ans(n, a):
    div = {}
    for i in range(n):
        k = (factorization(a[i]))
        for j in k:
            if j not in div:
                div[j]=1
            else:
                return True
    return False
    

n = int(input())
a = list(map(int, input().split()))
gcd = reduce(math.gcd, a)
if gcd !=1:
    print("not coprime")
else:
    if ans(n, a):
        print("setwise coprime")
    else:
        print("pairwise coprime")

Submission status: Wrong Answer

Solution code:
p=[1 for i in range(1001)]
p[0]=0
p[1]=0
for i in range(2,1001):
    if p[i]==1:
        for j in range(2,1001):
            if i*j<=1000:
                p[i*j]=0
#print(p[:25])
Prime=[]
for i in range(1001):
    if p[i]==1:
        Prime.append(i)
#print(Prime)
#print(len(Prime))
N=int(input())
L=list(map(int,input().split()))

def gcd(a,b):
    if b>a:
        a,b=b,a
    while a%b!=0:
        a,b=b,a%b
    return b
    
X=L[0]
for i in range(1,N):
    X=gcd(X,L[i])
    if X==1:
        break
if X>1:
    print("not coprime")
    exit()
        
D={}
if N>(10**5)*7:
    print("setwise coprime")
    exit()
for i in L:
    I=i
    for j in Prime:
        if I%j==0:
            if j not in D:
                D[j]=1
            else:
                print("setwise coprime")
                exit()
            while I%j==0:
                I//=j
    if I!=1:
        if I not in D:
            D[I]=1
        else:
            print("setwise coprime")
            exit()
#print(D)

print("pairwise coprime")

Submission status: Wrong Answer

Solution code:
from math import gcd

N = int(input())
A = list(map(int, input().split()))
MOD = 10 ** 9 + 7

g = A[0]
for i in range(1, N):
	g = gcd(g, A[i])
	
if g != 1:
	print("not coprime")
else:
	g = A[0]
	l = A[0]
	prod = A[0]
	for i in range(1, N):
		g = gcd(g, A[i])
		l = ((l * A[i]) // g) % MOD
		prod = (prod * A[i]) % MOD
		if l != prod:
			print("setwise coprime")
			exit()
	print("pairwise coprime")

Submission status: Wrong Answer

Solution code:
n = int(input())
*A, = map(int, input().split())

m = 10**6
is_prime = [True] * (m + 1)
is_prime[0] = False
is_prime[1] = False
for i in range(2, m + 1):
    for j in range(i * 2, m + 1, i):
        is_prime[j] = False
primes = [i for i in range(m + 1) if is_prime[i]]

# Amap[a]=1ならAはaをもつ
Amap = {a: 0 for a in range(1, m + 1)}
for a in A:
    Amap[a] = max(Amap[a], 1)

# Pmap[p]はAにでてくるpの倍数の数
Pmap = {p: 0 for p in primes}
for p in Pmap:
    for a in range(p, m + 1, p):
        if Amap[a] == 1:
            Pmap[p] += 1

score = max(Pmap.values())
if score == 1:
    print('pairwise coprime')
elif score != n:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Wrong Answer

Solution code:
from math import gcd
N = int(input())
A = list(map(int, input().split()))
max_A = max(A)
happend_numbers = [False]*(max_A+1)  # 0~NのN+1個
for a in A:
    happend_numbers[a] = True

for i in range(2, max_A+1):
    true_count = 0
    for j in range(i, max_A+1, i):
        if happend_numbers[j]:
            true_count += 1
    if true_count >= 2:
        break
else:
    print("pairwise coprime")
    exit()

now = A[0]
for a in A[1:]:
    now = gcd(a, now)
if now == 1:
    print("setwise coprime")
    exit()
print("not coprime")

Submission status: Wrong Answer

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

def sieve(num):
    input_list = [False if i % 2 == 0 or i % 3 == 0 or i % 5 == 0 else True for i in range(num)]
    input_list[0] = input_list[1] = False
    input_list[2] = input_list[3] = input_list[5] = True
    sqrt = math.sqrt(num)
    for serial in range(3, num, 2):
        if serial >= sqrt:
            return input_list
        for s in range(serial ** 2, num, serial): 
            input_list[s] = False
            
def fact(num):
    arr = []
    temp = num
    for i in range(2, int(-(-num**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(num)
    return arr

flg=True
prim=sieve(mxa+5)
table=[0]*(mxa+1)
for i in a:
  fc=fact(i)
  for j in fc:
    if table[j]==1:
      flg=False
    table[j]+=1

if flg:
  print("pairwise coprime")
elif n in table:
  print("not coprime")
else:
  print("setwise coprime")

Submission status: Wrong Answer

Solution code:
import math

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

t = A[0]
check = A[0]
for i in range(1, n):
    s = math.gcd(check, A[i])
    t = math.gcd(t, A[i])
    check *= (A[i] // t)
    if t != 1:
        break


if t == 1 and s == 1:
    print('pairwise coprime')
elif t == 1:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Wrong Answer

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


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


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

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

    # if arr==[]:  # n=1のとき、[1,1]を返す
    #     arr.append([n, 1])

    return arr


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

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

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

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

print("pairwise coprime")