Problem:


Score : 500 points

Problem Statement

We have N integers. The i-th number is A_i.

\{A_i\} is said to be pairwise coprime when GCD(A_i,A_j)=1 holds for every pair (i, j) such that 1\leq i < j \leq N.

\{A_i\} is said to be setwise coprime when \{A_i\} is not pairwise coprime but GCD(A_1,\ldots,A_N)=1.

Determine if \{A_i\} is pairwise coprime, setwise coprime, or neither.

Here, GCD(\ldots) denotes greatest common divisor.

Constraints

2 \leq N \leq 10^6

1 \leq A_i\leq 10^6

Input

Input is given from Standard Input in the following format:

N
A_1 \ldots A_N

Output

If \{A_i\} is pairwise coprime, print pairwise coprime; if \{A_i\} is setwise coprime, print setwise coprime; if neither, print not coprime.

Sample Input 1

3
3 4 5

Sample Output 1

pairwise coprime

GCD(3,4)=GCD(3,5)=GCD(4,5)=1, so they are pairwise coprime.

Sample Input 2

3
6 10 15

Sample Output 2

setwise coprime

Since GCD(6,10)=2, they are not pairwise coprime. However, since GCD(6,10,15)=1, they are setwise coprime.

Sample Input 3

3
6 10 16

Sample Output 3

not coprime

GCD(6,10,16)=2, so they are neither pairwise coprime nor setwise coprime.



Sample input:
3
3 4 5


Sample output:
pairwise coprime

Submission status: Wrong Answer

Solution code:
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter,defaultdict
from operator import mul
import copy
# ! /usr/bin/env python
# -*- coding: utf-8 -*-
import heapq
sys.setrecursionlimit(10**6)
# INF =  float("inf")
INF = 10**18
import bisect
import statistics
mod = 10**9+7
# mod = 998244353

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

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

B = set()
count = 0
sc = 1
flag = 0
sc_flag = 0

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

    if f[0][0] != 1:
        if flag == 0:
            C = set()
            for ff in f:
                C.add(ff[0])
            flag = 1
        for ff in f:
            B.add(ff[0])
            if ff[0] in C:
                sc = 0
            count += 1
    else:
        sc_flag = 1

if count == len(B):
    print("pairwise coprime")
elif sc == 1 or sc_flag ==1:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Wrong Answer

Solution code:
import bisect
import sys,io
import math
from collections import deque
from heapq import heappush, heappop
import functools
input = sys.stdin.buffer.readline

def sRaw():
    return input().decode("utf-8").rstrip("\n").rstrip("\r")


def iRaw():
    return int(input())

def ssRaw():
    return input().split()


def isRaw():
    return list(map(int, ssRaw()))

INF = 1 << 29

DIV = (10**9) + 7
#DIV = 998244353

def mod_inv_prime(a, mod=DIV):
    return pow(a, mod-2, mod)


def mod_inv(a, b):
    r = a
    w = b
    u = 1
    v = 0
    while w != 0:
        t = r//w
        r -= t*w
        r, w = w, r
        u -= t*v
        u, v = v, u
    return (u % b+b) % b


def CONV_TBL(max, mod=DIV):
    fac, finv, inv = [0]*max, [0]*max, [0]*max
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1
    for i in range(2, max):
        fac[i] = fac[i-1]*i % mod
        inv[i] = mod - inv[mod % i] * (mod//i) % mod
        finv[i] = finv[i-1]*inv[i] % mod

    class CONV:
        def __init__(self):
            self.fac = fac
            self.finv = finv
            pass

        def ncr(self, n, k):
            if(n < k):
                return 0
            if(n < 0 or k < 0):
                return 0
            return fac[n]*(finv[k]*finv[n-k] % DIV) % DIV

    return CONV()


def cumsum(As):
    s = 0
    for a in As:
        s += a
        yield s


sys.setrecursionlimit(200005)


def dijkstra(G,start=0):
    heap = []
    cost = [INF]*len(G)
    heappush(heap,(0,start))
    while len(heap)!=0:
        c,n = heappop(heap)
        if cost[n] !=INF:
            continue
        cost[n]=c
        for e in G[n]:
            ec,v = e
            if cost[v]!=INF:
                continue
            heappush(heap,(ec+c,v))
    return cost

def gcd_list(As):
    return functools.reduce(math.gcd, As)

def lcm_div(x, y):
    return ((x * y) // math.gcd(x, y))%DIV

def lcm_div_list(numbers):
    return functools.reduce(lcm_div, numbers, 1)%DIV


def main():
    N = iRaw()
    As = isRaw()
    gcds = gcd_list(As)
    if gcds!=1:
        print("not coprime")
        return
    lcms = lcm_div_list(As)
    mul_div = 1
    for a in As:
        mul_div = (mul_div*a)%DIV
    if lcms == mul_div:
        print("pairwise coprime")
        return
    else:
        print("setwise coprime")
        return
    
main()

Submission status: Wrong Answer

Solution code:
#Code by Sounak, IIESTS
#------------------------------warmup----------------------------

import os
import sys
import math
from io import BytesIO, IOBase
from fractions import Fraction
import collections
from itertools import permutations
from collections import defaultdict


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

#-------------------game starts now-----------------------------------------------------
mod=10**9+7
n=int(input())
a=list(map(int,input().split()))
a.sort()
g=a[0]
d=defaultdict(int)
for i in a:
    g=math.gcd(g,i)
    d[i]+=1
if g>1:
    print("not coprime")
p=[0]*(a[-1]+1)
ch=0
for i in range (2,a[-1]+1):
    if p[i]==1:
        continue
    p[i]=1
    ans=0
    for j in range (i,a[-1]+1,i):
        ans+=d[j]
    if ans>1:
        ch=1
        break
if ch==1:
    print("setwise coprime")
else:
    print("pairwise coprime")

Submission status: Wrong Answer

Solution code:
import math
import sys
n=int(input())
a=list(map(int,input().split()))
ans=a[0]
a=sorted(a)
flag=0
for i in range(len(a))[::-1]:
    for j in range(len(a)):
        if math.gcd(a[i],a[j])!=1 and i!=j:
            flag=1
            break
    if flag==1:
        break
    if i==0:
        print("pairwise coprime")
        sys.exit()
for i in range(1,len(a)):
    ans=math.gcd(ans,a[i])
    if ans==1:
        print("setwize coprime")
        sys.exit()
print("not coprime")

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float("INF")
def primes(n):
    ass = []
    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
    for i in range(len(is_prime)):
        if is_prime[i]:
            ass.append(i)
    return ass

#solve
def solve():
    n = II()
    a = LI()
    M = 10 ** 6 + 1
    p = [True] * M
    p[0] = False
    p[1] = False
    d = [-1] * M
    for xi in range(2, M):
        if p[xi]:
            d[xi] = xi
            for i in range(xi * 2, M, xi):
                p[i] = False
                if d[i] == -1:
                    d[i] = xi
    res = defaultdict(int)
    flg = 0
    for ai in a:
        tmp = []
        if d[ai] == -1:
            res[ai] = 1
            tmp = [ai]
        else:
            while d[ai] != -1:
                tmp.append(d[ai])
                ai = ai // d[ai]
        for t in set(tmp):
            if res[t]:
                flg = 1
            res[t] = 1
        if flg:
            break
    else:
        print("pairwise comprime")
        return
    g = a[0]
    for i in a:
        g = math.gcd(g, i)
    if g == 1:
        print("setwise comprime")
        return
    print("not comprime")
    
    return


#main
if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
from bisect import bisect_right


import math
from functools import reduce

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

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


P=[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]

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

check = [0]*1000
flag = 0
for a in A:
    for i in range(bisect_right(P, int(a**0.5))):
        if a%P[i] == 0 and flag == 0:
            if check[P[i]] == 1:
                flag = 1
            else:
                check[P[i]] = 1
    if flag:
        break

if gcd_list(A) > 1:
    print("not coprime")
elif flag:
    print("setwise coprime")
else:
    print("pairwise coprime")

Submission status: Wrong Answer

Solution code:
def max(a,b):
    if a>b:
        return a
    else:
        return b

def min(a,b):
    if a>b:
        return b
    else:
        return a

def gcd(a,b):
    a,b = max(a,b),min(a,b)
    while a%b!=0:
        a,b = b,a%b
    return b

from collections import defaultdict
def factorize(n,dd):
    #print(int(n**0.5))
    for i in range(2,int(n**0.5)+1):
        flag=True
        while n%i==0 and n>0:
            if flag:
                if dd[i]>0:
                    return False
                else:
                    flag=False
            dd[i]+=1
            n//=i
    if n>1:
        if dd[n]>0:
            return False
        dd[n]+=1
    #print(dd)
    return True

def gcdl(A):
    if len(A)==2:
        return gcd(A[0],A[1])
    elif len(A)==1:
        return A[0]
    else:
        return gcd(gcdl(A[:len(A)//2]),gcdl(A[len(A)//2:]))

import sys

sys.setrecursionlimit(500000)
def input():
    return sys.stdin.readline()[:-1]

def main():
    N = int(input())

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

    B = [a for a in A if a!=1]

    if len(B)<=1:
        print("pairwise coprime")
    else:
        N = len(B)
        if N>78498:
            print("not coprime")
        else:
            dd = defaultdict(int)
            flag=True
            for b in B:
                if factorize(b,dd)==False:
                    flag=False
                    break
            if flag:
                print("pairwise coprime")
            else:
                if gcdl(B)==1:
                    print("setwise coprime")
                else:
                    print("not coprime")        
        
if __name__ == '__main__':
    main()

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)
            
        i = 0
        while i < len(A):
            if A[i] % prime == 0:
                A.pop(i)
                continue
            i += 1
            
    for a in A:
        P.append(a)
            
    return P


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
        #print('setwise coprime')
    else:
        print('not coprime')
        return






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


resolve()

Submission status: Wrong Answer

Solution code:
def pair (inp):
    from collections import Counter
    z=max(inp)
    arr=[1]*(z+1)
    c=Counter(inp)
    c[1]=0
    if max(c.values())>=2 :
        return -1
    for i in range(2,z+1):
        if arr[i]==1:
            k=2
            f=0
            while k*i<len(arr):
                arr[k*i]=0
                if c[k*i]!=0:
                    f+=c[k*i]
                k+=1
            if f>=2:
                return -1
    return 1
def gcd (a,b):
    if a%b==0:
        return b
    if b%a==0:
        return a
    if a>b:
        return gcd(b,a%b)
    if b>a:
        return gcd(a,b%a)
n=int(input())
arr=list(map(int,input().split()))
if pair(arr)==1:
    print ('pairwise coprime')
else:
    k=arr[0]
    for i in range(1,len(arr)):
        k=gcd(k,arr[i])
        if k==1:
            break
    if k==1:
        print ('setwise coprime')
    else:
        print ('not coprime')

Submission status: Wrong Answer

Solution code:
def eratosthenes(mx, sss):
    array = [1 for _ in range(mx + 1)]
    array[0] = array[1] = 0
    pair_wise = True
    set_wise = True
    cnt = 0
    for i in range(2, mx+1, 2):
        array[i] = 0
        if i in sss:
            cnt += 1
    if cnt > 1:
        pair_wise = False
    if cnt == len(sss):
        set_wise = False

    for i in range(3, mx + 1, 2):
        if not array[i]:
            continue
        cnt = 0
        for j in range(i, mx + 1, i):
            array[j] = 0
            if i in sss:
                cnt += 1
        if cnt == len(sss):
            set_wise = False
            break

    if pair_wise:
        print('pairwise coprime')
    elif set_wise:
        print('setwise coprime')
    else:
        print('not coprime')

def resolve():
    n = int(input())
    a = set(map(int, input().split()))

    eratosthenes(max(a), a)

if __name__ == "__main__":
    resolve()

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
def main():
    N = 10**6
    table = [0 for _ in range(N+1)]
    prime = [True] * (N+1)
    for i in range(2, N+1):
        if not prime[i]:
            continue
        else:
            table[i] = i
            num = i + i
            while num < N:
                prime[num] = False
                table[num] = i
                num += i

    def factorize(n):
        ans = []
        while not prime[n]:
            ans.append(table[n])
            n = n // table[n]
        ans.append(n)
        return ans
    n = I()
    A = LI()
    coprime = True
    c = collections.Counter()
    memo = {}
    for a in A:
        soinsu = factorize(a)
        memo[a] = soinsu
        for s in soinsu:
            c[s] += 1

    for a in A:
        soinsu = memo[a]
        for s in soinsu:
            if c[s] > 0:
                c[s] -= 1
        for s in soinsu:
            if c[s] > 0:
                coprime = False
                break
    def gcd(a, b):
        if b == 0:
            return a
        return gcd(b, a % b)

    if coprime:
        print("pairwise coprime")
        return

    setwise = False
    m = A[0]
    for a in A:
        m = gcd(a, m)
    if m == 1:
        setwise = True
    if setwise:
        print("setwise coprime")
        return
    print("not coprime")
    return





main()

Submission status: Wrong Answer

Solution code:
import math
n = int(input())
lis = list(map(int,input().split()))
lis.sort(reverse=True)
num = lis[0]
for nu in lis:
    num = math.gcd(num,nu)
exist = [0 for i in range(max(lis)+1)]
if num != 1:
    print("not coprime")
    exit()
for nu in lis:
    if nu != 1:
        for i in range(2,math.ceil(math.sqrt(nu))+1):
            if nu % i == 0:
                if exist[i] == 1:
                    print("setwise coprime")
                    exit()
                else:
                    exist[i] = 1
                    while nu % i == 0:
                        nu //= i
print("pairwise coprime")

Submission status: Wrong Answer

Solution code:

from math import gcd
from functools import reduce


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

lim = 10 ** 6 + 10
is_prime = [True] * (lim + 1)
is_prime[0] = False
is_prime[1] = False
min_factor = list(range(lim + 1))

for i in range(2, lim + 1):
    if is_prime[i]:
        for j in range(2 * i, lim + 1, i):
            is_prime[j] = False
            min_factor[j] = i

pairwise = True
appeared = set()
for v in X:
    while v > 1:
        if v in appeared:
            pairwise = False
            break
        appeared.add(v)
        v //= min_factor[v]

if pairwise:
    print("pairwise coprime")
elif reduce(gcd, 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=list(set(a))

def fact(n):
    arr = []
    ret = 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.append([i, cnt])
            ret.add(i)
    if temp!=1:
        arr.append([temp, 1])
        ret.add(temp)
    if arr==[]:
        arr.append([n, 1])
        ret.add(n)

    return ret

from collections import defaultdict
cntd=defaultdict(int)
for i in range(len(a)):
    lis = fact(a[i])
    for num in lis:
        if num==1:
            continue
        cntd[num]+=1

flg=False

for c in cntd.values():
    if c==n:
        print("not coprime")
        exit()
    if c>1:
        flg=True
if flg:
    print("setwise coprime")
else:
    print("pairwise coprime")

Submission status: Wrong Answer

Solution code:
from math import gcd
(_,),a  = [list(map(int, s.split())) for s in open(0)]

ans = 'pairwise coprime'

g = a.pop()
for x in a:
    g, l = gcd(g, x), g * x
    if g != 1:
        ans = 'setwise coprime'
        l //= g
if g != 1:
    ans = 'not coprime'
print(ans)

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)

check = [0] * (10 ** 6 + 1)
for d in data:
    check[d] = 1
#print(check[:100])

def is_pairwise(arr):
    # 同じ数があったらアウト
    len_A = len(arr)
    A = list(set(arr))
    if len_A != len(arr):
        return 0
    
    # 比素数が168個以上あったらアウト
    non_prime = []
    for a in arr:
        if check[a] == 0:
            non_prime.append(a)
    #print(non_prime)
    
    if len(non_prime) > 168:
        return 0
    
    cnt = [0] * 1001
    for np in non_prime:
        for d2 in data2:
            if np % d2 == 0:
                cnt[d2] += 1
    if max(cnt) >= 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:
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()))
P=primes(10**6)
C={}
for i in range(78498):
  C[P[i]]=i
p=set(P)
B=[0]*(78498)
for i in range(n):
  x=A[i]
  s=A[i]**(1/2)+5
  j=0
  if x in p:
    B[C[x]]+=1
    continue
  while P[j]<s:
    if x in p:
      B[C[x]]+=1
      break
    if x%P[j]==0:
      B[j]+=1
      x=x//P[j]
      while x%P[j]:
        x=x//P[j]
    s=x**(1/2)+5
    j=j+1
f=0
for i in range(78498):
  if B[i]>1:
    f=1
if f==0:
  print("pairwise coprime")
  exit()
for i in range(78498):
  if B[i]>=n:
    f=0
if f==1:
  print("setwise coprime")
else:
  print("not coprime")

Submission status: Wrong Answer

Solution code:
def  gcd( a,  b): 
    while a != 0: 
        a, b = b % a, a
    return b
N = int(input())
A = [int(s) for s in input().split()]

def is_pw(N, A):
    prod = 1
    for a in A:
        if gcd(a, prod) == 1:
            prod *= a
        else:
            return False
    return True

def is_sw(N,A):
    n = A[0]
    for a in A:
        n = gcd(a, n) 
        if n == 1:
            return True
    return False

def main(N, A):
    if N < 78498:
        if is_pw(N, A):
            print('pairwise coprime')
            return

    if is_sw(N, A):
        print('setwise coprime')
        return 
    print('not coprime')
main(N, A)

Submission status: Wrong Answer

Solution code:

from math import gcd
N=int(input())
A=list(map(int, input().split()))
p=10**9+7

A=sorted(A)
gcda=A[0]
gcdais=True
gcdb=A[0]
MAX=max(A)
counts=[0]*MAX
counts[A[0]-1]+=1
for i in range(1,N):
    
    a=A[i]
    gcdb=gcd(gcdb, a)
    counts[a-1]+=1

for i in range(1,MAX):
    count=0
    now=i+1
    while now<=MAX:
        if counts[now-1]!=0:
            count+=1
        now+=(i+1)
    if count>=2:
        gcdais=False
    
#print(counts)
if gcdais:
    print("pairwise coprime")
elif gcdb==1:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Wrong Answer

Solution code:
from math import gcd
N=int(input())
A=[int(i) for i in input().split()]

ans=0
product=int(1)
g=gcd(A[0],A[1])
if g!=1:
    ans=1


for i in range(N):
    if ans==0:
        if product%A[i]==0:
            ans=1
        product*=A[i]
    if g!=1:
        g=gcd(g,A[i])

if ans==0:
    print('pairwise coprime')
elif g==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()))

def calc_primes(n):
    data = [i for i in range(2, n + 1)]
    for d in data:
        data = [x for x in data if (x == d or x % d != 0)]
    return data

primes = calc_primes(int(math.sqrt(10**6)))

is_pairwise = True if N <= len(primes) else False
prod = 1
all_gcd = A[0]
for a in A:
    all_gcd = math.gcd(all_gcd, a)
    if is_pairwise:
        g = math.gcd(prod, a)
        if g > 1:
            is_pairwise = False
        prod *= a

if is_pairwise:
    print('pairwise coprime')
elif all_gcd == 1:
    print('setwise coprime')
else:
    print('not coprime')

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, cnt])

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

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

    return arr
#pairwise coprime どの2つをとっても共通素因数がない
#setwise coprime すべてに共通する素因数が存在しない
#左から見ていって、素因数の個数をカウントしていく…？
#setwise はエラトステネスの篩を再帰的に行う
#pairwise はそもそも、maxまでの素数の個数までしか存在し得ない
N = int(input())
A = [int(hoge) for hoge in input().split()]
Pairwise = False
Setwise = False
SOSUU = [0]*(10**6+10)
A.sort()
Fail = False
G = A[0]
for a in A:
    G = math.gcd(G,a)
if G != 1:
    print("not coprime")
    exit()

if len(A) <= 80000:
    for a in A:
        Fact = factorization(a)
        for f in Fact:
            if SOSUU[f[0]] > 0:
                Fail = True
                break
            else:
                SOSUU[f[0]] += 1
        if Fail:
            break
    if not Fail:
        Pairwise = True
if Pairwise:
    print("pairwise coprime")
else:
    print("setwise coprime")

Submission status: Wrong Answer

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip("\r\n")

def max_gcd_pair(S):
    # Assumption 1: S is the list of numbers
    # Assumption 2: There are no duplicates in S

    s = set(S)
    m = max(S)

    res = 0
    i = m

    while(i > 0):
        a = i
        cnt = 0
        while (a<=m): # a maxed at max of the list
            if a in s:   
               cnt += 1
            a += i

        if cnt >= 2:  # we have found the result
            res = i
            break

        i = i -1 

    return res

n = int(input())
a = [int(x) for x in input().split()]

if max_gcd_pair(a) == 1:
    print('pairwise coprime')
    sys.exit()

import math
from functools import reduce

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

if gcd(*a) == 1:
    print('setwise coprime')
    sys.exit()

else:
    print('not coprime')

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import math

def cal_primes(N):
    candidate = [*range(2, N+1)]
    primes = []

    while candidate[0]**2 <= N:
        primes.append(candidate[0])
        candidate = [*filter(lambda x: x % candidate[0] != 0, candidate)]
    
    primes.extend(candidate)
    return primes

def main():
    N = int(input())
    A = list(map(int, input().split()))
    if N == 2:
        if math.gcd(A[0],A[1]) == 1:
            ans = 0
        else:
            ans = 2
    else:
        A.sort()
        nums = [0] * (10**6+1)
        for a in A:
            nums[a] = 1
        
        plist = cal_primes(10**6//2)

        ans = 0
        for p in plist:
            now = p
            cnt = 0
            while now <= 10**6:
                if nums[now]:
                    cnt += 1
                now += p
            if cnt == N:
                ans = 2
                break
            elif cnt > 1:
                ans = 1
    
    if ans == 0:
        print('pairwise coprime')
    elif ans == 1:
        print('setwise coprime')
    else:
        print('not coprime')

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from math import gcd
n = int(input())
a = list(map(int, input().split()))
a.sort()
used = [False] * (10**6+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)
    if temp!=1:
        arr.append(temp)
    if arr==[]:
        arr.append(n)
    return arr

g = a[0]
arr = factorization(a[0])
for i in arr:
    used[i] = True

pair = True
for i in range(n-1):
    g = gcd(g, a[i+1])
    # 一度でも互いに素でない組合せが出たらpariwise coprimeではない
    arr = factorization(a[i+1])
    for i in arr:
        if used[i]: pair=False
        used[i] = True
if g > 1:
    print('not coprime')
    exit(0)
if not pair:
    print('setwise coprime')
    exit(0)
else:
    print('pairwise coprime')

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline

n = int(input())
a = [int(item) for item in input().split()]

smallest_factor = [-1] * (10**6 + 10) 
for i in range(2, n+1):
    if smallest_factor[i] != -1:
        continue
    base = i
    j = 2
    while base * j <= (10**6 + 1):
        smallest_factor[base * j] = i
        j += 1

factor_count = [0] * (10**6 + 10)
is_pairwise = True
for item in a:
    val = item
    pset = set() 
    while smallest_factor[val] != -1:
        pset.add(smallest_factor[val])
        val //= smallest_factor[val]
    pset.add(val)
    for item in pset:
        factor_count[item] += 1

same_p = max(factor_count)
if same_p == 1:
    print("pairwise coprime")
elif same_p == n:
    print("not coprime")
else:
    print("setwise coprime")