Problem:


Score : 500 points

Problem Statement

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

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

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

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

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

Constraints

2 \leq N \leq 10^6

1 \leq A_i\leq 10^6

Input

Input is given from Standard Input in the following format:

N
A_1 \ldots A_N

Output

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

Sample Input 1

3
3 4 5

Sample Output 1

pairwise coprime

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

Sample Input 2

3
6 10 15

Sample Output 2

setwise coprime

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

Sample Input 3

3
6 10 16

Sample Output 3

not coprime

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



Sample input:
3
3 4 5


Sample output:
pairwise coprime

Submission status: Wrong Answer

Solution code:
import math
import sys
from collections import Counter

n = int(input())
a = list(map(int,input().split()))
ma = max(a)
pc = True

if ma == 1:
    print("pairwise coprime")
    sys.exit()
if len(Counter(a)) != n:
    pc = False
    
cu = [0]*(ma+1)
for i in a:
    cu[i] = 1

for i in range(2,ma+1):
    aa = 0
    for j in range(i,ma+1,i):
        aa += cu[j]
    if aa > 1:
        pc = False

gc = a[0]
for i in a[1:]:
    gc = math.gcd(i,gc)
    
if pc:
    print("pairwise coprime")
elif gc == 1:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Wrong Answer

Solution code:
def divisor(i):
    s = []
    for j in range(1, int(i ** (1 / 2)) + 1):
        if i % j == 0:
            s.append(i // j)
            s.append(j)
    return sorted(set(s))

import math

n = int(input())
a = list(map(int, input().split()))
ans = ["pairwise coprime", "setwise coprime", "not coprime"]
if n >= 100000:
    g = a[0]
    for i in a:
        g = math.gcd(i, g)
        if g == 1:
            print(ans[1])
            exit()
    print(ans[2])
    exit()
else:
    x = [0] * 1000005
    for i in a:
        s = divisor(i)
        t = 1
        for j in s:
            if j == 1:
                continue
            if x[j] == 1:
                t = 0
                break
            x[j] = 1
        if t == 0:
            break
    if t == 1:
        print(ans[0])
        exit()
    g = a[0]
    for i in a:
        g = math.gcd(i, g)
        if g == 1:
            print(ans[1])
            exit()
    print(ans[2])
    exit()

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
tmp = [False if i == 0 or i == 1 else True for i in range(1000)]
p, s = True, True

for i in range(2, 1000):
    t = 0
    if tmp[i]:
        for j in A:
            if j % i == 0:
                t += 1

    for j in range(i * 2, 1000, i):
        tmp[j] = False
    
    if t >= 2:
        p = False
    
    if t == N:
        s = False
        break

print('pairwise coprime' if p else 'setwise coprime' if s else 'not coprime')

Submission status: Wrong Answer

Solution code:
n = int(input())
*arr, = map(int, input().split())

def pairwise_coprime(arr):
    mx = max(arr)
    data = [0] * (mx + 1)
    for v in arr:
        data[v] = 1
    primes = [1] * (mx + 1)
    for v in range(2, mx + 1):
        if primes[v]:
            cnt = 0
            for nonprime in range(2 * v, mx + 1, v):
                primes[nonprime] = 0
                if data[nonprime]:
                    cnt += 1
            if cnt > 1:
                return False
    return True

def gcd(a, b):
    if a > b:
        a, b = b, a

    while a:
        # gcd(a, b) = gcd(b, a % b)
        b, a = a, b % a
    return b


def setwise_coprime(arr):
    common_gcd = arr[0]
    for i in range(1, len(arr)):
        common_gcd = gcd(common_gcd, arr[i])
    return common_gcd == 1


if pairwise_coprime(arr):
    print("pairwise coprime")
elif setwise_coprime(arr):
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Wrong Answer

Solution code:
import math
def makePrimes(x):
    if x < 2: return []

    primes = [i for i in range(x)]
    primes[1] = 0 # 1は素数ではない

    # エラトステネスのふるい
    for prime in primes:
        if prime > math.sqrt(x): break
        if prime == 0: continue
        for non_prime in range(2 * prime, x, prime): primes[non_prime] = 0

    return [prime for prime in primes if prime != 0]

primes = makePrimes(10**6)
prime_set = set()
def prime_factorization(n):
    tmp = n
    ret = True
    m = int(-(-n**0.5//1))+1
    for p in primes:
        if m < p:
            break
        if tmp%p==0:
            if p in prime_set:
                ret = False
            while tmp%p==0:
                tmp//=p
            prime_set.add(p)
    if tmp!=1:
        prime_set.add(tmp)
    return ret

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

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

if pairwize:
    print("pairwise coprime")
elif gcd == 1:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Wrong Answer

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

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)

def get_primes(N):
    is_prime = [True] * (N+1)
    is_prime[0] = is_prime[1] = False
    for i in range(int(N**0.5)+1):
        if not is_prime[i]:
            continue
        for j in range(i+i, N+1, i):
            is_prime[j] = False
    return [i for i in range(N+1) if is_prime[i]]

def solve(N: int, A: "List[int]"):
    from math import gcd
    from functools import reduce
    from collections import defaultdict
    counts = defaultdict(int)
    for a in A:
        for p in PRIMES:
            if a % p == 0:
                counts[p] += 1
    if max(counts.values()) == 1:
        return "pairwise coprime"
    return "setwise coprime" if reduce(gcd, A) == 1 else "not coprime"


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools
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]"
    print(solve(N, A))

def test():
    import doctest
    doctest.testmod()

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

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().rstrip().split()
def S(): return sys.stdin.readline().rstrip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]

mod=10**9+7




pair_flg=0
set_flg=0
n=I()
A=LI()
t_set=set()
D=defaultdict(set)
s_set=set()
for j in range(n):
    a=A[j]
    prime_set = D[A[j]]
    flg=0
    if not prime_set:
        for i in range(2, int(a ** 0.5) + 1):
            while a % i == 0:
                a //= i
                if D[a]:
                    prime_set|=D[a]
                    flg=1
                    break
            if a == 1 or flg:
                break
        if a != 1:
            prime_set.add(a)
        D[A[j]]=prime_set
    if prime_set&t_set:
        pair_flg=1
    t_set|=prime_set
    if j:
        s_set&=prime_set
    else:
        s_set=prime_set


if not pair_flg:
    print("pairwise coprime")
elif not s_set:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

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

# n = 10**6
# A = [i+1 for i in range(n)]

A.sort()
p_ng = 0
l = 10**6 + 5
B = [0] * l

for i in range(2, l):
    if B[i] == 0:
        j = 2
        ind = j * i
        while ind < l:
            B[ind] = 1
            j += 1
            ind = j * i

C = [0] * l
for i in range(n):
    if A[B[i]] == 0:
        if C[B[i]] == 1:
            p_ng = 1
            break
        C[i] = 1
    else:
        a = A[i]
        w = 2
        one = []
        while a != 1:
            f = 1

            while a%w == 0:
                a//=w
                if f == 1 and C[w] == 1:
                    p_ng = 1
                    break
                f = 0
                one.append(w)
            w += 1
            if B[a] == 0:
                if C[a] == 1:
                    p_ng = 1
                    break
                one.append(a)
                break
            # print(a,w)
            if p_ng== 1:
                break
        for ii in one:
            C[ii] = 1
        if p_ng == 1:
            break


# ind = 0
# while ind < n and A[ind] == 1:
#     ind += 1

# if ind < n:
#     for j in range(ind, n):
#         # print(B[:10])
#         for i in range(1, (l-1) // A[j] + 1):
#             indj = i * A[j]
#             # print(indj)
#             if i == 1 and B[indj] == 1:
#                 p_ng = 1
#                 break
#             B[indj] = 1
#         if j > 0 and A[j-1] == A[j]:
#             p_ng = 1
#             break
#         if p_ng == 1:
#             break

if p_ng == 0:
    print("pairwise coprime")
    sys.exit()

from math import gcd
g = A[0]
for i in range(1, n):
    g = gcd(g, A[i])

if g == 1:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Wrong Answer

Solution code:
def make_divisors(n):
    divisors = []
    # 試し割りで、かつ積でnを作るときの相方も同時に追加してる
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors
from math import gcd
import sys
n = int(input())
a_ls = list(map(int, input().split()))
now = a_ls[0]
for i in range(1,n):
    now = gcd(now,a_ls[i])
if now != 1:
    print('not_coprime')
    sys.exit()
else:
    a_ls.sort()
    is_in_a = [0] * (10**6+1)
    for a in a_ls:
        is_in_a[a] = 1

    res = 'pairwise coprime'
    Max = a_ls[-1]
    for i in range(n):
        divisors = make_divisors(a_ls[i])
        for d in divisors:
            if d == 1:
                continue
            base = d
            now = 2*base
            while now <= int((10**6)**0.5)+1:
                if is_in_a[now] and not now == a_ls[i]:
                    res = 'setwise coprime'
                now += base

    print(res)

Submission status: Wrong Answer

Solution code:
def prime_decomposition(n):
    i = 2
    table = []
    while i * i <= n:
        while n % i == 0:
            n //= i
            table.append(i)
        i += 1
    if n > 1: table.append(n)
    return set(table)

n = int(input())
a = list(map(int, input().split()))
d = [0] * (10**6+1)
for i in range(n):
    for j in prime_decomposition(a[i]):
        d[j] += 1
        
max_ = max(d)
if max_ == 1:
    print('pairwise coprime')
elif max_ != n:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Wrong Answer

Solution code:
from math import gcd
from collections import Counter, defaultdict, deque

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


ACounter = Counter(A)

hasPair = any(v > 1 for v in ACounter.values())
if not hasPair:
    seenCount = defaultdict(set)

    def sieve(n):
        ret = [-1] * n
        for i in range(2, n):
            if ret[i] == -1:
                for j in range(i, n, i):
                    # each cell is rewritten once for each of its unique prime factors so total cost is O(n loglog n)
                    ret[j] = i
                    if ACounter[j]:
                        seenCount[i].add(j)
        return ret

    sieve(10 ** 6 + 1)

    # print({k: v for k, v in seenCount.items() if v})
    hasPair = any(len(v) > 1 for k, v in seenCount.items())

if hasPair:
    g = 0
    for x in A:
        g = gcd(g, x)
    if g == 1:
        print("setwise coprime")
    else:
        print("not coprime")
else:
    print("pairwise coprime")

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().rstrip().split()
def S(): return sys.stdin.readline().rstrip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]

mod=10**9+7




pair_flg=0
set_flg=0
n=I()
A=LI()
t_set=set()
D=defaultdict(set)

for j in range(n):
    a=A[j]
    prime_set = D[A[j]]
    flg=0
    if not prime_set:
        for i in range(2, int(a ** 0.5) + 1):
            while a % i == 0:
                a //= i
                if D[a]:
                    prime_set|=D[a]
                    flg=1
                    break
            if a == 1 or flg:
                break
        if a != 1:
            prime_set.add(a)
        D[A[j]]=prime_set
    if prime_set&t_set:
        pair_flg=1
    t_set|=prime_set
    if j:
        s_set&=prime_set
    else:
        s_set=prime_set


if not pair_flg:
    print("pairwise coprime")
elif not s_set:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Wrong Answer

Solution code:
# E - Coprime
from math import gcd

N = int(input())
A = list(map(int,input().split()))
A = sorted(A)
L = [None]*(10**6+1)
L[1] = set()

def prime(x):
    global L
    if L[x]!=None:
        return L[x]
    p = 2
    while True:
        if x%p==0:
            s = prime(x//p)|set([p])
            L[x] = s
            return L[x]
        p = p+1 if p*p<=x else x
        
G = A[0]
pairwise = True
s = prime(A[0])

for i in range(1,N):
    a = A[i]
    t = prime(a)
    if len(s&t)>0:
        pairwise = False
    s = s|t
    G = gcd(G,a)
    if G==1:
        break

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

Submission status: Wrong Answer

Solution code:
import math
def makePrimes(x):
    if x < 2: return []

    primes = [i for i in range(x)]
    primes[1] = 0 # 1は素数ではない

    # エラトステネスのふるい
    for prime in primes:
        if prime > math.sqrt(x): break
        if prime == 0: continue
        for non_prime in range(2 * prime, x, prime): primes[non_prime] = 0

    return [prime for prime in primes if prime != 0]

primes = makePrimes(10**6)
prime_set = set()
def prime_factorization(n):
    tmp = n
    ret = True
    m = int(-(-n**0.5//1))+1
    for p in primes:
        if m < p:
            break
        if tmp%p==0:
            if p in prime_set:
                ret = False
            while tmp%p==0:
                tmp//=p
            prime_set.add(p)
    if tmp!=1:
        prime_set.add(tmp)
    return ret

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

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

if pairwize:
    print("pairwize coprime")
elif gcd == 1:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Wrong Answer

Solution code:
from math import *
n = int(input())
a = list(map(int,input().split()))
g = 0
for i in range(n):
    g = gcd(g,a[i])
    
if g == 1:
    x = a.count(1)
    a = list(set(a))
    m = len(a)
    

    
    if m != n - x + 1:
        print("setwise coprime")
        
    else:
    
        b = [True]*(10**6+1)

        for i in range(m):
            b[a[i]] = False

        sw = 1
        
        for i in range(2, 10**6+1):
            q = 0
            j = 1
            while i*j <= 10**6:
                if b[i*j] == False:
                    q += 1
                j += 1
                
                
            if q >= 2:
                sw = 0
                break

        if sw == 0:
            print("setwise coprime")
        else:
            print("pairwise coprime")
        
else:
    print("not coprime")

Submission status: Wrong Answer

Solution code:
import sys
from math import gcd
from functools import reduce

input = sys.stdin.readline


def find_divisors(n):
    divisors = []
    for i in range(1, int(n ** 0.5) + 1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n // i)

    # divisors.sort()
    return divisors


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

ds = [0] * (10 ** 6 + 1)

for ai in a:
    for d in find_divisors(ai):
        ds[d] += 1

if max(ds[2:]) == 1:
    ans = "pairwise coprime"
elif reduce(gcd, a) == 1:
    ans = "setwise coprime"
else:
    ans = "not coprime"
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
p = [0 for _ in range(10**6)]
pr = []
pr2 = [0 for _ in range(10**3)]
for i in range(2,10**3):
  if pr2[i] == 0:
    pr.append(i)
    now = i
    while True:
      try:
        pr2[now] = 1
        now += i
      except:
        break
#print(pr)
at = 0
for x in a:
  d = int(x)
  for y in pr:
    if d % y == 0:
      if p[y] == 1:
        at = 1
        #print(y)
      else:
        p[y] = 1
      while d % y == 0:
        d //= y
  if d != 1:
    p[d] += 1
  if at == 1:
    break
  #print(p)
if at == 0:
  print('pairwise coprime')
  exit()
now = int(a[0])
for x in a:
  big,sml = x,now
  while sml:
    #print(big,sml)
    big,sml = sml,big%sml
  now = big
  if now == 1:
    print('setwise coprime')
    exit()
  #print(now)
print('not coprime')

Submission status: Wrong Answer

Solution code:
import math
import sys
from collections import Counter

n = int(input())
a = list(map(int,input().split()))
ma = max(a)
pc = True

if ma == 1:
    print("pairwise coprime")
    sys.exit()
if len(Counter(a)) != n:
    pc = False
    
cu = [0]*(ma+1)
for i in a:
    cu[i] = 1

for i in range(2,ma+1):
    aa = 0
    for j in range(i,ma+1,i):
        aa += cu[i]
    if aa > 1:
        pc = False

gc = a[0]
for i in a[1:]:
    gc = math.gcd(i,gc)
    
if pc:
    print("pairwise coprime")
elif gc == 1:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Wrong Answer

Solution code:
#素因数分解
def Prime_Factorization(N):
    if N<0:
        R=[[-1,1]]
    else:
        R=[]

    N=abs(N)
    k=2
    while k*k<=N:
        if N%k==0:
            C=0
            while N%k==0:
                C+=1
                N//=k
            R.append([k,C])
        k+=1

    if N!=1:
        R.append([N,1])
    if not R:
        R.append([N,1])

    return R
#================================================
from math import gcd
N=int(input())
A=list(map(int,input().split()))

#Pairwise?
P=set()
F=True
for a in A:
    K=Prime_Factorization(a)
    for (p,_) in K:
        if p in P:
            F=False
            break
        else:
            P.add(p)

    if not F:
        break

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

#Setwise?
g=A[0]
for a in A:
    g=gcd(g,a)
    if g==1:
        break

if g==1:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Wrong Answer

Solution code:
import math
def makePrimes(x):
    if x < 2: return []

    primes = [i for i in range(x)]
    primes[1] = 0 # 1は素数ではない

    # エラトステネスのふるい
    for prime in primes:
        if prime > math.sqrt(x): break
        if prime == 0: continue
        for non_prime in range(2 * prime, x, prime): primes[non_prime] = 0

    return [prime for prime in primes if prime != 0]

primes = makePrimes(10**6)
prime_set = set()
def prime_factorization(n):
    tmp = n
    ret = True
    m = int(-(-n**0.5//1))+1
    for p in primes:
        if m < p:
            break
        if tmp%p==0:
            if p in prime_set:
                ret = False
            while tmp%p==0:
                tmp//=p
            prime_set.add(p)
    if tmp!=1:
        prime_set.add(tmp)
    return ret

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

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

if pairwize:
    print("pairwize coprime")
elif gcd == 1:
    print("setwize coprime")
else:
    print("not coprime")

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
from math import gcd
from functools import reduce
def input(): return sys.stdin.readline().rstrip()

def pairwaise(bools):
    for i in range(2,10**6):
        hantei=0
        for j in range(i,10**6+1,i):
            hantei+=bools[j]
        if hantei>1:
            return False
    return True


def main():
    n=int(input())
    A=list(map(int, input().split()))
    gcds=reduce(gcd,A)
    if gcds>1:
        print('not coprime')
    else:
        bools=[0]*(10**6+5)
        for AA in A:
            if bools[AA]==1:
                print('setwise coprime')
                exit()
            bools[AA]+=1
        if pairwaise(bools):
            print('pairwise coprime')
        else:
            print('setwise coprime')

    
    


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
'''
自宅用PCでの解答
'''
import math
#import numpy as np
import itertools
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7 #998244353
dir = [(-1,0),(0,-1),(1,0),(0,1)]
alp = "abcdefghijklmnopqrstuvwxyz"

#nまでの素数の配列を返す関数
def primes(n):
    if n == 1:
        return []
    else:
        tbl = [True]*(n+1)
        pri = set([2])
        for i in range(2,n+1,2):
            tbl[i] = False
        k = 3
        while k <= n:
            if tbl[k]:
                pri.add(k)
                for i in range(k,n+1,k):
                    tbl[i] = False
            k += 2
        return pri

def main():
    n = int(ipt())
    ps = primes(10**6)
    d = defaultdict(bool)
    a = [int(i) for i in ipt().split()]
    g = a[0]
    f = True
    if n > 78498:
        f = False

    for i in a:
        g = math.gcd(g,i)
        if f:
            ni = i
            for j in ps:
                ff = True
                while ni%j == 0:
                    if ff and d[i]:
                        f = False
                    d[i] = True
                    ff = False
                    ni //= j
                    if ni == 1:
                        break
            if ni == 1:
                continue
            if d[ni]:
                f = False
            d[ni] = True
        if g == 1 and not f:
            break

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




    return None

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from math import gcd
def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]
p = primes(1000)
c = [0]*1000
# print(p)
n = int(input())
a = list(map(int,input().split()))
g = 0
f = 1
for i in a:
    g = gcd(g,i)
    for j in p:
        if i%j == 0:
            c[j] += 1
if max(c) > 1:
    f = 0
if len(set(a)) != n:
    f = 0
# print(g,f)
if g == 1:
    if f == 1:
        print("pairwise coprime")
    else:
        print("setwise coprime")
else:
    print("not coprime")

Submission status: Wrong Answer

Solution code:
N = int(input())

from math import gcd
prime = [0] * 2 + [1] * (10 ** 6 - 1)
A = list(map(int, input().split()))
A.sort()
for i in range(2, 10 ** 3 + 1):
  if prime[i]:
    for j in range(2 * i, 10 ** 6 + 1, i):
      prime[j] = 0
P = [i for i in range(2, 10 ** 6) if prime[i]]
from bisect import bisect
S = bisect(A, 1)
if N - S <= len(P):
  T = 1
  for p in P:
    count = 0
    for i in range(bisect(A, p), N):
      if A[i] % p == 0:
        count += 1
    if count > 1:
      T = 0
      break
  if T:
    print('pairwise coprime')
    exit()
g = 0
for a in A:
  g = gcd(g, a)
if g == 1:
  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()))

PAIR_WISE = "pairwise coprime"
SET_WISE = "setwise coprime"
NOT = "not coprime"

def get_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

is_pair = True
is_set = True

primes = get_primes(1000)
p_map = {i:False for i in primes}
set_gcd = a[0]
for i in a:

    if is_pair:
        for p in primes:
            if i % p == 0:
                if p_map[p]:
                    is_pair = False
                else:
                    p_map[p] = True
    set_gcd = gcd(i, set_gcd)

is_set = set_gcd == 1
if is_pair:
    print(PAIR_WISE)
    exit()
if is_set:
    print(SET_WISE)
    exit()
print(NOT)

Submission status: Wrong Answer

Solution code:
from math import gcd
from collections import Counter, defaultdict, deque

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

ACounter = Counter(A)
seenCount = defaultdict(set)


def sieve(n):
    ret = [-1] * n
    for i in range(2, n):
        if ret[i] == -1:
            for j in range(i, n, i):
                # each cell is rewritten once for each of its unique prime factors so total cost is O(n loglog n)
                ret[j] = i
                if ACounter[j]:
                    seenCount[i].add(j)
    return ret


sieve(10 ** 6 + 1)

# print({k: v for k, v in seenCount.items() if v})
hasPair = any(len(v) > 1 for k, v in seenCount.items())
"""
hasPair = False
for i in range(N):
    for j in range(i + 1, N):
        if gcd(A[i], A[j]) != 1:
            hasPair = True

"""

if hasPair:
    g = 0
    for x in A:
        g = gcd(g, x)
    if g == 1:
        print("setwise coprime")
    else:
        print("not coprime")
else:
    print("pairwise coprime")

Submission status: Wrong Answer

Solution code:
from math import sqrt, gcd
def factoring(k): #kを因数分解し、素因数とその個数を辞書に入れて返す。
    dic = dict()
    n = int(sqrt(k))+2
    for i in range(2, n):
        count = 0
        while k%i == 0:
            count += 1
            k = k//i
        if count != 0:
            dic[i] = count
    if k != 1: #sqrt(k)までチェックしてもkが1になっていない --> kが素因数
        dic[k] = 1
    return dic

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


from collections import defaultdict


dic = defaultdict(int)

if N <= 10 ** 5:
    count = 0
    for a in A:
        tmp = factoring(a)
        for i in tmp:
            dic[i] = max(tmp[i], dic[i])
            count += tmp[i]

    tmp = 0
    for i in dic:
        tmp += dic[i]

    if count == tmp:
        print ('pairwise coprime')
        exit()

GCD = A[0]
for a in A:
    GCD = gcd(GCD, a)
    if GCD == 1:
        break

if GCD == 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()))

dp=[0 for _ in range(1000000+1)]

if n>=150:
  print('pairwise coprime')
  
else:
  ch1=0
  for h in range(n-1):
    g1=a[h]
    for f in range(h+1,n):
      g1=math.gcd(g1,a[f])
    if g1==1:
      ch1+=1
  if ch1==n-1:
    print('pairwise coprime')
    
  else:
    g=a[0]
    for h in range(1,n):
      g=math.gcd(g,a[h])
    
    if g==1:
      print('setwise coprime')
    
    else:
      print('not coprime')

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
n = 1000
primes = set(range(2, n+1))
for i in range(2, int(n**0.5+1)):
    primes.difference_update(range(i*2, n+1, i))
primes=list(primes)

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

Fpr = {}

for i in range(N):
  for p in primes:
    if A[i]%p != 0:
      continue
    while A[i]%p == 0:
      A[i] //= p
    if p in Fpr:
      Fpr[p] += 1
    else:
      Fpr[p] = 1
    
res = 0
for k in Fpr:
  res = max(res,Fpr[k])
if res == 1:
  print("pairwise coprime")
elif res == N:
  print("not coprime")
else:
  print("setwise coprime")