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

isSetWise = False
gcd = A[0]
for i in range(1, N):
    gcd = math.gcd(gcd, A[i])
if gcd == 1:
    isSetWise = True

isPairWise = True
for i in range(N-1):
    if math.gcd(A[i], A[i+1]) != 1:
        isPairWise = False
        break

if isPairWise:
    print("pairwise coprime")
    exit()

if isSetWise:
    print("setwise coprime")
    exit()

print("not coprime")

Submission status: Wrong Answer

Solution code:
import sys
mod=10**9+7 ; inf=float("inf")
from math import sqrt, ceil
from collections import deque, Counter, defaultdict #すべてのkeyが用意されてる defaultdict(int)で初期化
input=lambda: sys.stdin.readline().strip()
sys.setrecursionlimit(11451419)
from decimal import ROUND_HALF_UP,Decimal  #変換後の末尾桁を0や0.01で指定
  #Decimal((str(0.5)).quantize(Decimal('0'), rounding=ROUND_HALF_UP))
from functools import lru_cache
from bisect import bisect_left as bileft, bisect_right as biright
#メモ化再帰defの冒頭に毎回 @lru_cache(maxsize=10**10)
#引数にlistはだめ
#######ここまでテンプレ#######
#ソート、"a"+"b"、再帰ならPython3の方がいい
#######ここから天ぷら########

n=int(input())

A=list(map(int,input().split()))
from math import sqrt
def eratosu(n):
  if not isinstance(n,int):
    raise TypeError("nがint型になってねえぞ")
  if n<2:
    raise ValueError('nが2よりちっちぇえぞ')
  prime = []
  limit = sqrt(n)
  data = [i+1 for i in range(1, n)]  #2,3,4,...,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]
PRIME=eratosu(10**6)
@lru_cache(maxsize=10**10)
def bunkai(n):
    if n==1:return []
    ans=[]
    temp=n
    #そんな早くしなくてよかったり、何回もするわけじゃないなら、
    #for i in range(2,int(sqrt(n))+1): とかで
    primelist= PRIME
    for i in primelist:
        if i>sqrt(n):break
        if temp % i ==0:
            ji=0
            while temp%i==0:
                ji+=1
                temp//=i
            ans.append([i,ji])
    if ans==[]:return([[n,1]])  #素数のとき
    if temp!=1:
        ans.append([temp,1])  #4*5882353とか
    return ans

flag=1
seen={i:0 for i  in PRIME}
#print(bunkai(3))
for i in A:
    for l in bunkai(i):
        now=l[0] 
        if seen[now]!=0:
            flag=0
        seen[now]+=1
if flag:
    print("pairwise coprime")
elif max(seen)!=n:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Wrong Answer

Solution code:
import math
from functools import reduce

def gcd(numbers):
    return reduce(math.gcd, numbers)
def gcd_list(numbers):
    return reduce(math.gcd, numbers)
def lcm(x, y):
    return (x * y) // math.gcd(x, y)

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

def main():
    if gcd_list(A) != 1:
        print("not coprime")
        exit()

    flag = True
    LCM = A[-1]
    for i in range(N - 2, -1, -1):
        if LCM // A[i] == (LCM + A[i] - 1) // A[i]:
            flag = False
            break

        LCM *= A[i]

    if flag:
        print("pairwise coprime")
    else:
        print("setwise coprime")

if __name__ == "__main__":
    main()

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:
from sys import stdin, setrecursionlimit
#input = stdin.buffer.readline
setrecursionlimit(10 ** 7)

from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
from collections import deque, defaultdict, Counter
from itertools import combinations, permutations, combinations_with_replacement
from itertools import accumulate
from math import ceil, sqrt, pi, radians, sin, cos

MOD = 10 ** 9 + 7
INF = 10 ** 18

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

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 = [2]
    limit = int(n**0.5)
    data = [i + 1 for i in range(2, n, 2)]
    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(1000001)
data2 = get_sieve_of_eratosthenes(1001)

# 1~1000000の素数リストを作成
check = [0] * (10 ** 6 + 5)
for d in data:
    check[d] = 1

# 素因数分解
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

def is_pairwise(arr):

    cnt = [0] * 1000001
    
    # 非素数が168個以上あったらアウト
    non_prime = []
    for a in arr:
        if check[a] == 0:
            non_prime.append(a)
        else:
            cnt[a] += 1
    if len(non_prime) > 1000:
        return 0
    
    # 非素数を素因数分解して、cntに足し合わせる
    for np in non_prime:
        for a, b in factorization(np):
            cnt[a] += 1
    if max(cnt[2:]) >= 2:
        return 0
    
    return 1
    
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

def is_setwise(arr):
    
    tmp = arr[0]
    for a in arr:
        tmp = gcd(tmp, a)
    if tmp == 1:
        return 1
    else:
        return 0
        
ip = is_pairwise(A)
iss = is_setwise(A)

if ip:
    print("pairwise coprime")
else:
    if iss:
        print("setwise coprime")
    else:
        print("not coprime")

Submission status: Wrong Answer

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

import itertools
import math
#
# 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 = math.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:
m = int(input())
a = list(map(int, input().split()))
max_int = a[m-1] // 2 + 1

flg = 0
for i in range(max_int-1):
  tmp = list(map(lambda x: x % (i+2), a))
  c = tmp.count(0)
  if c == m:
    flg = 2
    break
  elif c >= 2:
    flg = 1
  
if flg == 1:
  print("setwise coprime")
elif flg == 2:
  print("not coprime")
else:
  print("pairwise 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 len(targets) != N:
        is_pw = False

    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 math import gcd
from functools import reduce

def lcm(a, b):
    div = pow(gcd(a, b), p - 2, p)
    return (a * b * div) % p

def lcm_list(A):
    return reduce(lcm, A)

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

def mul_mod(a, b):
    return a * b % p

n = int(input())
a = [int(x) for x in input().split()]
p = 10 ** 9 + 7

if gcd_list(a) == 1:  # setwise coprime or pairwise coprime
    prod_a = reduce(mul_mod, a)
    lcm_a = lcm_list(a)
    if prod_a == lcm_a:
        print('pairwise coprime')
    else:
        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=1000002
    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:
#abc177 e
import sys,math,collections,itertools
input = sys.stdin.readline


N=int(input())
A=list(map(int,input().split()))
num = [0]*(10**6+1)
for a in A:
    num[a]+=1
    i=2
    while i*i <=a:
        if a%i==0:
            num[i]+=1
            if i*i != a:
                num[a//i]+=1
        i+=1
mn = max(num)

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

Submission status: Wrong Answer

Solution code:
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
import random

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

pc = True
sc = True
M = {}
MAX = 0

if N == 1:
    pc,sc = False,False
for i,A in enumerate(A_s):        
    for p in factorization(A):
        if p[0] in M:
            M[p[0]] += 1
            pc = False
        else:
            M[p[0]] = 1
        MAX = max(MAX, M[p[0]])
    if not pc and MAX <= i:
        break
else:
    sc = False

if pc:
    print('pairwise coprime')
elif sc:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Wrong Answer

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

ans = ["pairwise coprime", "setwise coprime", "not coprime"]
p_list = [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]
#print(p_list)

def factorization(n):
    arr = []
    temp = n
    for i in p_list:
      if (n >= i):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
      else:
        break
        
    if temp != 1:
        arr.append([temp, 1])

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

    return arr
  
ans_ = 0
used = [0] * len(p_list)
for i in range(N):
  x = factorization(A[i]) 
  for j in range(len(x)):
    if x[j][0] in p_list:
      used[p_list.index(x[j][0])] += 1
      if used[p_list.index(x[j][0])] != 1:
        ans_ = 1
  #print(x, used[:10])
  
if max(used) == N:
  ans_ = 2
  
print(ans[ans_])

Submission status: Wrong Answer

Solution code:
import math
def gcd(x,y):
  return math.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"))


#print(gcd(1,1))

Submission status: Wrong Answer

Solution code:
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

#factorization(24) 

## [[2, 3], [3, 1]] 
##  24 = 2^3 * 3^1

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

#A = sorted(A)

ansN = A[0]
for i in range(1, n):
    ansN = math.gcd(ansN, A[i])
if ansN > 1:
    print('not coprime')
else:
    ans2 = True
    C = [0 for _ in range(10**6+10)]
    for a in A:
        F = factorization(a)
#        print(F)
        for f in F:
            if C[f[0]] == 0:
                C[f[0]] = 1
#                print('!!')
            else:
                ans2 = False
                break
        else:
            continue
        break
    if ans2:
        print('pairwise coprime')
    else:
        print('setwise coprime')

Submission status: Wrong Answer

Solution code:
import sys, bisect, math, itertools, heapq, collections
from operator import itemgetter
# a.sort(key=itemgetter(i)) # i番目要素でsort
from functools import lru_cache
# @lru_cache(maxsize=None)
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
mod = 10**9 + 7
eps = 10**-7


def inp():
    '''
    一つの整数
    '''
    return int(input())


def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))


def str_inp():
    '''
    文字列をリストとして読み込む
    '''
    return list(input()[:-1])


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]


n = inp()
a = inpl()

data = get_sieve_of_eratosthenes(10**6)
dp = {i: 0 for i in data}
for i in range(n):
    tmp = a[i]
    for j in data:
        if tmp == 1:
            break
        if tmp % j == 0:
            dp[j] += 1
            while tmp % j == 0:
                tmp //= j
ans=max(list(dp.values()))
if ans==1:
    print("pairwise coprime")
elif ans==n:
    print("not coprime")
else:
    print("setwise coprime")
# ans = "pairwise coprime"
# for i in data:
#     coprime = 0
#     for j in range(n):
#         if a[j] % i == 0:
#             coprime += 1
#         elif a[j] % i != 0 and (coprime >= 2 or ans == "setwise coprime"):
#             break
#     if coprime == n:
#         ans = "not coprime"
#         break
#     elif coprime >= 2:
#         ans = "setwise coprime"
# print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict
from fractions import gcd
N=int(sys.stdin.readline().strip())
A=map(int, sys.stdin.readline().split())

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

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

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

    return arr

pairwise_coprime=True

SOINSU=defaultdict(lambda: 0)

setwise_coprime=None
for i,a in enumerate(A):
    #全ての数が互いに素か　pairwise coprime判定
    if pairwise_coprime==False:
        pass
    else:
        f=factorization(a)
        for x in f:
            if SOINSU[x]==1:
                pairwise_coprime=False
                break
            SOINSU[x]=1
        #GCDの累積を取る　setwise coprime判定
        if i==0:
            setwise_coprime=a
        else:
            setwise_coprime=gcd(setwise_coprime,a)

if pairwise_coprime==True:
    print "pairwise coprime"
elif setwise_coprime==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//4,i+1),n-1),min(n//4+10000,n)):
            if math.gcd(a[i],a[j])!=1:
                print('setwise coprime')
                exit()
    print('pairwise coprime')

Submission status: Wrong Answer

Solution code:
def seachPrimeNum(N):
    max = int(N**.5)
    seachList = [i for i in range(2,N+1)]
    primeNum = []
    while seachList[0] <= max:
        primeNum.append(seachList[0])
        tmp = seachList[0]
        seachList = [i for i in seachList if i % tmp != 0]
    primeNum.extend(seachList)
    return primeNum

P=seachPrimeNum(5*10**5)

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

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

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

factorization(24) 

n=int(input())
A=[int(i) for i in input().split()]
DIC={i:0 for i in range(1,10**6+1)}
for ele in A:
    DIC[ele]=1
pair=True
setw=True
if n!=len(A):
    pair=False

for pri in P:
    cnt=0
    for i in range(pri,10**6+1,pri):
        cnt+=DIC[i]
    if cnt>1:
        pair=False
    if cnt==len(A):
        setw=False

if pair:
    print("pairwise coprime")
elif setw:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Wrong Answer

Solution code:
n=int(input()) 
c=list(map(int, input().split()))
ans = 1

import math
from functools import reduce
import fractions
def gcd_list(numbers):
    return reduce(math.gcd, numbers)

for i in range(n-1):
    f=fractions.gcd(c[i],c[i+1])
    ans = max(ans,f)

Ans = gcd_list(c)

if ans == 1 and Ans == 1:
    print('pairwise coprime')
if ans != 1 and Ans == 1:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Wrong Answer

Solution code:
import math
import copy

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


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 B[q]%w==0:
        ch2+=1
        S=B[q]
        while S%w==0:
          S=S//w
        B[q]=S
    if ch2>1:
      ch3+=1
  d={}
  ch4=0
    
  for u in B:
      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:
def main():
    import sys
    input = sys.stdin.buffer.readline
    from math import gcd
    N = int(input())
    A = list(map(int, input().split()))
    A.sort()
    S = 1
    d = dict()
    for x in A:
        S *= x
    flag = False

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

        else:
            print("not coprime")


main()

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())
if n>80000:
    print("not coprime")
    exit()
a = list(map(int,input().split()))
g = 0
f = 1
c1 = 0
for i in a:
    g = gcd(g,i)
    if i == 1:
        c1 += 1
    if f == 1:
        for j in p:
            if i%j == 0:
                c[j] += 1
                if c[j] > 1:
                    f = 0
# print(c1)
if len(set(a))+max(0,c1-1) != n:
    f = 0
# print(g,f)
if g == 1:
    if f == 1:
        print("pairwise coprime")
    else:
        print("setwise coprime")
else:
    print("not coprime")

Submission status: Wrong Answer

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

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]]

pl = primes(1000)

def fact(n):
    temp = n
    for i in pl:
        if temp%i==0:
            while temp%i==0:
                temp //= i
            dp[i] +=1

import math

temp = []
dp = [0]*(10**6+2)
#pairwise
for i in range(n):
    fact(al[i])

dpp = dp[2:]

if max(dpp)<=1:
    print("pairwise coprime")

elif max(dpp) ==n:
    print("not coprime")
    
else:
    print("setwise coprime")

Submission status: Wrong Answer

Solution code:
from collections import Counter
def make_divisors(n):
    divisors = []
    # 試し割りで、かつ積でnを作るときの相方も同時に追加してる
    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
from math import gcd
import sys
n = int(input())
a_ls = list(map(int, input().split()))
now = a_ls[0]
for i in range(1,n):
    now = gcd(now,a_ls[i])
if now != 1:
    print('not coprime')
    sys.exit()
else:
    a_ls.sort()
    Max = a_ls[-1]
    c = Counter(a_ls)

    res = 'pairwise coprime'
    
    lim = int(Max**0.5)+2
    isdone = [0] * (Max+1)
    # baseは共通の素因数の候補
    for base in range(2,lim+1):
        if base > Max:
            break
        if isdone[base]:
            continue

        now = base
        time_inA = 0
        while now <= Max:
            isdone[now] = 1
            if c[now] > 0:
                time_inA += c[now]
            now += base
            
        if time_inA >= 2:
            res = 'setwise coprime'
            break
            
    print(res)

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//3,i+1),n-1),min(n//3+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
from functools import reduce


def is_prime(n):
    if n <= 1:
        return False
    if n == 2:
        return True
    i = 2
    while i * i <= n:
        if n % i == 0:
            return False
        i += 1
    return True


# def Eratosthenes_sieve(n):
#     primes = []
#     table = [True] * (n + 1)
#     for i in range(n + 1):
#         if is_prime(i):
#             primes.append(i)
#     return primes


def Eratosthenes_sieve(n):
    table = [True] * (n + 1)
    for i in range(n + 1):
        if is_prime(i):
            for j in range(2 * i, n + 1, i):  # 素数の倍数は非素数
                table[j] = False
        else:
            table[i] = False
    return table


def calc_ggcd(arr):
    return reduce(gcd, arr)


def decomposition(n):
    if n == 1:
        return True
    is_coprime = True
    if appear[n]:
        is_coprime = False
    else:
        appear[n] = True
    # while i * i <= n:
    for i in primes:
        if i**2 > n:
            break
        if n % i == 0:
            if appear[i]:
                is_coprime = False
            else:
                appear[i] = True
    return is_coprime


n = int(input())
a = list(map(int, input().split()))
ma = max(a)
# primes = Eratosthenes_sieve(ma)
prime_table = Eratosthenes_sieve(ma + 1)
primes = []
for i in range(ma + 1):
    if prime_table[i]:
        primes.append(i)

appear = [False] * (max(a) + 1)
keep_pair_coprime = True

for aa in a:
    if not decomposition(aa):
        keep_pair_coprime = False

        # 素因数分解 O(√N)
global_gcd = calc_ggcd(a)
if keep_pair_coprime:
    print('pairwise coprime')
elif global_gcd == 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
    
l = 0
for i in range(len(A)):
  if A[i] % 3 != 0:
    l = 1
    
p = 0
for i in range(len(A)):
  if A[i] % 5 != 0:
    p = 1

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

Submission status: Wrong Answer

Solution code:
import sys
n=int(input())
A=[int(i) for i in input().split()]

N=10**6
spf = [i for i in range(N+1)]

for i in range(2,N):
    if i**2>N:
        break
    if spf[i] == i:
        for j in range(i**2,N+1,i):
            if spf[j] == j:
                spf[j] = i

def get(n):
    ps = set()
    while n != 1:
        ps.add(spf[n])
        n //= spf[n]
    return ps

f1=True
f2=True

n0 = list(get(A[0]))
K=set(n0)
J=set(n0)

for a in A[1:]:
    res = get(a)
    #print(K,J,res)
    
    if len(K & res) != 0:
        f1 = False
        
    if len(res) != 0:
        K &= res
        
    if len(J & res) !=0:
        f2 = False
        
    if len(res) != 0:
        J |= res
        
#print(K,J,res)        
        
if 1 in A:
    f1 = True

    
if f1:
    if f2:
        print("pairwise coprime")
    else:
        print("setwise coprime")
else:
    print("not coprime")