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
sys.setrecursionlimit(1 << 25)
readline = sys.stdin.buffer.readline
read = sys.stdin.readline  # 文字列読み込む時はこっち
ra = range
enu = enumerate


def exit(*argv, **kwarg):
    print(*argv, **kwarg)
    sys.exit()


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))
# 受け渡されたすべての要素からsubだけ引く.リストを*をつけて展開しておくこと


def a_int(): return int(readline())


def ints(): return list(map(int, readline().split()))


def read_col(H):
    '''H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) #一列の場合'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, readline().split())))
    return tuple(map(list, zip(*ret)))


def read_tuple(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, readline().split())))
    return ret


def read_matrix(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, readline().split())))
    return ret
    # return [list(map(int, read().split())) for _ in range(H)] # 内包表記はpypyでは遅いため


def factorization(n: int):
    if n == 1:
        return []  # 1は素数ではない
    # 素因数分解
    arr = []
    temp = n
    for i in range(2, int(n**0.5) + 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


def can_factorization(n: int):
    if n == 1:
        return []  # 1は素数ではない
    # 素因数分解
    arr = []
    temp = n
    for i in range(2, int(n**0.5) + 1):  # ここにバグがないか心配
        if temp % i == 0:
            arr.append(i)

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

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

    return arr


MOD = 10**9 + 7
INF = 2**31  # 2147483648 > 10**9
# default import
from collections import defaultdict, Counter, deque
from operator import itemgetter, xor, add
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  # , insort_left, insort_right
from functools import reduce
from math import gcd


N = a_int()
A = ints()

# setかはすぐわかる
# setでなければ not coprime
# pairは互いに素かをみればいいのか
# つまり因数分解して足してったときにすべての素数のべき数が1以下であれば良い

g_set = 0
cnt = defaultdict(lambda: 0)
flg = 1  # pairwiseであるフラグ
if N > 10**5:
    flg = 0
    for a in A:
        g_set = gcd(g_set, a)
else:
    for a in A:
        g_set = gcd(g_set, a)
        for p, n in factorization(a):
            if cnt[p] != 0:
                flg = 0
            cnt[p] += n


# print(cnt)
# for v in cnt.values():
#     if v > 1:
#         flg = 0
#         break

if g_set > 1:
    print('not coprime')
elif flg:
    print('pairwise coprime')
else:
    print('setwise coprime')

Submission status: Wrong Answer

Solution code:
def sieve_eratosthenes(n):
    primes = [0, 1] * (n // 2 + 1)
    if n % 2 == 0:
        primes.pop()
    primes[1] = 0
    primes[2] = 1
    for p in range(3, n + 1, 2):
        if primes[p]:
            for q in range(p * p, n + 1, 2 * p):
                primes[q] = 0
    return primes

NB = int(input())
B = list(map(int,input().split()))
A = []
for i in range(NB):
    if B[i]!=1:
        A.append(B[i])
N = len(A)

if N==0:
    print("pairwise coprime")
else:
    P = sieve_eratosthenes(10**6)
    Ps = []
    for i in range(10**6):
        if P[i]==1:
            Ps.append(i)
    PN = len(Ps)

    if N>PN+1:
        print("not coprime")
    else:
        flag = 0
        pf={}
        for i in range(N):
            pf1 = {}
            m=A[i]
            for i in range(2,int(m**0.5)+1):
                while m%i==0:
                    pf1[i]=pf1.get(i,0)+1
                    m//=i
            if m>1:pf1[m]=1
            for i in pf1.keys():
                pf[i]=pf.get(i,0)+1
                if pf[i]>1:
                    flag = 1
        if flag==0:
            print("pairwise coprime")
        else:
            import fractions
            ans = A[0]
            for i in range(1, N):
                ans = fractions.gcd(ans, A[i])
            if ans==1 or N!=NB:
                print("setwise coprime")
            else:
                print("not coprime")

Submission status: Wrong Answer

Solution code:
import math
import unittest
import collections


def f(n):
    e = set()
    if n < 2:
        return e
    if n % 2 == 0:
        e.add(2)
        while n % 2 == 0:
            n //= 2
    i = 3
    while i <= n:
        if n % i == 0:
            e.add(i)
            while n % i == 0:
                n //= i
        i += 2
    return e


def is_pairwise_coprime(n, a):
    e = set()
    for i in range(n):
        e2 = f(a[i])
        if e & e2:
            return False
        e |= e2
    return True


def is_setwise_coprime(n, a):
    gcd = a[0]
    for i in range(1, n):
        gcd = math.gcd(gcd, a[i])
    return gcd == 1


# number of prime
UPPER = 78498
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 solve(n, a):
    if not is_setwise_coprime(n, a):
        return 'not coprime'

    is_pairwise_coprime_flag = True

    a.sort()
    for i in range(n-1):
        if 1 < a[i] == a[i+1]:
            is_pairwise_coprime_flag = False
    used_factor = set()
    for p in PRIMES:
        for ai in a:
            if ai % p == 0:
                if p in used_factor:
                    return 'setwise coprime'
                else:
                    used_factor.add(p)


    if is_pairwise_coprime_flag:
        return 'pairwise coprime'
    return 'setwise coprime'


def main():
    n = int(input())
    a = list(map(int, input().split()))
    print(solve(n, a))


if __name__ == "__main__":
    main()


class Test(unittest.TestCase):
    def test_1(self):
        n = 3
        a = [3, 4, 5]
        self.assertEqual(solve(n, a), 'pairwise coprime')

    def test_2(self):
        n = 3
        a = [6, 10, 15]
        self.assertEqual(solve(n, a), 'setwise coprime')

    def test_3(self):
        n = 3
        a = [6, 10, 16]
        self.assertEqual(solve(n, a), 'not coprime')

    def test_4(self):
        n = 3
        a = [1, 1, 1]
        self.assertEqual(solve(n, a), 'pairwise coprime')

    def test_5(self):
        n = 3
        a = [1, 2, 2]
        self.assertEqual(solve(n, a), 'setwise coprime')

    def test_6(self):
        n = 10
        a = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
        self.assertEqual(solve(n, a), 'pairwise coprime')

    def test_7(self):
        n = 11
        a = [1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
        self.assertEqual(solve(n, a), 'pairwise coprime')

Submission status: Wrong Answer

Solution code:
import numpy as np
import sys
from math import gcd

input = sys.stdin.buffer.readline


def primes_np(n):
    is_prime = np.ones(n + 1, dtype=bool)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n ** 0.5) + 1):
        if not is_prime[i]:
            continue
        is_prime[i * 2:n + 1:i] = False
    return np.where(is_prime)[0].tolist()


N = int(input())
A = tuple(map(int, input().split()))
MAX = 10 ** 6


def pairwise(A):
    st = set(A)
    for p in primes_np(MAX):
        ct = 0
        for i in range(p, MAX + 1, p):
            if i in st:
                ct += 1
        if ct > 1:
            return False
    return True


def setwise(A):
    return np.gcd.reduce(A) == 1


if pairwise(A):
    print('pairwise coprime')
elif setwise(A):
    print('setwise coprime')
else:
    print('not 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 len(B)!=len(A):
                    print("setwise coprime")
                elif gcdl(B)==1:
                    print("setwise coprime")
                else:
                    print("not coprime")        
        
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from sys import stdin

rInt       = lambda : int(stdin.readline().strip("\n"))
rIntArray  = lambda : [int(x) for x in stdin.readline().split()]

rString    = lambda : stdin.readline().strip("\n")
rStrArray  = lambda : [x for x in stdin.readline().split()]

# for _ in range(rInt()):

maxn = 10**6

n = rInt()
arr = rIntArray()

pairwise, setwise = True, True

present = [False]*(maxn + 1)
for i in arr: present[i] = True

for i in range(2, maxn + 1):
	cnt = 0
	for j in range(i, maxn + 1, i):
		if present[j]:
			cnt += 1
	if cnt > 1:
		pairwise = False
	if cnt == n:
		setwise = False

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

Submission status: Wrong Answer

Solution code:
import sys
N = int(input())
A = list(map(int, input().split()))
A_max = max(A)
if A_max == 1:
    print("pairwise coprime")
    sys.exit()
dp = [0]*(A_max+10)
p = 0
s = 0
for i in range(2, max(int((A_max+1)**0.5)+1, 2)):
    c = 0
    if dp[i] == 0:
        dp[i] = 1
        for j in range(i, A_max+1, 2):
            if j % i == 0:
                dp[j] = 1
        for j in range(N):
            if A[j] % i == 0:
                c += 1
        if c >= 2:
            p = 1
        if c == N:
            s = 1
if p == 0:
    print("pairwise coprime")
elif s == 0:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Wrong Answer

Solution code:
def gcd(a,b):
    while b:
        a,b=b,a%b
    return a
      

N=int(input())
A=list(map(int,input().split()))
left=[0]*N
right=[0]*N
for i in range(1,N):
    left[i]=gcd(left[i-1],A[i-1])
    right[N-1-i]=gcd(right[N-i],A[N-i])
#pairwiseについて
ans=10**9
for i,j in zip(left,right):
    ans=min(ans,gcd(i,j))
#sewtwiseについて
a=A[0]
for i in range(1,N):
    a=gcd(a,A[i])

if ans==1:
    print('pairwise coprime')
elif a==1:
    print('sewtwise 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()))
q=0
size=10**6

judge=[0]*(size)

for i in range(len(a)):
    num=a[i]
    for j in range(2,int(num**0.5)+1):
        if num%j==0:
            if judge[j-1]==-1:
                q=1
            elif judge[num//j-1]==-1:
                q=1
            else:
                judge[j-1]=-1
                judge[num//j-1]=-1

    if judge[num-1]==-1:
        q=1
    else:
        judge[num-1]=-1

if reduce(math.gcd,a)==1:
    if q!=1:
        q=2
else:
    q=0

if q==2:
    print('pairwise coprime')

elif q==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()))
a.sort()

ans = a[0]
for i in range(1, n):
    ans = math.gcd(ans, a[i])

if ans!=1:
    print('not coprime')

else:
    for i in range(300):
        for j in range(i+1,n):
            if math.gcd(a[i],a[j])!=1:
                print('setwise coprime')
                exit()
    print('pairwise coprime')

Submission status: Wrong Answer

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

def gcdall(a):
	rt = 0
	for i in a:
		rt = math.gcd(rt, i)
		if rt == 1:
			break
	return rt

#GCD(ai, aj)=1 がすべてとは, aの中の素因数に共通のものがないということ

def makediv(n):
	lower_divisors , upper_divisors = [], []
	i = 1
	while i*i <= n:
		if n % i == 0:
			lower_divisors.append(i)
			if i != n // i:
				upper_divisors.append(n//i)
		i += 1
	return lower_divisors + upper_divisors[::-1]

def sieve(n):
	ret = set()
	divlis = [-1]*(n+1)  # 何で割ったかのリスト(初期値は-1)
	flag = [True]*(n+1)
	flag[0] = False
	flag[1] = False
	ind = 2
	while ind <= n:
		if flag[ind]:
			ret.add(ind)
			ind2 = ind**2
			while ind2 <= n:
				flag[ind2] = False
				divlis[ind2] = ind
				ind2 += ind
		ind += 1
	#何で割ったかのリストを取得したいとき, divlisも出力する
	return ret

targ = sieve(n)

def pairwise(a):
	t = set()
	mint = n
	mode = True
	for i in a:
		if i == 1:
			continue
		mint = min(i, mint)
		if i in targ:
			for j in range(i, mint, i):
				if j not in t:
					t.add(j)
				else:
					mode = False
					break
		else:
			k = makediv(i)
			for j in k:
				if j == 1:
					continue
				if j not in t:
					t.add(j)
				else:
					mode = False
					break
		if not mode:
			break
	return mode

if gcdall(a) == 1:
	if pairwise(a):
		print("pairwise coprime")
	else:
		print("setwise coprime")
else:
	print("not coprime")

Submission status: Wrong Answer

Solution code:
import sys

n = int(input())
numbers = list(map(lambda x: int(x), input().split()))
if_set_has_gcd = False
if_pair_has_gcd = False

max_divider = int(max(numbers) ** 0.5) + 1

for divider in range(2, max_divider + 1):
    print([each % divider == 0 for each in numbers])
    num_divided = sum([each % divider == 0 for each in numbers])
    if num_divided == n:
        if_set_has_gcd = True
    if num_divided >= 2:
        if_pair_has_gcd = True

# print(if_set_has_gcd, if_pair_has_gcd)    
if not if_pair_has_gcd:
    print('pairwise coprime')
    sys.exit()
    
if not if_set_has_gcd:
    print('setwise coprime')
    sys.exit()
    
print('not coprime')

Submission status: Wrong Answer

Solution code:
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
import numpy as np
def s(): return input()
def i(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10 ** 9)
INF = 10**9
mod = 10**9+7

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 list(set(arr))

N = i()
A = l()
li = []
num = [0]*(10**6+1)
for i in range(N):
    for j in factorization(A[i]):
        if j not in li:
            li.append(j)
        else:
            num[j] += 1
if max(num) == 0:
    print('pairwise coprime')
elif max(num) == N-1:
    print('not coprime')
else:
    print('setwise coprime')

Submission status: Wrong Answer

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

def mp(): return map(int, input().split())
def lmp(): return list(map(int, input().split()))
import math
from functools import reduce

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

n = int(input())
a = lmp()
agcd = gcd(a)
used = set()
flag = True
for i in range(n):
    tar = a[i]
    f = factorization(tar)
    for j in range(len(f)):
        if f[j][0] not in used:
            used.add(f[j][0])
        else:
            flag = False
            break
    if not flag:
        break
if flag:
    print("pairwise coprime")
elif agcd == 1:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Wrong Answer

Solution code:
def primes(n):
    ass = []
    is_prime = [True] * (n + 1)
    is_prime[0], is_prime[1] = False, 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

prime = primes(1009)

def prime_decomposition(n):
    i = 0
    table = []
    while prime[i]**2 < n:
        while n % prime[i] == 0:
            n //= prime[i]
            table.append(prime[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 sys import stdin
input=lambda : stdin.readline().strip()
from math import ceil,sqrt,factorial
from collections import deque
from bisect import bisect_left,bisect_right
def isPrime(n) : 
	# Corner cases 
	if (n <= 1) : 
		return False
	if (n <= 3) : 
		return True

	# This is checked so that we can skip 
	# middle five numbers in below loop 
	if (n % 2 == 0 or n % 3 == 0) : 
		return False

	i = 5
	while(i * i <= n) : 
		if (n % i == 0 or n % (i + 2) == 0) : 
			return False
		i = i + 6

	return True

# print all prime numbers 
# less than equal to N 
dp=[]
def printPrime(n): 
	for i in range(2, n + 1): 
		if isPrime(i): 
			dp.append(i)


n = 1000		
printPrime(n) 
# print(dp)
def gcd(a,b):
	while a%b!=0:
		a,b=b,a%b
	return b
n=int(input())
l=list(map(int,input().split()))
flag=1
a=l[n-1]
s=set()
z=list(l)
for i in range(n):
	j=0
	while l[i]>1 and j<len(dp):
		if l[i]%dp[j]==0:
			l[i]//=dp[j]
			if dp[j] in s:
				flag=0
				break
			while l[i]%dp[j]==0:
				l[i]//=dp[j]
			s.add(dp[j])
		j+=1
	if flag==0:
		break
	if l[i]>1:
		s.add(l[i])
if 1 in z:
	if z.count(1)==n:
		print("pairwise coprime")
		exit()
if flag:
	print("pairwise coprime")
	exit()
a=z[0]
for i in range(1,n):
	a=gcd(max(a,z[i]),min(a,z[i]))
	if a==1:
		break
if a==1:
	print("setwise coprime")
	exit()
print("not coprime")

Submission status: Wrong Answer

Solution code:
gcd=lambda x,y:gcd(y,x%y) if y!=0 else x
def f(a):
    p=a[0]
    for i in range(1,len(a)):
        p=gcd(p,a[i])
    if p==1:
        print("setwise coprime")
    else:
        print("not coprime")

n=int(input())
a=list(map(int,input().split()))
l=[0 for i in range(2*10**6)]
for i in a:
    l[i]+=1
for i in range(2,2*10**6):
    p=0
    for j in range(i*i,2*10**6,i):
        p+=l[j]
    if p>1:
        f(a)
        exit()
print("pairwise coprime")

Submission status: Wrong Answer

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import accumulate, permutations, combinations, product, groupby, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
A = LIST()

if reduce(gcd, A) != 1:
    print("not coprime")
    exit()

def primes_for(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, n + 1):
        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]]

l = primes_for(int(max(A)**(1/2))+1)
s = set()
for x in l:
    if x != 1:
        if x in s:
            print("setwise coprime")
            exit()
        else:
            s.add(x)
    cnt = 0
    for y in A:
        if y%x == 0:
            cnt += 1
    if cnt >= 2:
        print("setwise coprime")
        break
else:
    print("pairwise coprime")

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    input = sys.stdin.buffer.readline
    from math import gcd
    N = int(input())
    A = list(map(int, input().split()))
    g = A[0]

    # import numpy as np

    # def seachPrimeNum(N):
    #     max = int(np.sqrt(N))
    #     seachList = [i for i in range(2, N+1)]
    #     primeNum = []
    #     while seachList[0] <= max:
    #         primeNum.append(seachList[0])
    #         tmp = seachList[0]
    #         seachList = [i for i in seachList if i % tmp != 0]
    #     primeNum.extend(seachList)
    #     return primeNum

    def factorization(n):
        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
                ret.add(i)
        if temp != 1:
            ret.add(temp)

        if len(ret) == 0 and n != 1:
            ret.add(n)

        return ret

    # primes = set(seachPrimeNum(max(A)))

    s = factorization(A[0])

    ls = len(s)
    flag = True
    for x in A[1:]:
        g = gcd(g, x)
        if flag:
            for y in s:
                if x % y == 0:
                    flag = False
            s != factorization(x)

    if flag:
        print("pairwise coprime")
    elif g == 1:
        print("setwise coprime")

    else:
        print("not coprime")


main()

Submission status: Wrong Answer

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

N = int(input())
A = list(map(int, input().split()))
P = 10 ** 9 + 7
"""
lcm = 1
flg = True
for a in A:
    if gcd(lcm, a) != 1:
        flg = False
        break
    lcm = (lcm*a)%P
if flg:
    print('pairwise coprime')
    sys.exit()
"""

gcd_ = A[0]
for a in A[1:]:
    gcd_ = gcd(gcd_, a)
    if gcd_ == 1:
        print('setwise coprime')
        sys.exit()

print('not coprime')

Submission status: Wrong Answer

Solution code:
def egcd(a, b):
    if a == 0:
        return b
    else:
        g= egcd(b % a, a)
        return g

N=int(input())
A=list(map(int, input().split()))
n=N//2
m=((N//2)-(N+1)%2)
L1=[0]*n
L2=[0]*m

for i in range(n):
    L1[i]=egcd(A[2*i],A[2*i+1])
for j in range(m):
    L2[j]=egcd(A[2*j+1],A[2*j+2])
# print(L1)
# print(L2)

if all(L1[i]==1 for i in range(n)) and all(L2[j]==1 for j in range(m)):
    print('pairwise coprime')
    exit()

if N%2==1:
    L1.append(A[-1])
while len(L1)>1:
    l=len(L1)//2
    tmp=[0]*l
    for i in range(l):
        tmp[i]=egcd(L1[2*i],L1[2*i+1])
    if len(L1)%2==1:
        tmp.append(L1[-1])
    L1=tmp

if L1[0]==1:
    print('setwise 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 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 == [] and n != 1:
        arr.append([n, 1])

    return arr


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

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

for ai in a:
    for d, _ in factorization(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:
import math
N = int(input())
A = list(map(int, input().split()))
A.sort()
ans = 0
holdGcd = math.gcd(A[0], A[1])
pairwise = 1
setwise = 1
for i in range(N):
    cnt = 1
    for j in range(i+1,N):
        if A[i] > A[i+cnt]:
            continue
        holdGcd = math.gcd(holdGcd, A[i+cnt])
        break
    if holdGcd != 1:
        pairwise = 0

if holdGcd != 1:
    setwise = 0

if pairwise == 1:
    print('pairwise coprime')
elif setwise == 1:
    print('setwise coprime')
else:
    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 = [i for i in LI() if i != 1] 
    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 coprime")
        return
    g = a[0]
    for i in a:
        g = math.gcd(g, i)
    if g == 1:
        print("setwise coprime")
        return
    print("not coprime")
    
    return


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

Submission status: Wrong Answer

Solution code:
gcd=lambda x,y:gcd(y,x%y) if y!=0 else x
def f(a):
    p=a[0]
    for i in range(1,len(a)):
        p=gcd(p,a[i])
    if p==1:
        print("setwise coprime")
    else:
        print("not coprime")

n=int(input())
a=list(map(int,input().split()))
l=[0 for i in range(2*10**6)]
for i in a:
    l[i]+=1
for i in range(2,2*10**6):
    p=0
    for j in range(2*i,2*10**6,i):
        p+=l[j]
    if p>1:
        f(a)
        exit()
print("pairwise coprime")

Submission status: Wrong Answer

Solution code:
import math
n = int(input())
lis = list(map(int,input().split()))
lis.sort()
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
        if nu != 1:
            exist[nu] = 1
print("pairwise coprime")

Submission status: Wrong Answer

Solution code:
import math
# 素数判定関数
def isPrime(num):
    # 2未満の数字は素数ではない
    if num < 2: return False
    # 2は素数
    elif num == 2: return True
    # 偶数は素数ではない
    elif num % 2 == 0: return False

    # 3 ~ numまでループし、途中で割り切れる数があるか検索
    # 途中で割り切れる場合は素数ではない
    for i in range(3, math.floor(math.sqrt(num))+1, 2):
        if num % i == 0:
            return False
    # 素数
    return True
# 素数判定
def callIsPrime(input_num=1000):
    numbers = []
    # ループしながら素数を検索する
    for i in range(1, input_num):
        if isPrime(i):
            numbers.append(i)

    # 素数配列を返す
    return numbers

N=int(input())
A=[int(x) for x in input().split()]
result="pairwise coprime"
for i in callIsPrime(min(1000,max(A))):
  on=0
  off=0
  for a in A:
    if a%i==0:
      on+=1
    elif a%i!=0:
      off+=1
    if on>=2 and off>=1:
      break
  if on>=2 and off==0:
    result="not coprime"
    break
  elif on>=2:
    result="setwise coprime"
print(result)