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

read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
MOD = 10 ** 9 + 7


def main():
    N = int(readline())
    if N>78498:
        print('setwise coprime')
        sys.exit()
    A = list(map(int, readline().split()))
    setwise = True
    pairwise = True
    primes = [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]
    for p in primes:
        if not setwise and not pairwise:
            break
        tmp = 0
        for a in A:
            if a % p == 0:
                tmp += 1
        if tmp >=2:
            pairwise = False
            if tmp == N:
                setwise = False
        else:
            continue

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


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import math

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

flag = 0
pairw = 0
setw = a[n-1]

for i in range(n-1):
    pairw = math.gcd(a[i],a[i+1])
    setw = math.gcd(setw,a[i])
    if pairw != 1:
        flag = 1

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

Submission status: Wrong Answer

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

import math
from functools import reduce

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

def sieve_of_eratosthenes(n): 
    candidate = [i for i in range(2, n+1)] 
    prime = []
    limit = math.sqrt(n) + 1 

    while True:
        p = min(candidate) 
        if limit <= p:
            prime.extend(candidate) 
            break
        prime.append(p) 

        candidate = [i for i in candidate if i % p != 0]

    return prime

prime = sieve_of_eratosthenes(10**3+1)
g = gcd_list(A)
if g != 1: print('not coprime');exit();

for p in prime:
  cnt = 0
  for a in A:
    if a%p == 0: cnt += 1
    if cnt == 2:
      print('setwise coprime')
      exit()
print('pairwise coprime')

Submission status: Wrong Answer

Solution code:
import math
from functools import reduce

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

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 list_check(list1, list2):
    for i in list1:
        if i in list2:
            return True
    return False
    # return set(list1).issubset(list2)

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

so_list = []
no_pairwise = False
no_setwise = False
for a in A:
    fac_list = factorization(a)
    # print(fac_list, so_list, no_pairwise)
    if list_check(fac_list, so_list):
        no_pairwise = True
        break
    else:
        so_list.extend(factorization(a))

if gcd_list(A) != 1:
    no_setwise = True

if not no_pairwise:
    print("pairwise coprime")
elif not no_setwise:
    print("setwise coprime")
else:
    print("not coprime")

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())
# a = [999983] * 100 + [1]
a = list(map(int,input().split()))
a = [1] * (1 in a) + [i for i in a if i != 1]
# print(a)
n = len(a)

f = 1
if n>80000:
    # print("not coprime")
    # exit()
    f = 0
g = 0
c1 = 0
if len(set(a)) != n:
    f = 0
for i in a:
    g = gcd(g,i)
    if f == 1:
        for j in p:
            if i%j == 0:
                c[j] += 1
                if c[j] > 1:
                    f = 0
if g == 1:
    if f == 1:
        print("pairwise coprime")
    else:
        print("setwise coprime")
else:
    print("not coprime")
# print(a,g,f)

Submission status: Wrong Answer

Solution code:
import sys
import math
import collections
import bisect
import itertools
import decimal

# import numpy as np

# sys.setrecursionlimit(10 ** 6)
INF = 10 ** 20
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline().rstrip())
ns = lambda: map(int, sys.stdin.readline().rstrip().split())
na = lambda: list(map(int, sys.stdin.readline().rstrip().split()))
na1 = lambda: list(map(lambda x: int(x) - 1, sys.stdin.readline().rstrip().split()))


# ===CODE===
# N以下の素数列挙
def make_prime_nums(n):
    prime_nums = [2 if n >= 2 else None]
    for i in range(3, n + 1):
        for p in prime_nums:
            if p >= int(i ** (1 / 2)) + 1:
                prime_nums.append(i)
                break
            if i % p == 0:
                break
    return prime_nums


def main():
    n = ni()
    a = na()

    prime = make_prime_nums(10 ** 3)

    pc = True
    tc = True

    for pi in prime:
        cnt = 0
        for i in range(n):
            flg = False
            if a[i] % pi == 0:
                cnt += 1
        if cnt > 1:
            pc = False
        if cnt == n:
            tc = False
            break

    ca = collections.Counter(a)
    for k, v in ca.items():
        if k > 1:
            if ca[k] > 1:
                pc = False
            if ca[k] == n:
                tc = False
                break

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


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import math
n = int(input())
a = list(map(int,input().split()))
s = [0]*(10**6+1)
t = [0]*169
u = [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, 1009]
v = 0
m = 169
for i in range(n):
    for j in range(m):
        if(a[i]%u[j] == 0):
            t[j] += 1
            while(a[i]%u[j] == 0):
                a[i] //= u[j]
            if(a[i] == 1):
                break
    if(a[i] != 1):
        s[a[i]] += 1
        v += 1
if(max(t) == n):
    print('not coprime')
elif(max(t) <= 1):
    z = 0
    if(v > 0):
        if(max(s) <= 1):
            print('pairwise coprime')
        else:
            print('setwise coprime')    
    else:
        print('setwise coprime')
else:
    print('setwise coprime')

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
N = int(input())
a = list(map(int, input().split()))

am = int(max(a)**0.5)+1

memo = [1] * (am+1)
memo[0] = 0
memo[1] = 0

p = -1
g = a[0]
d = defaultdict(int)

for ai in range(2, am+1):
    if ai == p:
        memo[ai] = 0
        continue
    for j in range(2, am // ai + 1):
        memo[ai * j] = 0
    p = ai

cs = []
for i, memoi in enumerate(memo):
    if memoi:
        cs.append(i)

# print(cs)

def make_divisors(n):
    global d



f1 = 1
f2 = 1

for ai in a:
    lim = int(ai**0.5)+1
    f0 = 0
    for i in cs:
        if i >= lim:
            break
        if ai % i == 0:
            d[i] += 1
            if i != ai // i:
                d[ai//i] += 1
            if d[i] > 1 or d[ai//i] > 1:
                f1 = 0
            if d[i] == N or d[ai//i] == N:
                f2 = 0
                break

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

Submission status: Wrong Answer

Solution code:
import math
n=int(input())
a=list(map(int,input().split()))
mxa=max(a)

            
def fact(num):
    arr = []
    temp = num
    for i in range(2, int(-(-num**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(num)
    return arr

flg=True
flg2=False
table=[0]*(mxa+1)
for (i,x) in zip(a,range(len(a))):
  fc=fact(i)
  for j in fc:
    if table[j]==1:
      flg=False
    table[j]+=1
  if not flg and x not in table:
    flg2=True
    break
if flg:
  print("pairwise coprime")
elif flg2:
  print("not coprime")
else:
  print("setwise coprime")

Submission status: Wrong Answer

Solution code:
import math
#素数列挙
def get_primes(limit):
    A = [i for i in range(2, limit+1)]
    P = []
    time = 0
    
    while True:
        prime = min(A)
        
        if prime > math.sqrt(limit):
            break
            
        P.append(prime)
            
        A = [i for i in A if i%prime!=0]

    P.extend(A)
          
    return P


def resolve():
    N = int(input())
    A = list(map(int,input().split()))
    sosus = set(get_primes(max(A)+1))
    dvd = set()



    val = A[0]
    for i in A:
        val = math.gcd(i,val)

    if val ==1:
        pass
    else:
        print('not coprime')
        return

    for i in A:
        tmp=[]
        for j in sosus:
            if j<i:
                break
            if i % j ==0:
                tmp.append(j)
                while i % j ==0:
                    i //=j
            if i ==1:
                break
        sosus.difference_update(tmp)
        
        if i != 1:
            break
    else:
        print('pairwise coprime')
        return

    print('setwise coprime')

resolve()

Submission status: Wrong Answer

Solution code:
"""nを素因数分解"""
"""2以上の整数n => [[素因数, 指数], ...]の2次元リスト"""

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 len(arr) == 0:
        arr.add(n)

    return arr


n = int(input())
a = list(map(int,input().split()))
ans = "pairwise coprime"
yakusu = []

for i in range(n):
    arr = factorization(a[i])
    yakusu.append(arr)

for i in range(n-1):
    for j in range(i+1,n):
        s1 = yakusu[i] & yakusu[j]
        if len(s1) != 0:
            ans = "setwise coprime"
            break

s2 = yakusu[0]

for i in range(1,n):
    s2 = s2 & yakusu[i]

if len(s2) != 0:
    ans = "not coprime"

print(ans)

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]]
n = int(input())
a = list(map(int, input().split()))
b = a[0]
c = 0
d = [0]*(10**6+1)
for i in range(1, n):
    b = gcd(b, a[i])
for i in range(n):
    d[a[i]] += 1
    if d[a[i]] == 2:
        c = 1
        break
if b != 1: print("not coprime")
elif c == 1: print("setwise coprime")
else:
    data = primes(1000)
    count = [0]*(len(data))
    d = 0
    for j in range(len(data)):
        for i in range(n):
            if a[i] >= data[j]*2 and 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:
N = int(input())
a = [int(x) for x in input().split()]
import math
b = 0
if N <= 10000:
    for i in range(N-1):
        for j in range(i+1,N):
            m = math.gcd(a[i],a[j])
            if m != 1:
                b = 1
    if b == 0:
        print("pairwise coprime")
        exit()
ans = a[0]
for i in range(1,N):
    ans = math.gcd(ans,a[i])
if ans == 1:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
A.sort()
m = A[0]
R = int(A[-1]**0.5)

is_pairwise_coprime = True
is_setwise_coprime = True
checked = [0]*(R+1)
l = 0
for i in range(2, R+1):
    if checked[i]:
        continue
    
    while A[l] < i:
        l += 1
    
    if l == N-1:
        break
    
    tmp = 0
    for j in range(l, N):
        if A[j]%i == 0:
            tmp += 1
        if tmp > 1:
            is_pairwise_coprime = False

    if tmp == N:
        is_setwise_coprime = False
    
    if is_setwise_coprime == False:
        break
    
    n = i
    while n < R+1:
        checked[n] = 1
        n += i
    # print(checked, l)
if is_pairwise_coprime:
    print('pairwise coprime')
elif is_setwise_coprime:
    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):
                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
        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
for i in range(n):
    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()))
a.sort()
b=[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]
B=len(b)
s=0
for i in range(B):
    t=0
    for j in range(n):
        if a[j]%b[i]!=0:
            t+=1
            break
    if t==0:
        s+=1
        break
S=0
for i in range(B):
    T=0
    for j in range(n):
        if a[j]%b[i]==0:
            T+=1
            if T>=2:
                break
    if T>=2:
        S+=1
        break
if s==1:
    print("not coprime")
elif S==1:
    print("setwise coprime")
else:
    print("pairwise coprime")

Submission status: Wrong Answer

Solution code:
from math import *
n,*a=map(int,open(0).read().split())
a.sort()
b=0
for i,j in zip(a,a[1:]):
    if gcd(i,j)==1:
        b+=1
if b==n-1:print("pairwise coprime");exit()
c=a[0]
for i in a:
    c=gcd(c,i)
    if c==1:print("setwise coprime");exit()
print("not coprime")

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
from collections import defaultdict
def main():
    n, *a = map(int, read().split())

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

    if 1 in a:
        print('not coprime')
        sys.exit()
    d1 = defaultdict(int)
    for ae in a:
        t1 = factorization(ae)
        for t1e in t1:
            d1[t1e[0]] += 1

    d1v = tuple(d1.values())
    if max(d1v) == n:
        print('not coprime')
    elif all([i == 1 for i in d1v]):
        print('pairwise coprime')
    else:
        print('setwise coprime')
    #print(d1)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import math

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

ans = "not coprime"

a, b = als[1], als[0]
if a < b:
    tmp = b
    b = a
    a = tmp 
while a % b != 0:
    a, b = b, a % b

for i in range(2, n):
    a = als[i]
    if a < b:
        tmp = b
        b = a
        a = tmp 
    while a % b != 0:
        a, b = b, a % b
    if b == 1:
        ans = "setwise coprime"
        break

existeven = False

failed = False

for i in range(n):
    if als[i] >= 2 and als[i]%2 == 0:
        if existeven:
            failed = True
            break
        else:
            existeven = True

maxa = max(als)

if not failed:
    for i in range(3, int(math.sqrt(maxa))+1, 2):
        existfactrial = False
        failed = False
        for j in range(n):
            if als[j] >= i and als[j]%i == 0:
                if existfactrial:
                    failed = True
                    break
                else:
                    existfactrial = True
        if failed:
            break
    if not failed:
        ans = "pairwise coprime"

print(ans)

Submission status: Wrong Answer

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

def GCM(y, x):
  buf = y%x
  if buf==0:
    return x
  else:
    return GCM(x, buf)

A.sort()
maxA = A[-1]
for i in range(2,N+1):
  maxA %= A[-i]
  if maxA == 0:
    maxA = A[-i]
if GCM(A[0], maxA)>1:
  print("not coprime")
else:
  count = 0
  flag=False
  for i in range(N-1):
    for j in range(i+1,N):
      count += 1
      if count > 2000000:
        break
      if GCM(A[-(i+1)],A[-(j+1)]) != 1:
        flag=True
        break
  if flag:
    print("setwise coprime")
  else:
    print("pairwise coprime")

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
MAX= 10**6

from math import gcd
g = A[0]
# g_list = [A[0]]
for i in range(1, N):
    g = gcd(g, A[i])
    # g_list.append(g)
if g != 1:
    print("not coprime")
    exit()
else:
    A = [a for a in A if a != 1]
    n_primes = 78498
    if N > n_primes:
        print("setwise coprime")
        exit()
    else:
        def makePrimeChecker(n):
            """
            エラトステネスの篩.
            nまでの自然数が素数かどうかを表すリストを返す.
            """
            isPrime = [True] * (n + 1)
            isPrime[0] = False
            isPrime[1] = False
            for i in range(2, int(n ** 0.5) + 1):
                if isPrime[i]:
                    for j in range(i * i, n + 1, i):
                        isPrime[j] = False
            return isPrime

        is_prime = makePrimeChecker(MAX)
        is_ok = 1
        used_prime = [0]*(MAX+1)
        primes = [n for n in range(2, MAX+1) if is_prime[n]]
        for p in primes:
            for a in A:
                if a % p == 0:
                    if used_prime[p]:
                        is_ok = 0
                        break
                    used_prime[p] = 1
            if not is_ok:
                break
        if is_ok:
            print("pairwise coprime")
        else:
            print("setwise coprime")

Submission status: Wrong Answer

Solution code:
import math
from functools import reduce

def gcd_lis(num_lis):
    return reduce(math.gcd, num_lis)

N = int(input())
lis = list(map(int, input().split()))
c1 = True
c2 = True
for i in range(N-1):
  for j in range(i+1, N):
    if math.gcd(lis[i], lis[j]) != 1:
      c1 = False

if gcd_lis(lis) != 1:
  c2 = False

if c1 and not c2:
  print("pairwise coprime")
if not c1 and c2:
  print("setwise coprime")
if not c1 and not c2:
  print("not coprime")

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
import collections
from math import gcd
from functools import reduce

from random import randint

def find_gcd(list):
    x = reduce(gcd, list)
    return x

def solve(N: int, A: "List[int]"):



    # q2 = True
    # for a in A:
    #     for b in A:
    #         if a!=b and gcd(a, b) != 1:
    #             q2 = False
    #             break

    q1 = reduce(gcd, A) == 1
    q2 = True

    if q1 and q2:
        print('pairwise coprime')
    elif q1:
        print('setwise coprime')
    else:
        print('not coprime')
    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"

    solve(N, A)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict


def factorization(n):

    arr = defaultdict(int)
    tmp = n
    for i in range(2, int(-(-n**0.5 // 1)) + 1):  # sqrt(n) まで

        # i で割れるだけ割る、を繰り返す
        if tmp % i == 0:
            cnt = 0

            while tmp % i == 0:
                cnt += 1
                tmp //= i

            arr[i] = cnt  # 結果を追加

    if tmp != 1:
        arr[tmp] = 1  # まだ余っていれば追加しておく

    # if arr == {}:
    #    arr[n] = 1  # このブロック、必要か？

    return arr


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


pc = True
sp = True

maxlist = factorization(A[0])
minlist = factorization(A[0])

for i in range(1, N):
    d = factorization(A[i])
    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:
from collections import Counter
N = int(input())
A = list(set((map(int, input().split()))))
N = len(A)

pc = True
gg = False
cnt = Counter()

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

for a in factorization(A[0]):
    if a > 1:
        cnt[a] = 1

for i in range(1, N):
    for a in factorization(A[i]):
        if cnt[a] >= 1:
            pc = False
        if a > 1:
            cnt[a] += 1

if pc:
    print("pairwise coprime")
elif cnt.most_common(1)[0][1] < N:
    print("setwise coprime")
else:
    print("not 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, n):
                        if a[i] != a[j]:
                                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:
# Date [ 2020-08-29 21:59:01 ]
# Problem [ e.py ]
# Author Koki_tkg

import sys
# import math
# import bisect
# import numpy as np
# from decimal import Decimal
# from numba import njit, i8, u1, b1 #JIT compiler
# from itertools import combinations, product
# from collections import Counter, deque, defaultdict

# sys.setrecursionlimit(10 ** 6)
MOD = 10 ** 9 + 7
INF = 10 ** 9
PI = 3.14159265358979323846

def read_str():      return sys.stdin.readline().strip()
def read_int():      return int(sys.stdin.readline().strip())
def read_ints():     return map(int, sys.stdin.readline().strip().split())
def read_ints2(x):   return map(lambda num: int(num) - x, sys.stdin.readline().strip().split())
def read_str_list(): return list(sys.stdin.readline().strip().split())
def read_int_list(): return list(map(int, sys.stdin.readline().strip().split()))
def GCD(a: int, b: int) -> int: return b if a%b==0 else GCD(b, a%b)
def LCM(a: int, b: int) -> int: return (a * b) // GCD(a, b)

class PrimeFactorization():
    def __init__(self, n):
        self.n = n
        self.prime = [2]
        self.data = [i for i in range(3, self.n+1, 2)]

    def eratosthenes(self):
        p = self.data[0]
        while p*p <= self.n:
            p = self.data[0]
            self.prime.append(p)
            self.data = [e for e in self.data if e % p != 0]
        
        return self.prime + self.data

def Main():
    n = read_int()
    a = read_int_list()
    a.sort()
    if a[-1] < 3:
        prime = [2]
    else:
        p = PrimeFactorization(a[-1])
        prime = p.eratosthenes()
    
    cnt = 0
    for i in range(n):
        if a[i] % 2 == 1:
            cnt += 1
    
    length = len(set(a))
    aa = set(a) & set(prime)
    if set(a) == aa:
        print('pairwise coprime')
    elif length - 1 == len(aa):
        if len(set(a + prime) ^ set(prime)) == 1:
            print('pairwise coprime')
        else:
            print('setwise coprime')
    else:
        if len(aa) > 0 or cnt > 0:
            print('setwise coprime')
        else:
            print('not coprime')

                


if __name__ == '__main__':
    Main()

Submission status: Wrong Answer

Solution code:
def SieveEratosthenes(N):
    PrimeCand = [True if T>=2 else False for T in range(N+1)]
    for I in range(2,N+1):
        if I*I>N:
            break
        if PrimeCand[I]:
            for J in range(2*I,N+1,I):
                PrimeCand[J] = False
    Prime = [I for I in range(1,N+1) if PrimeCand[I]]
    return Prime

N = int(input())
A = [int(T) for T in input().split()]
if len(set(A))!=len(A):
    print('not coprime')
else:
    SeFlag = False
    NoFlag = False
    for SN in SieveEratosthenes(50000):
        Sum = sum(True if TA%SN==0 else False for TA in A)
        if Sum==len(A):
            SeFlag = False
            NoFlag = True
            break
        if Sum>=2:
            SeFlag = True
            NoFlag = False     
    if NoFlag:
        print('not coprime')
    elif SeFlag:
        print('setwise coprime')
    else:
        print('pairwise 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 itertools
import random
def factorize(n):
    b = 2
    fct = []
    while b * b <= n:
        cnt =0
        while n % b == 0:
            n //= b
            cnt +=1
        if cnt >=1:
            fct.append((b,cnt))
        b = b + 1
    if n > 1:
        fct.append((n,1))
    return fct
def solve():
    n = ni()
    A = lma()
    d=collections.Counter()
    r = random.random()
    if n==10**6:
        if r<0.3:
            print("setwise coprime")
            exit()
        elif 0.3<r<0.6:
            print("pairwise coprime")
            exit()
    for i in range(n):
        a = A[i]
        fct = factorize(a)
        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
    if f2==False:
        print("not coprime")
        exit()
    elif f1 and f2:
        print("pairwise coprime")
    elif f1==False:
        print("setwise coprime")
solve()