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 sys
N = int(input())
A = set(map(int, input().split())) #Aの要素の分布を集合として表記
MAX = 10**6

not_pairwise_coprime = False #19行目参照

for p in range(2,MAX+1):
  ct = 0 #pの倍数の個数を求める
  for q in range(p,MAX+1,p): #qはpの倍数全てを走る
    if q in A:
      ct += 1
  
  # ct = Nのとき、pはすべてのA_nの約数。つまり、Aはnot coprime
  if ct == N:
    print("not coprime")
    sys.exit()
  
  # 2 <= ct < Nのとき、pは2つ以上のA_nの約数。つまり、Aはpairwise coprimeではない。
  # setwise coprimeか、not coprimeかを判定するため、次のpを調べる必要あり。 
  elif ct >= 2:
    not_pairwise_coprime = True
  
  # ct <= 1のとき、pはどの２つのA_nの公約数にも一致しない。次のpを調べる必要あり。
  #else: continue
  
  
# ループが途中で終わるのは、not coprimeの時のみ。
# したがって、この時点で可能性があるのは、setwise coprimeかpairwise coprimeのどちらか。
print("setwise coprime" if not_pairwise_coprime else "pairwise coprime")

Submission status: Wrong Answer

Solution code:
import sys
import math
from collections import defaultdict, deque, Counter
from copy import deepcopy
from bisect import bisect, bisect_right, bisect_left
from heapq import heapify, heappop, heappush
    
input = sys.stdin.readline
def RD(): return input().rstrip()
def F(): return float(input().rstrip())
def I(): return int(input().rstrip())
def MI(): return map(int, input().split())
def MF(): return map(float,input().split())
def LI(): return tuple(map(int, input().split()))
def LF(): return list(map(float,input().split()))
def Init(H, W, num): return [[num for i in range(W)] for j in range(H)]
    
    
def main():
    N = I()
    mylist = LI()
    max_num = max(mylist)
    max_num2 = math.ceil(math.sqrt(max_num))
    D = [True]* (max_num+1)
    mylist = set(mylist)
    setwise = True
    pairwise = True

    for i in range(2, max_num2+1):
        temp = 0
        if D[i]:
            for j in range(i, max_num+1, i):
                D[j] = False
                if j in mylist:
                    temp+=1
        if temp == N:
            print("not coprime")
            
            sys.exit()
        if temp >= 2:
            pairwise = False

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

            
    
    
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
import math
import fractions
from collections import deque
from collections import defaultdict

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid(h, w, num): return [[int(num)] * w for _ in range(h)]


# Nの素因数分解を辞書で返す
def prime_fact(n, ela):
    if n == 1:
        return {1: 1}


    prime_dict = {}
    for i in ela:
        cnt = 0
        while n % i == 0:
            cnt += 1
            n = n // i
        if cnt:
            prime_dict[i] = cnt
        if n == 1:
            break
    if n != 1:
        prime_dict[n] = 1
    return prime_dict


def sieve_of_erastosthenes(num):
    input_list = [False if i % 2 == 0 or i % 3 == 0 or i % 5 == 0 else True for i in range(num)]
    input_list[0] = input_list[1] = False
    input_list[2] = input_list[3] = input_list[5] = True
    sqrt = math.sqrt(num)

    for serial in range(3, num, 2):
        if not input_list[serial]:
            continue

        if serial >= sqrt:
            return input_list

        for s in range(serial ** 2, num, serial):
            input_list[s] = False


def main():
    N = NI()
    A = NLI()
    ela = sieve_of_erastosthenes(1001)
    ela2 = [i for i, b in enumerate(ela) if b]

    if max(A) == 1:
        print("pairwise coprime")
        exit()

    g = A[0]
    for a in A:
        g = math.gcd(g, a)
    if g > 1:
        print("not coprime")
        exit()

    p_cnt = defaultdict(int)
    PD_list = defaultdict(dict)
    cnt = 0
    for a in A:
        if a == 1:
            continue

        cnt += 1
        if cnt >= 90000:
            print("not coprime")
            exit()

        if PD_list[a]:
            AP = PD_list[a]
        else:
            AP = prime_fact(a, ela2)
            PD_list[a] = AP
        for apk in AP.keys():
            p_cnt[apk] += 1

    max_p = max(p_cnt.values())
    if max_p == 1:
        print("pairwise coprime")
    elif max_p == N:
        print("not coprime")
    else:
        print("setwise coprime")



if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import numpy as np
from numba import njit


n = int(input())
arr = np.array(list(map(int, input().split())))


n = 10**3
primes = set(range(3, n+1, 2))

for i in range(3, int(n**0.5+1)):
    primes.difference_update(range(i*2, n+1, i))
primes.add(2)


@njit
def solve(arr, primes):
    used = [False] * 1000
    ans = True
    for x in arr:
        for p in primes:
            while x % p == 0:
                if used[p]:
                    ans = False
                    return ans
                while x % p == 0:
                    x //= p
                used[p] = True
    return ans


ans1 = solve(arr, primes)
ans2 = np.gcd.reduce(arr) == 1

if ans1 and ans2:
    print("pairwise coprime")
elif ans2:
    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()))

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

if g_all > 1:
    print('not coprime')
    quit()

def sieve(n):
    is_prime = [True for _ in range(n+1)]
    is_prime[0] = False
    for i in range(2, n+1):
        if is_prime[i-1]:
            j = 2 * i
            while j <= n:
                is_prime[j-1] = False
                j += i
    table = [ i for i in range(1, n+1) if is_prime[i-1]]
    return is_prime, table


appeared = [False] * (10**6 + 1)
primes = sieve(10**3)[1]
for a in A:
    if a == 1:
        continue
    for p in primes:
        if a % p == 0:
            if appeared[p]:
                print('setwise coprime')
                quit()
            appeared[p] = True
            while a % p == 0:
                a //= p
    
    if a != 1:
        if appeared[a]:
            print('setwize coprime')
            quit()
        
        appeared[a] = True

print('pairwise coprime')

Submission status: Wrong Answer

Solution code:
import sys
import math
import fractions
from collections import deque
from collections import defaultdict

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid(h, w, num): return [[int(num)] * w for _ in range(h)]


# Nの素因数分解を辞書で返す
def prime_fact(n, ela):
    if n == 1:
        return {1: 1}


    prime_dict = {}
    for i in ela:
        cnt = 0
        while n % i == 0:
            cnt += 1
            n = n // i
        if cnt:
            prime_dict[i] = cnt
        if n == 1:
            break
    if n != 1:
        prime_dict[n] = 1
    return prime_dict


def sieve_of_erastosthenes(num):
    input_list = [False if i % 2 == 0 or i % 3 == 0 or i % 5 == 0 else True for i in range(num)]
    input_list[0] = input_list[1] = False
    input_list[2] = input_list[3] = input_list[5] = True
    sqrt = math.sqrt(num)

    for serial in range(3, num, 2):
        if not input_list[serial]:
            continue

        if serial >= sqrt:
            return input_list

        for s in range(serial ** 2, num, serial):
            input_list[s] = False


def main():
    N = NI()
    A = NLI()
    ela = sieve_of_erastosthenes(1001)
    ela2 = [i for i, b in enumerate(ela) if b]

    if max(A) == 1:
        print("pairwise coprime")
        exit()

    g = A[0]
    for a in A:
        g = math.gcd(g, a)
    if g > 1:
        print("no coprime")
        exit()

    p_cnt = defaultdict(int)
    PD_list = defaultdict(dict)
    cnt = 0
    for a in A:
        if a == 1:
            continue

        cnt += 1
        if cnt >= 90000:
            print("not coprime")
            exit()

        if PD_list[a]:
            AP = PD_list[a]
        else:
            AP = prime_fact(a, ela2)
            PD_list[a] = AP
        for apk in AP.keys():
            p_cnt[apk] += 1

    max_p = max(p_cnt.values())
    if max_p == 1:
        print("pairwise coprime")
    elif max_p == N:
        print("not coprime")
    else:
        print("setwise coprime")



if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import math

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

def func():
    D = [x if x % 2 != 0 else 2 for x in range(Amax+1)]
    for i in range(3, Amax+1, 2):
        if i**2 > Amax:
            break
        elif D[i] != i:
            continue
        else:
            j = i*2
            while j < Amax:
                if D[j] == j:
                    D[j] = i
                j += i
    return D

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

if GCD > 1:
    print('not coprime')
else:
    D = func()
    pri = [0] * (Amax+1)
    for i in range(N):
        x, pri_set = A[i], set()
        while x != 1:
            pri_set.add(D[x])
            x //= D[x]
        for y in pri_set:
            if pri[y] > 0:
                print('setwise coprime')
                exit()
            else:
                pri[y] += 1

    print('pairwise coprime')

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
from collections import defaultdict

input = sys.stdin.readline


def ST():
    return input().rstrip()


def I():
    return int(input())


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


def LI():
    return list(MI())


N = I()
A = LI()


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


d = defaultdict(set)
for i, a in enumerate(A):
    tmp = fac(a)
    for t in tmp:
        d[t[0]].add(i)

flag = True
ans = 0
for v in d.values():
    if flag and len(v) != 1:
        flag = False
    ans = max(ans, len(v))


if flag:
    print("pairwise coprime")
elif ans != N:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Wrong Answer

Solution code:
import sys


def input():
    return sys.stdin.readline().rstrip()

def euc(a,b):

    while b!=0:
        a,b =b,a%b

    return a

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

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

    PS =set()

    current =A[0]
    for i in range(N-1):
        current =euc(current,A[i+1])
        if current ==1:
            break

    else:
        print("not coprime")
        exit()
    exit()



    for i in range(N):
        if A[i]==1:
            continue
        aa =factorization(A[i])
        for i in aa:
            if i in PS:
                print("setwise coprime")
                exit()
            else:
                PS.add(i)

    print("pairwise coprime")
    exit()



if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def resolve():
    n=int(input())
    a=sorted(list(map(int,input().split())))
    ma=a[-1]
    pn=[i for i in range(ma+1)]
    for i in range(2,ma//2+1):
      j=2
      while j*i<=ma:
        pn[j*i]=i
        j+=1
    chk=[0]*(ma+1)
    for i in a:
      if i==1:
        continue
      x=pn[i]
      chk[x]+=1
      while x!=i:
        while i%x==0:
          i//=x
        x=pn[i]
        chk[x]+=1
    ans=2
    for i in chk:
      if i==n:
        ans=0
        break
      if i>=2:
        ans=1
    if ans==2:
      print('pairwise coprime')
    elif ans==1:
      print('setwise coprime')
    else:
      print('not coprime')

if __name__ == '__main__':
    resolve()

Submission status: Wrong Answer

Solution code:
def resolve():
    import sys
    input = sys.stdin.readline
    n=int(input())
    a=sorted(list(map(int,input().split())))
    ma=a[-1]
    pn=[i for i in range(ma+1)]
    for i in range(2,ma//2+1):
      j=2
      while j*i<=ma:
        pn[j*i]=i
        j+=1
    chk=[0]*(ma+1)
    for i in a:
      if i==1:
        continue
      x=pn[i]
      chk[x]+=1
      while x!=i:
        while i%x==0:
          i//=x
        x=pn[i]
        chk[x]+=1
    ans=2
    for i in chk:
      if i==n:
        ans=0
        break
      if i>=2:
        ans=1
    if ans==2:
      print('pairwise coprime')
    elif ans==1:
      print('setwise coprime')
    else:
      print('not coprime')

if __name__ == '__main__':
    resolve()

Submission status: Wrong Answer

Solution code:
import math


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 not arr:
        arr.append(n)

    return arr


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 = [0] * (max(A)+1)
for i in range(N):
    P = set(factorization(A[i]))
    for p in P:
        X[p] += 1
        if X[p] > 1:
            is_pairwise = False
            break

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

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

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

Submission status: Wrong Answer

Solution code:
import sys
import math
from collections import defaultdict, deque, Counter
from copy import deepcopy
from bisect import bisect, bisect_right, bisect_left
from heapq import heapify, heappop, heappush
    
input = sys.stdin.readline
def RD(): return input().rstrip()
def F(): return float(input().rstrip())
def I(): return int(input().rstrip())
def MI(): return map(int, input().split())
def MF(): return map(float,input().split())
def LI(): return tuple(map(int, input().split()))
def LF(): return list(map(float,input().split()))
def Init(H, W, num): return [[num for i in range(W)] for j in range(H)]
    
    
def main():
    N = I()
    mylist = LI()
    max_num = max(mylist)
    max_num2 = round(math.sqrt(max_num))
    D = [True]* (max_num+1)
    mylist = set(mylist)
    setwise = True
    pairwise = True

    for i in range(2, max_num2+1):
        temp = 0
        if D[i]:
            for j in range(i, max_num+1, i):
                D[j] = False
                if j in mylist:
                    temp+=1
        if temp == N:
            print("not coprime")
            
            sys.exit()
        if temp >= 2:
            pairwise = False

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

            
    
    
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
import math
import fractions
from collections import deque
from collections import defaultdict

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid(h, w, num): return [[int(num)] * w for _ in range(h)]


# Nの素因数分解を辞書で返す
def prime_fact(n, ela):
    if n == 1:
        return {1: 1}


    prime_dict = {}
    for i in ela:
        cnt = 0
        while n % i == 0:
            cnt += 1
            n = n // i
        if cnt:
            prime_dict[i] = cnt
        if n == 1:
            break
    if n != 1:
        prime_dict[n] = 1
    return prime_dict


def sieve_of_erastosthenes(num):
    input_list = [False if i % 2 == 0 or i % 3 == 0 or i % 5 == 0 else True for i in range(num)]
    input_list[0] = input_list[1] = False
    input_list[2] = input_list[3] = input_list[5] = True
    sqrt = math.sqrt(num)

    for serial in range(3, num, 2):
        if not input_list[serial]:
            continue

        if serial >= sqrt:
            return input_list

        for s in range(serial ** 2, num, serial):
            input_list[s] = False


def main():
    N = NI()
    A = NLI()
    ela = sieve_of_erastosthenes(1001)
    ela2 = [i for i, b in enumerate(ela) if b]

    if max(A) == 1:
        print("pairwise coprime")
        exit()

    g = A[0]
    for a in A:
        g = fractions.gcd(g, a)
    if g > 1:
        print("no coprime")
        exit()

    p_cnt = defaultdict(int)
    PD_list = defaultdict(dict)
    cnt = 0
    for a in A:
        if a == 1:
            continue

        cnt += 1
        if cnt >= 90000:
            print("not coprime")
            exit()

        if PD_list[a]:
            AP = PD_list[a]
        else:
            AP = prime_fact(a, ela2)
            PD_list[a] = AP
        for apk in AP.keys():
            p_cnt[apk] += 1

    max_p = max(p_cnt.values())
    if max_p == 1:
        print("pairwise coprime")
    elif max_p == N:
        print("not coprime")
    else:
        print("setwise coprime")



if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from math import gcd


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

# setwise validation
tmp = 0
for a in A:
    tmp = gcd(tmp, a)
isSetwise = (tmp == 1)


# pairwise validation
# M = 10 ** 6
# A = set(A)
# isPairwise = True
# for i in range(2, M):
#     cnt = 0
#     ni = 0
#     while ni <= M:
#         cnt += (ni in A)
#         ni += i
#     isPairwise &= (cnt <= 1)
M = 10 ** 6
sieve = [0] * (M + 1)
for a in A:
    sieve[a] = 1

cnt = 0
for i in range(2, M + 1):
    cnt = max(cnt, sum(sieve[j] == 1 for j in range(i, M + 1, i)))
isPairwise = (cnt <= 1)

# check
if isPairwise:
    ans = 'pairwise coprime'
elif isSetwise:
    ans = 'setwise coprime'
else:
    ans = 'not coprime'
print(ans)

Submission status: Wrong Answer

Solution code:
from math import gcd


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

# setwise validation
tmp = 0
for a in A:
    tmp = gcd(tmp, a)
isSetwise = (tmp == 1)


# pairwise validation
# M = 10 ** 6
# A = set(A)
# isPairwise = True
# for i in range(2, M):
#     cnt = 0
#     ni = 0
#     while ni <= M:
#         cnt += (ni in A)
#         ni += i
#     isPairwise &= (cnt <= 1)
M = 10 ** 6
sieve = [0] * (M + 1)
for a in A:
    sieve[a] = 1

cnt = 0
for i in range(2, M):
    cnt = max(cnt, sum(sieve[j] == 1 for j in range(i, M + 1, i)))
isPairwise = (cnt <= 1)

# check
if isPairwise:
    ans = 'pairwise coprime'
elif isSetwise:
    ans = 'setwise coprime'
else:
    ans = 'not coprime'
print(ans)

Submission status: Wrong Answer

Solution code:
n,a=int(input()),list(map(int,input().split()))
g=0
from math import gcd
for i in a:g=gcd(i,g)
if g!=1:print("not coprime")
else:

    primes=list(range(10**6))
    primes[0]=primes[1]=0
    for i in range(2,10**6):
        if primes[i]==i:
            for j in range(2*i,10**6,i):primes[j]=i
    ps=set()
    for x in a:
        while x !=1:
            t=primes[x]
            if t in ps:print("setwise coprime");exit()
            ps.add(t)
            x//=t
    print("pairwise coprime")

Submission status: Wrong Answer

Solution code:
import sys
N = int(input())
A = set(map(int, input().split())) #Aの分布を集合として表記
MAX = 10**6

for p in range(2,MAX+1):
  ct = 0 #pの倍数の個数を数える
  for q in range(p,MAX+1,p): #qはpの倍数全てを走る
    if q in A:
      ct += 1
  
  #ct = Nのとき、pばすべてのA_nの約数。つまり、Aはnot coprime
  if ct == N:
    print("not coprime")
    sys.exit()
  
  #2 <= ct < Nのとき、pばいくつかのA_nの約数。つまり、Aはsetwise coprime
  elif ct >= 2:
    print("setwise coprime")
    sys.exit()
  
  # ct <= 1のとき、pはどの２つのA_nの公約数にも一致しない。次のpを調べる必要あり。
  #else: continue
  
  
#途中で終わらない場合、1より大きな公約数は存在しないことがわかる。
print("pairwise coprime")

Submission status: Wrong Answer

Solution code:
# pypy
from math import gcd

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

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

if g_all > 1:
    print('not coprime')
    quit()

def sieve(n):
    is_prime = [True for _ in range(n+1)]
    is_prime[0] = False
    for i in range(2, n+1):
        if is_prime[i-1]:
            j = 2 * i
            while j <= n:
                is_prime[j-1] = False
                j += i
    table = [ i for i in range(1, n+1) if is_prime[i-1]]
    return is_prime, table


appeared = [False] * (10**6 + 1)
primes = sieve(10**3)[1]
for a in A:
    for p in primes:
        if a % p == 0:
            if appeared[p]:
                print('setwise coprime')
                quit()
            appeared[p] = True
            while a % p == 0:
                a //= p
    
    if a != 1:
        if appeared[a]:
            print('setwize coprime')
            quit()
        
        appeared[a] = True

print('pairwise coprime')

Submission status: Wrong Answer

Solution code:
import numpy as np
from numba import njit


n = int(input())
arr = np.array(list(map(int, input().split())))


n = 10**3 + 1
primes = set(range(3, n+1, 2))

for i in range(3, int(n**0.5+1)):
    primes.difference_update(range(i*2, n+1, i))
primes.add(2)
primes = list(primes)
primes.sort()


@njit
def solve(arr, primes):
    used = [False] * 1002
    ans = True
    flg = False
    for x in arr:
        for p in primes:
            while x > 1 and x % p == 0:
                if used[p]:
                    ans = False
                    flg = True
                    break
                while x % p == 0:
                    x //= p
                used[p] = True
            if flg:
                break
        if flg:
            break
    return ans


ans1 = solve(arr, primes)
ans2 = np.gcd.reduce(arr) == 1

if ans1 and ans2:
    print("pairwise coprime")
elif ans2:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Wrong Answer

Solution code:
import sys
N = int(input())
A = set(map(int, input().split())) #Aの分布を集合として表記
MAX = 10**6

for p in range(2,N):
  ct = 0 #pの倍数の個数を求める
  for q in range(p,MAX+1,p): #qはpの倍数全てを走る
    if q in A:
      ct += 1
  
  #ct = Nのとき、pばすべてのA_nの約数。つまり、Aはnot coprime
  if ct == N:
    print("not coprime")
    sys.exit()
  
  #2 <= ct < Nのとき、pばいくつかのA_nの約数。つまり、Aはsetwise coprime
  elif ct >= 2:
    print("setwise coprime")
    sys.exit()
  
  # ct <= 1のとき、pはどの２つのA_nの公約数にも一致しない。次のpを調べる必要あり。
  #else: continue
  
  
#途中で終わらない場合、1より大きな公約数は存在しないことがわかる。
print("pairwise coprime")

Submission status: Wrong Answer

Solution code:
import numpy as np
import sys
from collections import defaultdict


def first_prime_list(N):
    D = [1] * (N + 1)

    for i in range(2, N + 1):
        if D[i] != 1:
            continue
        for j in range(1, N // i + 1):
            if D[i * j] == 1:
                D[i * j] = i

    return D


def factorization_with_fpl(A, D):

    Ps = defaultdict(int)
    current_p = D[A]

    while D[A] > 1:
        cnt = 0
        while D[A] == current_p:
            A = A // D[A]
            cnt += 1

        Ps[current_p] = cnt
        current_p = D[A]

    if A != 1:
        Ps[A] = 1

    return Ps


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

D = first_prime_list(max(A))

pc = True
sp = True

maxlist = factorization_with_fpl(A[0], D)
minlist = factorization_with_fpl(A[0], D)

arrA = np.array(A)

for i in range(1, N):
    d = factorization_with_fpl(A[i], D)
    for p in maxlist.keys():
        if min(maxlist[p], d[p]) != 0:
            pc = False
        maxlist[p] = max(maxlist[p], d[p])
        minlist[p] = min(minlist[p], d[p])


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


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

Submission status: Wrong Answer

Solution code:
ma = lambda :map(int,input().split())
lma = lambda :list(map(int,input().split()))
tma = lambda :tuple(map(int,input().split()))
ni = lambda:int(input())
yn = lambda fl:print("Yes") if fl else print("No")
import collections
import math
def is_primes(n):
    primes = [1]*n
    primes[0] =0
    primes[1] =0
    for i in range(2,int(n**0.5)+1):
        if primes[i] ==1:
            for j in range(2*i,n,i):
                primes[j] = 0
    return primes

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

n =ni()
A = lma()
if max(A)==1:
    print("pairwise coprime")
mx= 10**6+10
prms = is_primes(mx)
prms2=[i for i in range(mx) if prms[i]==1]
d=collections.Counter()
for a in A:
    fct = factorize(a,prms2)
    #print(fct)
    for fc,cnt in fct:
        d[fc]+=1
        if d[fc]==n:
            break
f1=True # pp or sp
f2=True # sp or other
for num,cnt in d.items():
    if cnt==n:
        f2=False #other
        break
    else:
        if cnt==1:
            pass
        else:
            f1=False
            break
if f2==False:
    print("not coprime")
elif f1 and f2:
    print("pairwise coprime")
elif f1==False:
    print("setwise 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:
        ret = checker[checker[x]] >= 0
        y = x // checker[x]
        ret = ret and check_by_eratosthenes(y, checker)
        checker[checker[x]] = -1
        return ret
        

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 numpy as np

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

#if np.lcm.reduce(a)==np.prod(a):
#    print("pairwise coprime")
#elif np.gcd.reduce(a)==1:
#    print("setwise coprime")
#else:
#    print("not coprime")

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

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

Submission status: Wrong Answer

Solution code:
import math
from functools import reduce

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

    

    


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

def gcd_list(numbers):
    return reduce(math.gcd, numbers)
S=[]
tmp=gcd_list(T)
if tmp!=1:
    print("not coprime")
else:
    T.sort()
    S=[]
    n=10**6+1
    isprime=[True]*(n+1)
    isprime[0]=False
    isprime[1]=False
    for i in range(len(T)):
        if isprime[T[i]]==True:
            j=T[i]+T[i]
            while j<=n:
                 
                isprime[j] =False
                j=j+T[i]
                
                    
        else:
            print("setwise coprime")
            exit()
    print("pairwise coprime")

Submission status: Wrong Answer

Solution code:
import sys
import math
from collections import deque
from collections import defaultdict

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid(h, w, num): return [[int(num)] * w for _ in range(h)]


# Nの素因数分解を辞書で返す
def prime_fact(n, ela, ela2):
    if n == 1:
        return {1: 1}


    prime_dict = {}
    for i in ela2:
        cnt = 0
        while n % i == 0:
            cnt += 1
            n = n // i
        if cnt:
            prime_dict[i] = cnt
        if n == 1:
            break
    if n != 1:
        prime_dict[n] = 1
    return prime_dict


def sieve_of_erastosthenes(num):
    input_list = [False if i % 2 == 0 or i % 3 == 0 or i % 5 == 0 else True for i in range(num)]
    input_list[0] = input_list[1] = False
    input_list[2] = input_list[3] = input_list[5] = True
    sqrt = math.sqrt(num)

    for serial in range(3, num, 2):
        if not input_list[serial]:
            continue

        if serial >= sqrt:
            return input_list

        for s in range(serial ** 2, num, serial):
            input_list[s] = False


def main():
    N = NI()
    A = NLI()
    ela = sieve_of_erastosthenes(1001)
    ela2 = [i for i, b in enumerate(ela) if b]

    if max(A) == 1:
        print("pairwise coprime")
        exit()


    p_cnt = defaultdict(int)
    PD_list = defaultdict(dict)
    cnt = 0
    for a in A:
        if a == 1:
            continue

        cnt += 1
        if cnt >= 90000:
            print("not coprime")
            exit()

        if PD_list[a]:
            AP = PD_list[a]
        else:
            AP = prime_fact(a, ela, ela2)
            PD_list[a] = AP
        for apk in AP.keys():
            p_cnt[apk] += 1

    max_p = max(p_cnt.values())
    if max_p == 1:
        print("pairwise coprime")
    elif max_p == N:
        print("not coprime")
    else:
        print("setwise coprime")



if __name__ == "__main__":
    main()