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:
from math import gcd
import sys

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

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

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

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


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


sorted_A = sorted(A)

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

Submission status: Wrong Answer

Solution code:
import numpy as np

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

Submission status: Wrong Answer

Solution code:
from math import gcd
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")
    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
n = int(input())
a = list(map(int, input().split()))
b = a[0]
for i in range(1, n):
    b = gcd(b, a[i])
if b != 1: print("not coprime")
else:
    data = get_sieve_of_eratosthenes(1000)
    count = [0]*(len(data))
    d = 0
    for j in range(len(data)):
        for i in range(n):
            if a[i]%data[j] == 0:
                if count[j] == 1:
                    print("setwise coprime")
                    d = 1
                    break
                else:
                    count[j] = 1
        if d == 1:
            break
    else: print("pairwise coprime")

Submission status: Wrong Answer

Solution code:
import math
n=int(input())
l=list(map(int,input().split()))
e=0
e1=0
e2=0
e3=0
e4=0
e5=0
e6=0
e7=0
e8=0
c=l[0]
aa=0
for i in range(1,n):
    c=math.gcd(l[i],c)
for i in range(n):
    if(l[i]%2==0):
        e+=1
    if(l[i]%3==0):
        e1+=1
    if(l[i]%5==0):
        e2+=1
    if(l[i]%7==0):
        e3+=1
    if(l[i]%11==0):
        e4+=1
    if(l[i]%13==0):
        e5+=1
    if(l[i]%17==0):
        e6+=1
    if(l[i]%19==0):
        e7+=1
    if(l[i]%23==0):
        e8+=1
    if(e1>=2 or e2>=2 or e3>=2 or e4>=2 or e5>=2 or e6>=2 or e7>=2 or e8>=2 or e>=2):
        aa=1
        break

    
if(aa==1 and c==1):
    print("pairwise coprime")
elif(c==1):
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

def gcd(p,q):
# Create the gcd of two positive integers.
    while q != 0:
        p, q = q, p%q
    return p

def is_coprime(x, y):
    return gcd(x, y) == 1


N = int(input())
A = list(map(int,input().split()))
flag = False
cnt = 0
GCDArr = A[0]
for i in range(N):
    for j in range(i+1,N):
        if is_coprime(A[i],A[j]) == True:
            flag = True
        else:
            flag = False
if flag == True:
    print("pairwise coprime")
else:
    for i in range(N):
        GCDArr = gcd(GCDArr,A[i])
    if GCDArr == 1:
        print("setwise coprime")
        print(cnt)
    else:
        print("not coprime")

Submission status: Wrong Answer

Solution code:
from math import gcd
import sys

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

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

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

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


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


sorted_A = sorted(A)

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

Submission status: Wrong Answer

Solution code:
import math

def gcd(a, b):
    if a < b:
        return gcd(b, a)
    while b > 0:
        a, b = b, a % b
    return a

def eratosthenes(n):
    checker = [0] * (n+1)
    checker[0] = 1 #素数でない
    checker[1] = 0 #素数でない
    for i in range(2, n):
        if checker[i] == 0:
            for j in range(2, n // i + 1):
                checker[i * j] = i
    return checker

def check_by_eratosthenes(x, checker):
    if checker[x] == 0:
        checker[x] = -1
        return True
    if checker[x] < 0:
        return False
    else:
        y = x // checker[x]
        if checker[y] != checker[x] and y != checker[x]:
            checker[checker[x]] = -1
        if y < checker[x]:
            checker[x] = -1
        return check_by_eratosthenes(y, checker)

n = int(input())
a = list(map(int, input().split()))
a.sort()
for i in range(n):
    if a[i] != 1:
        break
a = a[i:]
n -= i
if n == 1:
    print("pairwise coprime")
    quit()

checker = eratosthenes(a[-1])
x = a[0]

pairwise = True
setwise = True
for i in range(n):
    if x != 1:
        x = gcd(x, a[i])
    if pairwise:
        pairwise = check_by_eratosthenes(a[i], checker)

if pairwise:
    print("pairwise coprime")
elif x == 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=1000001
    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(int)
    ok=True
    for i in ar:
        x=i
        while(x!=1):
            tp=prime[x]
            x=x//prime[x]
            if(tp in d and d[tp]!=i):
                ok=False
                break
            d[tp]=i

    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:
def abc177_e():
    n = int(input())
    A = list(map(int, input().split()))

    from math import gcd
    cumf = [1]*n
    cumr = [1]*n
    cumf[0] = A[0]
    cumr[-1] = A[-1]
    for i in range(1, n):
        cumf[i] = gcd(cumf[i-1], A[i])
    for i in range(n-2, -1, -1):
        cumr[i] = gcd(cumr[i+1], A[i])

    if cumr[0] > 1:
        return print('not coprime')

    def prime_factorize(n: int) -> list:
        ''' nの素因数分解 '''
        arr = []
        while n % 2 == 0:
            arr.append(2)
            n = n // 2
        f = 3
        while f * f <= n:
            if n % f == 0:
                arr.append(f)
                n = n // f
            else:
                f += 2
        if n != 1:
            arr.append(n)
        return set(arr)

    setwise = False
    #inf = 10**6 + 1
    inf = max(A)+1
    fac = [0]*inf
    for i in range(n-1, -1, -1):
        if A[i] == 1: break
        for p in prime_factorize(A[i]):
            if fac[p] == 1:
                setwise = True
                break
            fac[p] = 1
        if setwise: break
    ans = 'setwise coprime' if setwise else 'pairwise coprime'
    return print(ans)

if __name__ == '__main__':
    abc177_e()

Submission status: Wrong Answer

Solution code:
import math
n=int(input())
a=list(map(int,input().split()))
pflag=True
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

if len(set(a))!=n:
  pflag=False
sosu=[1]*(10**6+1)
sosu[0]=0

k=2
while k<(10**6+1)**0.5+1:
  for i in range(2*k,10**6+1,k):
    sosu[i]=0
  if k==2:
    k+=1
  else:
    k+=2
gu=0
import copy
ans=copy.deepcopy(sosu)

for i in range(n):
  if sosu[a[i]]==0 and gu>1:
    ai = set(prime_factorize(a[i]))
    for j in ai:
      if ans[j]==0:
        pflag=False
        break
      else:
        ans[j]=0
  else:
    ans[a[i]]=0
    pflag=False
  if a[i]%2==0:
    gu+=1
  ans[a[i]]=0
    
if pflag == False:
  setwise=a[0]
  for i in range(1,n):
    setwise=math.gcd(setwise,a[i])
  if setwise == 1:
    print("setwise coprime")
  else:
    print("not coprime")
else:
  print('pairwise coprime')

Submission status: Wrong Answer

Solution code:
import math
from functools import reduce

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

def gcd_list(numbers):
    return reduce(math.gcd, numbers)
 
def eratosthenes(limit):
    A = [i for i in range(2, limit+1)]
    P = []
 
    while True:
        prime = min(A)
 
        if prime > math.sqrt(limit):
            break
 
        P.append(prime)
 
        i = 0
        while i < len(A):
            if A[i] % prime == 0:
                A.pop(i)
                continue
            i += 1
 
    for a in A:
        P.append(a)
 
    return P
 
 
er = eratosthenes(1500)
s_er = set(er)
 
 
def make_divisors(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if i not in s_er:
            continue
        if temp % i == 0:
            arr.append(i)
 
    if temp != 1:
        arr.append(temp)
 
    if arr == []:
        arr.append(n)
 
    a = set(arr)
    if 1 in a:
        a.remove(1)
 
    return a
 
 
n = int(input())
a = list(map(int, input().split()))
 
is_pairwise = True
is_setwise = False
 
f_set = set()
n_set = set()
 
for item in a:
    if item in n_set:
        is_pairwise = False
        break
    else:
        if item != 1:
            n_set.add(item)
    for fc in make_divisors(item):
        if fc in f_set:
            is_pairwise = False
            break
        else:
            f_set.add(fc)
    if not is_pairwise:
        break
 
ret = gcd_list(a)
if ret == 1:
    is_setwise = True
 
if is_pairwise:
    print('pairwise coprime')
elif is_setwise:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Wrong Answer

Solution code:
import sys, math
input= sys.stdin.readline

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

def GCD(A, B):
  return math.gcd(A, B)

def LCM(A, B, g):
  return A*B//g

G = A_lst[0]
L = A_lst[0]
is_p = True
is_n = True
for a in A_lst[1:]:
  G = GCD(L, a)
  if is_p:
    if G!=1:
      is_p = False
  if is_n:
    if G == 1:
      is_n = False
  L = LCM(L, a, G)
if is_p:
  print('pairwise coprime')
elif is_n:
  print('not coprime')
else:
  print('setwise coprime')

Submission status: Wrong Answer

Solution code:
import math
from functools import reduce

n = int(input())
a = list(map(int, input().split()))
flag =1
if reduce(math.gcd, a) != 1:
        print("not coprime")
        flag = 0
if flag == 1:
        for i  in range(n):
                for j in range(i+1, n):
                                if math.gcd(a[i], a[j]) != 1:
                                        print("setwise coprime")
                                        flag = 0
                                        break
                                else:
                                        continue
                break
if flag == 1:
        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:
from math import gcd

# = map(int, input().split())
N = int(input())
A = list(map(int, input().split()))
mA = max(A)
counter = [0 for _ in range(mA+1)]

primenum = [2]
sgn = [-1 for _ in range(int(mA**0.5)+1)]
k = 3
while k**2 <= mA:
  if sgn[k] == -1:
    primenum.append(k)
    add = k*k
    while k**2 <= mA:
      sgn[k] = 1
      k += add
  k += 2
#prime_num が用意されているとき
def factorization(n):
  M = n
  f = True
  for p in primenum:
    if p**2 > M:
      break
    else:
      if M%p == 0:
        if counter[p] == 0:
          counter[p] = 1
        else:
          f = False
        while M%p == 0:
          M //= p

  if M > 1:
    if counter[M] == 0:
      counter[M] = 1
    else:
      f = False
  return f


g = A[0]
flag = True
for k in range(N):
  a = A[k]
  g = gcd(g, a)
  if flag:
    flag = factorization(a)
if flag:
  print('pairwise coprime')
  exit()
if g == 1:
  print('setwise coprime')
else:
  print('not coprime')

Submission status: Wrong Answer

Solution code:
import math

def gcd(a, b):
    if a < b:
        return gcd(b, a)
    while b > 0:
        a, b = b, a % b
    return a

def eratosthenes(n):
    checker = [0] * (n+1)
    checker[0] = 1 #素数でない
    checker[1] = 0 #素数でない
    for i in range(2, n):
        if checker[i] == 0:
            for j in range(2, n // i + 1):
                checker[i * j] = i
    return checker

def check_by_eratosthenes(x, checker):
    if checker[x] == 0:
        checker[x] = -1
        return True
    if checker[x] < 0:
        return False
    else:
        y = x // checker[x]
        if checker[y] != checker[x] and y != checker[x]:
            checker[checker[x]] = -1
        checker[x] = -1
        return check_by_eratosthenes(y, checker)

n = int(input())
a = list(map(int, input().split()))
a.sort()
for i in range(n):
    if a[i] != 1:
        break
a = a[i:]
n -= i
if n == 1:
    print("pairwise coprime")
    quit()

checker = eratosthenes(a[-1])
x = a[0]

pairwise = True
setwise = True
for i in range(n):
    if x != 1:
        x = gcd(x, a[i])
    if pairwise:
        pairwise = check_by_eratosthenes(a[i], checker)

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

Submission status: Wrong Answer

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

import math
import sys
tmp = A[0]

for i in range(1,N):
    tmp = math.gcd(tmp,A[i])
    
if tmp != 1:
    print("not coprime")
    sys.exit()
    
tmp_list = [0]*(max(A)+1)

def make_divisors(n,tmp_list):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            #divisors.append(i)
            tmp_list[i] += 1
            if i != n // i:
                #divisors.append(n//i)
                tmp_list[i] += 1

    #divisors.sort()
    return tmp_list

for i in range(N):
    make_divisors(A[i],tmp_list)

tmp_list
for i in range(2,max(A)+1):
    if tmp_list[i] > 1:
        print("setwise coprime")
        sys.exit()
        
print("pairwise coprime")

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np
sys = sys.stdin.buffer.readline
N = int(input())
A = np.array(list(map(int, input().split())))


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


def factorization(n):
    arr = []
    temp = n
    for i in range(2, n):
        if i * i > 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)
    # if temp != 1:
    #     arr.append([temp, 1])
    # if arr == []:
    #     arr.append([n, 1])
    return arr


# A = sorted(A)
# print(f'{A=}')
# print(primes)
arr = set(factorization(A[0]))
S = set([])
for a in A:
    # print(f'{a=}')
    tmp = set(factorization(a))
    # print(f'{arr=}, {tmp=}')
    arr = arr & tmp
    S = S | tmp
    # print(f'{arr=}, {S=}')

if len(arr) != 0:
    print('not coprime')
else:
    for s in S:
        # print(A % s, s)
        if np.count_nonzero(A % s == 0) >= 2:
            print('setwise coprime')
            exit()
    print('pairwise coprime')

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

def f(n):
    yakusu = []
    for i in range(1, int(n ** 0.5) + 1):
        if n % i == 0:
            yakusu.append(i)
            if i != n // i:
                yakusu.append(n // i)
    for i in yakusu:
        if i != 1:
            d[i] += 1

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

for i in range(N):
    f(A[i])

cnt = 0
for i, v in d.items():
    if v != 1:
        cnt = max(cnt, v)

if cnt == N:
    print('not coprime')
elif cnt == 1:
    print('pairwise coprime')
else:
    print('setwise coprime')

Submission status: Wrong Answer

Solution code:
try:
    from math import gcd
except ImportError:
    from fractions import gcd

n = int(input())
a = [int(_) for _ in input().split()]
p = [2]
a.sort()
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
gc = a[0]
for i in range(n):
    if a[i] == 1:
        print("pairwise coprime")
        exit(0)
    temp = a[i]
    gc = gcd(gc, 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 gc == 1:
    print("setwise coprime")
else:
    print("pairwise 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=1000001
    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 math
 
 
def eratosthenes(limit):
    A = [i for i in range(2, limit+1)]
    P = []
 
    while True:
        prime = min(A)
 
        if prime > math.sqrt(limit):
            break
 
        P.append(prime)
 
        i = 0
        while i < len(A):
            if A[i] % prime == 0:
                A.pop(i)
                continue
            i += 1
 
    for a in A:
        P.append(a)
 
    return P
 
 
er = eratosthenes(1500)
s_er = set(er)
 
 
def make_divisors(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if i not in s_er:
            continue
        if temp % i == 0:
            arr.append(i)
 
    if temp != 1:
        arr.append(temp)
 
    if arr == []:
        arr.append(n)
 
    a = set(arr)
    if 1 in a:
        a.remove(1)
 
    return a
 
 
n = int(input())
a = list(map(int, input().split()))
 
is_pairwise = True
is_setwise = False
 
f_set = set()
n_set = set()
 
for item in a:
    if item in n_set:
        is_pairwise = False
        break
    else:
        if item != 1:
            n_set.add(item)
    for fc in make_divisors(item):
        if fc in f_set:
            is_pairwise = False
            break
        else:
            f_set.add(fc)
    if not is_pairwise:
        break
 
if is_pairwise:
    print('pairwise coprime')
elif is_setwise:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Wrong Answer

Solution code:
from math import gcd
def lcm(a):
    x = a[0]
    for i in range(1, len(a)):
        x = (x * a[i]) // gcd(x, a[i])
    return x

n = int(input())
a = list(map(int, input().split()))
lenn = n
na = a
flag = 0
mod = 170141183460469231731687303715884105727
for i in range(n):
    templ = []
    for j in range(0, lenn, 2):
        if(j + 1 >= lenn):
            templ.append(a[j]%mod)
        else:
            temp = gcd(a[j], a[j+1])%mod
            if(temp == 1):
                templ.append(((a[j]*a[j+1])%mod//temp)%mod)
            else:
                ans = na[0]
                for k in range(1, n):
                    ans = gcd(ans, na[k])
                if(ans == 1):
                    flag = 1
                else:
                    flag = 0
                break
    a = templ
    lenn = len(templ)
    if(lenn == 1):
        flag = 2
        break
if(flag == 2):
    print("pairwise coprime")
elif(flag == 1):
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Wrong Answer

Solution code:
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
 
N=int(input())
A=[int(x) for x in input().split()]
 
def factorization(n):
    arr = 1
    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*=i
 
    if temp!=1:
        arr*=temp
 
    return arr
 
A=[factorization(n) for n in A]
result="pairwise coprime"
 
for i in callIsPrime(min(1000,max(A))):
  on=0
  off=0
  for a in set(A):
    if a%i==0:
      on+=1
    elif a%i!=0:
      off+=1
    if on>=2 and off>=1:
      break
  if on>=2 and off==0:
    result="not coprime"
    break
  elif on>=2:
    result="setwise coprime"
  A=[x/i if x % i == 0 else x for x in A]
  A=[x for x in A if x>=i]

if len(set(A))==1:
  result="not coprime"
elif result!="not coprime" and len(set(A))!=len(A):
  result="setwise coprime"
print(result)

Submission status: Wrong Answer

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

from math import gcd

def main():
    n = int(input())
    A = list(map(int , input().split()))
    N = max(A)+1
    
    c = 0
    for i in A:
      if i > 10**5:
        c += 1
        
    if n > 9.9*10**5 and c > N/2:
        print("pairwise coprime")
        exit()
    sv = [i for i in range(N)]
    for i in range(2 ,int(N**2)+1) :
        if i * i >= N : break
        if sv[i] < i : continue
        for j in range(i * i , N , i) :
            sv[j] = min(sv[j] , i)

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

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

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

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

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

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

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

main()

Submission status: Wrong Answer

Solution code:
import math

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

B = [1] * N
B[0] = A[0]
for i in range(1, N):
    B[i] = B[i - 1] * A[i]

is_pairwise = True
X = []
for i in range(N-1):
    g = math.gcd(A[i], B[-1]//B[i])
    if g != 1:
        is_pairwise = False
        X.append(g)

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

tmp = X[0]
for i in range(1, len(X)):
    tmp = math.gcd(tmp, X[i])

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