Problem: 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.

Submission attempts (in order):
import sys
sys.setrecursionlimit(10 ** 9)
# input = sys.stdin.readline    ####
def int1(x): return int(x) - 1
def II(): return int(input())
def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())
def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def MS(): return input().split()
def LS(): return list(input())
def LLS(rows_number): return [LS() for _ in range(rows_number)]
def printlist(lst, k=' '): print(k.join(list(map(str, lst))))
INF = float('inf')
# from math import ceil, floor, log2
from collections import deque, defaultdict
# from itertools import combinations as comb, combinations_with_replacement as comb_w, accumulate, product, permutations
# from heapq import heapify, heappop, heappush
# import numpy as np    # cumsum


from math import gcd

def solve():
    N = II()
    A = LI()
    
    mx = 1000003
    D = [1] * mx
    for i in range(2, mx):
        if D[i] != 1:
            continue
        for j in range(i, mx, i):
            if D[j] == 1:
                D[j] = i
    # print(D)
    # print(D[4], D[6], D[35])

    g = A[0]
    dct = defaultdict(int)
    flag = True
    for a in A:
        g = gcd(g, a)
        # print(a, D[a])
        if D[a] != 1:
            if dct[D[a]] > 0:
                flag = False
            dct[D[a]] += 1
    # print(dct, flag, g)
    flag = False
    if g == 1:
        if flag:
            print('pairwise coprime')
        else:
            print('setwise coprime')
    else:
        print('not coprime')


if __name__ == '__main__':
    solve()



import sys
sys.setrecursionlimit(10 ** 9)
# input = sys.stdin.readline    ####
def int1(x): return int(x) - 1
def II(): return int(input())
def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())
def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def MS(): return input().split()
def LS(): return list(input())
def LLS(rows_number): return [LS() for _ in range(rows_number)]
def printlist(lst, k=' '): print(k.join(list(map(str, lst))))
INF = float('inf')
# from math import ceil, floor, log2
from collections import deque, defaultdict
# from itertools import combinations as comb, combinations_with_replacement as comb_w, accumulate, product, permutations
# from heapq import heapify, heappop, heappush
# import numpy as np    # cumsum


from math import gcd

def solve():
    N = II()
    A = LI()
    
    mx = 1000003
    D = [1] * mx
    for i in range(2, len(D)):
        # if D[i] != 1:
        #     continue
        for j in range(i, len(D), i):
            if D[j] == 1:
                D[j] = i
    # print(D[mx-3])
    # print(D[4], D[6], D[35])

    g = A[0]
    
    
    C = [0] * mx
    for a in A:
        g = gcd(g, a)
        # print(a, D[a])
        # if D[a] != 1:
        
        
        #     dct[D[a]] += 1
        d = D[a]
        C[d] += 1
    # print(dct, flag, g)
    
    if all(C[i] <= 1 for i in range(2, len(C))):
        flag = True
    else:
        flag = False

    if g == 1:
        if flag:
            print('pairwise coprime')
        else:
            print('setwise coprime')
    else:
        print('not coprime')


if __name__ == '__main__':
    solve()



import sys
sys.setrecursionlimit(10 ** 9)
# input = sys.stdin.readline    ####
def int1(x): return int(x) - 1
def II(): return int(input())
def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())
def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def MS(): return input().split()
def LS(): return list(input())
def LLS(rows_number): return [LS() for _ in range(rows_number)]
def printlist(lst, k=' '): print(k.join(list(map(str, lst))))
INF = float('inf')
# from math import ceil, floor, log2
from collections import deque, defaultdict
# from itertools import combinations as comb, combinations_with_replacement as comb_w, accumulate, product, permutations
# from heapq import heapify, heappop, heappush
# import numpy as np    # cumsum


from math import gcd

def solve():
    N = II()
    A = LI()
    
    mx = 1000003
    D = [1] * mx
    for i in range(2, len(D)):
        if D[i] != 1:
            continue
        for j in range(i, len(D), i):
            if D[j] == 1:
                D[j] = i

    
    #     d = D[x]
    
    #     while x != d:
    #         x = x // d
    #         d = D[x]
    
    
    

    g = A[0]
    dct = defaultdict(int)
    flag = True
    for a in A:
        g = gcd(g, a)
        # print(a, D[a])
        # if D[a] != 1:
        
        
        #     dct[D[a]] += 1
        
        d = D[a]
        p = a
        
        while p != d:
            p = p // d
            d = D[p]

        if p != 1:
            dct[p] += 1
            if dct[p] > 1:
                flag = False

    if g == 1:
        if flag:
            print('pairwise coprime')
        else:
            print('setwise coprime')
    else:
        print('not coprime')


if __name__ == '__main__':
    solve()



Verdicts: Wrong Answer

Wrong Answer

Accepted