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 math

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

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


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:
import sys
import math
import random
from collections import defaultdict
input = sys.stdin.readline
def is_prime(q,k=50):
    q = abs(q)
    if q == 2: return True
    if q < 2 or q&1 == 0: return False
    d = (q-1)>>1
    while d&1 == 0:
        d >>= 1

    for i in range(k):
        a = random.randint(1,q-1)
        t = d
        y = pow(a,t,q)
        while t != q-1 and y != 1 and y != q-1: 
            y = pow(y,2,q)
            t <<= 1
        if y != q-1 and t&1 == 0:
            return False
    return True

def fact(n):
    ret = set()
    for i in range(2, math.floor(math.sqrt(n))+1):
        if n % i == 0:
            ret.add(i)
            while n % i == 0:
                n //= i
    if n != 1:
        ret.add(n)
    return ret
def pairwise(A):
    primes = set()
    for a in A:
        if is_prime(a):
            primes.add(a)
        else:
            ret = fact(a)
            if ret.intersection(primes):
                return False
            else:
                primes |= ret
    return True
def setwise(A):
    g = A[0]
    for i in range(1,len(A)):
        g = math.gcd(g, A[i])
        if g == 1:
            return True
    return False
    
if __name__ == "__main__":
    N = int(input())
    A = list(map(int,input().split()))
    if pairwise(A):
        print("pairwise coprime")
    elif setwise(A):
        print("setwise coprime")
    else:
        print("not coprime")

Submission status: Wrong Answer

Solution code:
import math
N = int(input())
A = [int(x) for x in input().split()]
P = [2]
M = math.ceil(max(A))
for L in range(3, M, 2): 
    if all(L % L2 != 0 for L2 in P):  
        P.append(L)
lst = [0] * len(P)
for i, p in enumerate(P):
    cnt = 0
    for a in A:
        cnt += a % p == 0
    lst[i] = cnt
tmp = max(lst)
if tmp == 1:
    print('pairwise coprime')
elif tmp == N:
    print('not coprime')
else:
    print('setwise 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]*1000
flag = 0
for a in A:
    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
    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:
N = int(input())
A = list(map(int, input().split()))

import itertools
import fractions
#
# ans_list = 1
not_pair = False
not_set = False

# for combi in itertools.combinations(A, 2):
#     ans = fractions.gcd(combi[0], combi[1])
#     if ans != 1:
#         not_pair = True
#         if ans_list == 1:
#             ans_list = ans
#         else:
#             ans_list = fractions.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")

ans = A[0]
for i in range(1, N):
    ans = fractions.gcd(ans, A[i])
    if ans != 1:
        not_pair = True
if ans != 1:
    not_set = True

if not not_pair:
    print("pairwise coprime")
elif not not_set:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Wrong Answer

Solution code:
N = int(input())

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

max_a = max(A)

set_a = set(A)

setFlag = False

if len(set_a) != len(A):
    setFlag = True

for i in range(2,int(max_a**0.5)+2):
    tmp_count = 0
    pairFlag = True
    for key,a in enumerate(set_a):
        if a%i == 0:
            tmp_count += 1
            if 1 < tmp_count and tmp_count != key+1:
                setFlag = True
                break
        else:
            pairFlag = False
    if pairFlag:
        print('not coprime')
        exit()

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

Submission status: Wrong Answer

Solution code:
from functools import reduce
from fractions import gcd
import sys

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

lcm = 1
flg = True
pia = 1
for a in A:
    pia = (pia * a) % P
    """
    if gcd(lcm, a) != 1:
        flg = False
        break
    lcm = (lcm*a)%P
    """
if flg:
    print('pairwise coprime')
    sys.exit()

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

Submission status: Wrong Answer

Solution code:
import math
import functools

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

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

for a in A:
    if a == 1:
        continue
    if pairwise is False:
        break
    for k in range(2, int(math.sqrt(a)) + 2):
        if a % k == 0:
            if k in p:
                pairwise = False
                break
            p.add(k)
            while a % k == 0:
                a //= k
    if pairwise and a > 1:
        p.add(a)

if pairwise:
    print("pairwise coprime")
elif y == 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()))
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 i in range(min(10000,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()
        for j in range(min(max(n//2,i+1),n-1),min(n//2+1000,n)):
            if math.gcd(a[i],a[j])!=1:
                print('setwise coprime')
                exit()
    print('pairwise coprime')

Submission status: Wrong Answer

Solution code:
from math import gcd
least_prime = [0]*(10000009)
def leastPrimeFactor() : 
    n = 1000009
    least_prime[1] = 1
    for i in range(2, n + 1) : 
        if (least_prime[i] == 0) : 
            least_prime[i] = i 
            for j in range(2 * i, n + 1, i) : 
                if (least_prime[j] == 0) : 
                    least_prime[j] = i 
leastPrimeFactor()
n = input()
s = input().split(" ")
uniq = set()

for c in s:
    uniq.add(least_prime[int(c)])
if len(uniq) == len(s):
    print("pairwise coprime")
else:
    ans = 0
    for c in uniq:
        ans  = gcd(ans, c)
    if ans ==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()))
MOD = 10**9+7
A.reverse()
val = A[0]
flg = True
for i in range(1,N):
    if gcd(val,A[i]) != 1:
        flg = False
    val *= A[i]
    val %= MOD
if flg == True:
    print('pairwise coprime')
    exit()





val = A[0]
for i in range(1,N):
    val = gcd(val,A[i])
if val == 1:
    print('setwise coprime')
    exit()
print('not coprime')

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
s = set()
for i in a:
    ns = set()
    for j in range(2, 10**3):
        if i%j!=0:
            continue
        while i%j==0:
            i//=j
        ns.add(j)
        if i==1:
            break
    else:
        ns.add(j)
    if len(ns&s)>0:
        break
    s = ns
else:
    print('pairwise coprime')
    exit(0)
def gcd_base(a, b):
    while b!=0:
        a, b = b, a%b
    return a

def gcd(num_list):
    ans = 0
    for i in num_list:
        ans = gcd_base(ans, i)
    return ans

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

Submission status: Wrong Answer

Solution code:
import math
def yakusu(n):
    results = []
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            results.append(i)
            if i != (n // i):
                results.append(n // i)
    results += [n]
    return results
def eratos(A):
    max_Ai = 10**6
    isprime = [0 for i in range(max_Ai+1)]
    ans = []
    for ai in set(A):
        if ai == 1:
            ans += [1]
        elif isprime[ai] == 0:
            y = yakusu(ai)
            ans += [y[0]]
            for i in y:
                if isprime[i] == 0:
                    j = i
                    while j <= max_Ai:
                        if isprime[j] == 0:
                            isprime[j] = i
                        j = j + i
        else:
            ans += [isprime[ai]]

    return isprime, ans
N = int(input())
A = list(map(int, input().split()))
isprime, ans = eratos(A)
set_ans = set(ans)
if len(set_ans) == N:
    print('pairwise coprime')
elif len(set_ans) == 1:
    print('not coprime')
else:
    print('setwise 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
    targets = set(targets)
    is_pw = True
    if N == 2:
        print(targets[10])

    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 < N:
            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:
from collections import Counter 

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

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


cnt = [0] * (10 ** 6)
for i in A:
    a = prime_factorize(i)
    alist = list(Counter(a).keys())
    for j in alist:
        cnt[j] += 1

ans = max(cnt)
if ans == 1:
    print("pairwise coprime")
elif ans == len(A):
    print("not coprime")
else:
    print("setwise coprime")

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
l=[0]*(10**6+100)
for m in a:
  l[m]=1
x=0
j=2
#print(l)
for i in range(n):
  c=0
  k=1
  while j*k<=10**6+1 :
    if l[j*k]==1:
      c+=1
      l[j*k]=0
    k+=1
  if c==n:
    print("not coprime")
    exit()
  elif c>1:
    x=1
  j+=1 
if x==1:
  print("setwise coprime")
else:
  print("pairwise coprime")

Submission status: Wrong Answer

Solution code:
import math
from functools import reduce

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

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

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

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

    return arr

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

s = set()
for i in a:
    for j in factorization(i):
        if j not in s:
            s.add(j)
        else:
            if gcd_list(a) == 1:
                print('setwise coprime')
                exit()
            else:
                print('not coprime')
                exit()
print('pairwise coprime')

Submission status: Wrong Answer

Solution code:
#ここまでテンプレ
from sys import stdin
from sys import setrecursionlimit
setrecursionlimit(10 ** 7)

n = int(stdin.readline().rstrip())
a = list(map(int,stdin.readline().rstrip().split()))

import fractions

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

ans = a[0]

se = set()
flag = False

if a[0] != 1:
    lin = make_divisors(a[0])[1:]
    for j in lin:
        se.add(j)

for i in range(1, n):
    ans = fractions.gcd(ans, a[i])
    if a[i] != 1 and flag == False:
        lin = make_divisors(a[0])[1:]
        for j in lin:
            if j in se:
                flag = True
                break
            else:
                se.add(j)
    
if ans == 1 and flag == False:
    print("setwise coprime")
elif ans == 1:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Wrong Answer

Solution code:
from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce, lru_cache
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def MAP1()  : return map(lambda x:int(x)-1,input().split())
def LIST()  : return list(MAP())
def LIST1() : return list(MAP1())

n = INT()
a = LIST()

k = 1
flag = 1
mod = pow(10,9)+7
for i in range(1, n):
    k *= a[i-1]
    k %= mod
    if gcd(k, a[i]) > 1:
        flag = 0

if flag == 1:
    print("pairwise coprime")
    exit()

else:
    g = a[0]
    for i in range(1, n):
        g = gcd(g, a[i])
    if g == 1:
        print("setwise coprime")
    else:
        print("not coprime")

Submission status: Wrong Answer

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

counter = Counter(A)

is_pairwise = True
for key, count in counter.items():
    if key > 1 and count > 1:
        is_pairwise = False

A = list(counter.keys())

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)))
used = set()

def factorize(n):
    N = n
    for prime in primes:
        if n == 1:
            break
        is_used = False
        while n % prime == 0:
            if prime in used:
                return False
            n //= prime
            is_used = True
        if is_used:
            used.add(prime)
    return True

all_gcd = A[0]
for a in A:
    all_gcd = math.gcd(all_gcd, a)
    if is_pairwise:
        if not factorize(a):
            is_pairwise = False

if is_pairwise:
    print('pairwise coprime')
elif all_gcd == 1:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Wrong Answer

Solution code:
def gcd(a,b):
  if b==0:
    return a
  else:
    return gcd(b,a%b)
n=int(input())
l=list(map(int,input().split())) 
c=0
for i in range(0,n):
  t=l[i%n]
  y=l[(i+1)%n]
  s=min(t,y)
  p=max(t,y)
  f=gcd(p,s)
  if f==1:
      c=c+1
if c==3:
    print('pairwise  coprime')
else:
    f=l[0]
    y=l[1]
    a=max(f,y)
    b=min(f,y)
    r=gcd(a,b)
    for w in range(2,len(l)):
        r=gcd(r,l[i])
    if r==1:
        print('setwise  coprime')
    else:
        print('not coprime')

Submission status: Wrong Answer

Solution code:
from functools import reduce
from fractions import gcd
import sys

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

lcm = 1
flg = True
pia = 1
for a in A:
    pia = pia * a
    """
    if gcd(lcm, a) != 1:
        flg = False
        break
    lcm = (lcm*a)%P
    """
if flg:
    print('pairwise coprime')
    sys.exit()

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

Submission status: Wrong Answer

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

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

A.sort()
M = A[-1]
d = {}
ans = 0
if len(set(A)) != N:
    ans = 1
for i in range(N):
    if A[i] not in d:
        primes = prime_decomposition(A[i])
        for p in primes:
            for j in range(M//p+1):
                d[j*p] = 0
        d[A[i]] = 1
    else:
        ans = 1
        break
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:
N = int(input())
A = list(map(int, input().split()))

h = 0

for i in range(len(A)):
  if A[i] % 2 != 0:
    h = 1

if h == 0:
  print("not coprime")
  
elif A[0] % 2 == 0:
  print("setwise coprime")
  
else:
  print("pairwise coprime")

Submission status: Wrong Answer

Solution code:
def prime(n):
    nums = [True]*n
    primes = []
    for i in range(2,n):
        if nums[i]:
            primes.append(i)
            for j in range(2*i,n,i):
                nums[j] = False
    return primes

def main():
    n = int(input())
    A = set(map(int,input().split()))

    Amax = max(A)
    primes = set(prime(Amax+1))
    ct = 1
    if len(A) != n:
        ct = 2
    for p in primes:
        g = set(())
        temp = p
        while temp <= Amax:
            g.add(temp)
            temp+=p
        
        k = len(g & A)
        if k > ct:
            ct = k
    
    if ct == len(A):
        print("not coprime")
    elif ct == 1:
        print("pairwise coprime")
    else:
        print("setwise coprime")
main()

Submission status: Wrong Answer

Solution code:
def gcd(x,y):
  return y if x%y==0 else gcd(y,x%y)

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


primes=[];
isprime=[1 for i in range(0,1001)];
isprime[1]=0;isprime[0]=0
for i in range(2,1001):
  if isprime[i]:
    primes.append(i)
    j=2;
    while i*j<=1000:
      isprime[i*j]=0;
      j+=1
#s=set();
A.sort();


pc=1

l=A[0]
for i in range(1,N):
  if l==A[i]:
    pc=0
  l=A[i];

#s=[0 for i in range(0,1001)];
s=[0 for i in range(0,1001)]
#s2=set();
for i in range(N):
  a=A[i];
  
  for p in primes:
    #if a==1:
    #  break
    if(a%p==0):
      #while(a%p==0):
      #  a//=p;
      if s[p]:
        pc=0
      s[p]=1
    #if a>=1000:
    #if a!=1:
      #if a in s2:
      #if s[a]:
      #  pc=0
      #s2.add(a)
      #s[a]=1


g=A[0];
for i in range(1,N):
  g=gcd(g,A[i])
print("pairwise coprime"if pc else("setwise coprime"if g==1 else "not coprime"))

Submission status: Wrong Answer

Solution code:
import sys,os
import math
from fractions import Fraction 
from collections import defaultdict
from random import randint

# sys.stderr=open('err.txt','w')
# sys.stdout=open('output.txt','w')
# sys.stdin=open('input.txt','r')

def linput():
    return list(minput())

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

###############################################################

def gdc(a,b):
    while b:
        a,b = b, a%b
    return a

n=int(input())
a=linput()
flg=0
for i in range(len(a)-1):
    if gdc(a[i],a[i+1])!=1:
        flg=1
        break
if flg==0:
    print("pairwise coprime")
else:
    g=gdc(a[0],a[1])
    for i in range(2,len(a)):
        g=gdc(g,a[i])
    if g==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()))

dp=[0 for _ in range(1000000+1)]

sosuu = [2]
A = 1000
for L in range(3, A, 2): # 2 以外の素数は奇数なので
    for L2 in sosuu:
        if L % L2 == 0:
            break # 素数でないことがわかったらそれ以上ループする必要はない
    else: # break で抜けることがなかったら L は素数（Python 特有の制御構文）
        sosuu.append(L)

if n>=80000:
  print('pairwise coprime')
  
else:
  ch1=0
  ch3=0
  for w in sosuu:
    ch2=0
    for q in range(n):
      if a[q]%w==0:
        ch2+=1
        S=a[q]
        while S%w==0:
          S=S//w
        a[q]=S
    if ch2>1:
      ch3+=1
  d={}
  ch4=0
    
  for u in a:
      if u>1000:
        if u not in d:
          d[u]=0
        else:
          ch4+=1
  if ch3==0 and ch4==0:
    print('pairwise coprime')
      
  
  
    
  else:
    g=a[0]
    for h in range(1,n):
      g=math.gcd(g,a[h])
    
    if g==1:
      print('setwise coprime')
    
    else:
      print('not coprime')

Submission status: Wrong Answer

Solution code:
import os
import heapq
import sys,threading
import math
import operator
from collections import defaultdict,deque
from io import BytesIO, IOBase
import math as mt
sys.setrecursionlimit(10 ** 5)
threading.stack_size(2**27)


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


"""def pw(a,b):
    result=1
    while(b>0):
        if(b%2==1): result*=a
        a*=a
        b//=2
    return result"""


def inpt():
    return [int(k) for k in input().split()]

def main():
    MAXN=100002
    prime=[0]*MAXN
    prime[1] = 1
    for i in range(2, MAXN):
        prime[i] = i

    for i in range(4, MAXN, 2):
        prime[i] = 2

    for i in range(3, mt.ceil(mt.sqrt(MAXN))):
        if (prime[i] == i):
            for j in range(i * i, MAXN, i):
                if (prime[j] == j):
                    prime[j] = i
    n=int(input())
    ar=inpt()
    d=defaultdict(set)
    ok=True
    for i in ar:
        x=i
        while(x!=1):
            tp=prime[x]
            x=x//prime[x]
            d[tp].add(i)

    for i in d.keys():
        if(len(d[i])>1):
            ok=False
            break

    if(ok):
        print('pairwise coprime')
        exit()

    gcd=ar[0]
    for i in range(1,n):
        gcd=mt.gcd(gcd,ar[i])

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




BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

if __name__ == "__main__":
    #main()
    threading.Thread(target=main).start()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6)


def main(input, print):
    N = int(input())
    A = list(map(int, input().split()))
    A = sorted(A)
    m = 100
    table = [0] * (m+1)
    for i in range(2, m+1):
        for j in range(N):
            if A[j] % i == 0:
                table[i] += 1
        if table[i] == N:
            print('not coprime')
            return
        if table[i] > 1:
            print('setwise coprime')
            return
    print('pairwise coprime')


if __name__ == '__main__':
    main(sys.stdin.readline, print)

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.values():
            dic[temp] += 1
        else:
            dic[temp] = 1
# print(ans[0:10])

ans = dic.values()
# print(ans)

if max(ans) == n:
    print("not coprime")
elif max(ans) == 1:
    print("pairwise coprime")
else:
    print("setwise coprime")

Submission status: Wrong Answer

Solution code:
def get_d(a):
  list = []
  for i in range(1,a):
    if a%i == 0:
      list.append(i)
  return list

input_N = input()
N = int(input_N)
a_str = input().split()
dict = {}
for a in a_str:
  dict[a]=get_d(int(a))
pair_flag = True
total_d = []
first_flag = True
for i in range(N-1):
  d_list = []
  new_total_d =[]
  for d in dict[a_str[i]]:
    if d in dict[a_str[i+1]]:
      d_list.append(d)
  for d in d_list:
    if d in total_d:
      new_total_d.append(d)
  if first_flag:
      new_total_d = d_list
      first_flag = False
  total_d = new_total_d
  d_list.sort()
  if not d_list == [1]:
    pair_flag = False
if pair_flag == True:
  print('pairwise coprime')
else:
  total_d.sort()
  if total_d == [1]:
    print('setwise coprime')
  else:
    print('not coprime')

Submission status: Wrong Answer

Solution code:
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
def s(): return input()
def i(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10 ** 9)
INF = 10**9
mod = 10**9+7

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

    if temp!=1:
        num[temp] += 1
        F = 1

    if F == 0:
        num[n] += 1

N = i()
A = l()
num = [0]*(10**6+1)
for i in range(N):
    factorization(A[i])
if max(num) == 1:
    print('pairwise coprime')
elif max(num) == N:
    print('not coprime')
else:
    print('setwise coprime')

Submission status: Wrong Answer

Solution code:
from math import gcd


def factorize(n):
    b = 2
    fct = []
    while b * b <= n:
        while n % b == 0:
            n //= b
            fct.append(b)
        b = b + 1
    if n > 1:
        fct.append(n)
    return set(fct)


n = int(input())
a = list(map(int, input().split()))
b = a[0]

new_a = list(map(factorize, a))
wa = new_a[0]
cnt = 0
flag = 0
for i in range(1, n):
    b = gcd(b, a[i])
    if b == 1:
        break
    if len(wa & new_a[i]) > 0 and flag == 0:
        flag = 1
    wa = wa | new_a[i]
if b != 1:
    print("not coprime")
    exit()
if flag:
    print("setwise coprime")
else:
    print("pairwise coprime")

# for i in range(1, n):
#     b = gcd(b, a[i])
#     if b == 1:
#         break
# else:
#     print("not coprime")
#     exit()
#
# new_a = list(map(factorize, a))
# wa = new_a[0]
# cnt = 0
# flag = 0
# for i in range(1, n):
#     if len(wa & new_a[i]) > 0 and flag == 0:
#         flag = 1
#         break
#     wa = wa | new_a[i]
#
# if flag:
#     print("setwise coprime")
# else:
#     print("pairwise coprime")