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
mod=10**9+7 ; inf=float("inf")
from math import sqrt, ceil
from collections import deque, Counter, defaultdict #すべてのkeyが用意されてる defaultdict(int)で初期化
input=lambda: sys.stdin.readline().strip()
sys.setrecursionlimit(11451419)
from decimal import ROUND_HALF_UP,Decimal  #変換後の末尾桁を0や0.01で指定
  #Decimal((str(0.5)).quantize(Decimal('0'), rounding=ROUND_HALF_UP))
from functools import lru_cache
from bisect import bisect_left as bileft, bisect_right as biright
#メモ化再帰defの冒頭に毎回 @lru_cache(maxsize=10**10)
#引数にlistはだめ
#######ここまでテンプレ#######
#ソート、"a"+"b"、再帰ならPython3の方がいい
#######ここから天ぷら########

n=int(input())

A=list(map(int,input().split()))
from math import sqrt
def eratosu(n):
  if not isinstance(n,int):
    raise TypeError("nがint型になってねえぞ")
  if n<2:
    raise ValueError('nが2よりちっちぇえぞ')
  prime = []
  limit = sqrt(n)
  data = [i+1 for i in range(1, n)]  #2,3,4,...,n
  while True:
    p = data[0]
    if limit <= p:
        return prime + data
    prime.append(p)
    data = [e  for e in data if e % p != 0]
PRIME=eratosu(10**3+10)
@lru_cache(maxsize=10**10)
def bunkai(n):
    ans=[]
    temp=n
    #そんな早くしなくてよかったり、何回もするわけじゃないなら、
    #for i in range(2,int(sqrt(n))+1): とかで
    primelist= PRIME
    for i in primelist:
        if i>sqrt(n):break
        if temp % i ==0:
            ji=0
            while temp%i==0:
                ji+=1
                temp//=i
            ans.append([i,ji])
    if ans==[]:return([[n,1]])  #素数のとき
    if temp!=1:
        ans.append([temp,1])  #4*5882353とか
    return ans

flag=1
seen=[0]*(10**6+1)
#print(bunkai(3))

for p in PRIME:
    for num in A:
        if num%p==0:
            if seen[p]!=0:flag=0
            seen[p]+=1
        

if flag:
    print("pairwise coprime")
elif max(seen)!=n:
    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()
k = math.gcd(a[0],a[1]) #最大公約数
m = a[0]*a[1]//math.gcd(a[0],a[1]) #最小公倍数
j = a[0]*a[1]#漱石

for i in range(2,n):
    j*=a[i]
    m = m*a[i]//math.gcd(a[i],m)
    k = math.gcd(k,a[i])
    
if(k==1):
    if(m==j):
        print("setwise coprime")
    else:
        print("pairwise coprime")
else:
    print("not coprime")

Submission status: Wrong Answer

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


def II():
    return int(sys.stdin.readline())


def MI():
    return map(int, sys.stdin.readline().split())


def LI():
    return list(map(int, sys.stdin.readline().split()))


def main():
    N = II()
    targets = LI()
    MAX_INT = max(targets)
    targets = set(targets)
    is_pw = True

    for i in range(2, MAX_INT):
        origin = i
        kosuu = 0
        while origin <= MAX_INT:
            if origin in targets:
                kosuu += 1
            origin += i

        if kosuu <= 1:
            continue
        elif kosuu < N:
            is_pw = False
        else:
            print("not coprime")
            return

    if is_pw:
        print("pairwise coprime")
        return
    print("setwise coprime")


main()

Submission status: Wrong Answer

Solution code:
import sys
import math

n = int(input())
a = sorted(map(int,input().split()), reverse =True)

ans = a[0]
for i in range(1, n):
    ans = ans * a[i] // math.gcd(ans, a[i])
    
if ans != 1:
  print("not coprime")
  sys.exit()

#print(a)
for i in range(n):
  for j in range(i+1,n):
    if (math.gcd(a[i],a[j]) != 1): 
      	print("setwise coprime")
      	sys.exit()

print("pairwise coprime")

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
#from heapq import heappop, heappush
from collections import defaultdict
sys.setrecursionlimit(10**7)
import math
#from itertools import product, accumulate, combinations, product
#import bisect
#import numpy as np
#from copy import deepcopy
#from collections import deque
#from decimal import Decimal
#from numba import jit

INF = 1 << 50
EPS = 1e-8
mod = 10 ** 9 + 7

class factorials:
    '''
    args:
      n : max val when exploring factorials
    '''
    def __init__(self, n):
        self.n = 1# factorials to be searched
        self.factorials = set()
        self.update_factorials(n)

    def update_factorials(self, n):
        if self.n >= n:
            return None
        for i in range(self.n+1, n+1):
            done = False
            limit = int(i ** 0.5)
            for j in self.factorials:
                if j > limit: break
                if not i % j:
                    done = True
                    break
            if not done:
                self.factorials.add(i)
        self.n = n
        return None

    def factorials_set(self):
        return self.factorials

    def check_fact(self, x):
        if x > self.n**2:
            self.update_factorials(int(x ** 0.5)+1)
        MAX = int(math.sqrt(x))
        for f in self.factorials:
            if f > MAX:break
            if not x % f:
                return False
        return True

    def prime_factorization(self, val, divisors=None):
        # divisors : default-dict of divisors. Should be specified only if appended vals are required
        max_n = int(math.sqrt(val))
        if self.n < max_n:
            self.update_factorials(max_n)
        if divisors == None:
            divisors = defaultdict(lambda: 0)
        for f in self.factorials:
            if f > val: break
            while True:
                if not val % f:
                    divisors[f] += 1
                    val //= f
                else:
                    break
        if val > 1:
            divisors[val] += 1
        return divisors

def run():
    N, *A = map(int, read().split())
    MAX = max(A)
    nn = int(MAX ** 0.5)
    FACT = factorials(nn)
    FACT_SET = FACT.factorials_set()
    #print(FACT_SET)
    fact_get = set()
    done = False
    for a in A:
        #print(a, fact_get)
        if done: break
        for f in FACT_SET:
            if not a % f:
                if f in fact_get:
                    done = True
                    break
                fact_get.add(f)
                while not a % f:
                    a //= f
        if a > 1:
            fact_get.add(a)
    if not done:
        print('pairwise coprime')
        return

    SETWISE = False
    setwise_fact = set()
    mina = min(A)
    for f in FACT_SET:
        if not mina % f:
            setwise_fact.add(f)
            while not mina % f:
                mina //= f
    if mina > 1:
        setwise_fact.add(mina)

    for a in A:
        remlist = []
        if len(setwise_fact) == 0:
            print('setwise coprime')
            return
        for f in setwise_fact:
            if not a % f:
                continue
            else:
                remlist.append(f)
        for f in remlist:
            setwise_fact.remove(f)
        #print(a, setwise_fact)
    if len(setwise_fact) == 0:
        print('setwise coprime')
        return


    print('not coprime')



if __name__ == "__main__":
    run()

Submission status: Wrong Answer

Solution code:
import sys, math
from functools import lru_cache
import numpy as np
sys.setrecursionlimit(10**9)
MOD = 10**9+7

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

def mi():
    return map(int, input().split())

def ii():
    return int(input())

def i2(n):
    tmp = [list(mi()) for i in range(n)]
    return [list(i) for i in zip(*tmp)]


def lcm(a, b):
    return a*b//math.gcd(a, b)


def main():
    N = ii()
    A = np.array(list(mi()))

    l = 1
    p = 1
    for a in A:
        l = np.lcm(l, a)
        p *= a
        l %= MOD
        p %= MOD

    g = np.gcd.reduce(A)

    if g > 1:
        print('not coprime')
    elif l == p:
        print('pairwise coprime')
    else:
        print('setwise coprime')

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
import heapq
import math
import fractions
import functools
import bisect
import itertools
from collections import Counter
from collections import deque
from operator import itemgetter
def input(): return sys.stdin.readline().strip()
def mp(): return map(int,input().split())
def lmp(): return list(map(int,input().split()))

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

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

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

    return arr

p=[0]*10**6
N=int(input())
A=sorted(lmp())

for i in A:
    l=factorization(i)
    for k in l:

        p[k[0]]+=1
for i in p:
    if i==N:
        print("not coprime")
        exit()

    if i>=2:
        print("setwise coprime")
        exit()
print("pairwise 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) :
	if (n <= 1) : 
		return False
	if (n <= 3) : 
		return True
	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
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
s=set()
z=list(l)
for i in range(n-1,-1,-1):
	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:
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()]

from collections import Counter

c = Counter(a)

for i in a:
    if c[i] > 1 and i != 1:
        print('not coprime')
        sys.exit()

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:
import math
n = int(input())
a = [int(i) for i in input().split()]

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

for i in range(n):
    if chk[a[i]] == 1 and a[i] >= 2:
        print("not coprime")
        exit()
    chk[a[i]] += 1

flag = True

for i in range(2,10**6+1):
    #tmp = i
    kake = 2
    num = 0
    #print(i)
    while i * kake <= 10**6:
        #print(i)
        if chk[i*kake] == 1:
            if num == 1:
                flag = False
                break
            num = 1
            #break
        kake += 1
gcd_num = math.gcd(a[0],a[1])
        
for i in range(n-2):
    gcd_num = math.gcd(gcd_num,a[i+2])
    
if flag == True:
    print("pairwise coprime")
elif gcd_num == 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)))
used = set()

def factorize(n):
    for prime in primes:
        if prime in used:
            continue
        if n == 1 or prime > n:
            break
        while n % prime == 0:
            n //= prime
            used.add(prime)

    if n > 1:
        return False
    return True

is_pairwise = True
prod = 1
all_gcd = A[0]
for a in A:
    all_gcd = math.gcd(all_gcd, a)
    if is_pairwise:
        if not factorize(a):
            is_pairwise = False

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

Submission status: Wrong Answer

Solution code:
def eratosthenes(mx, arr):
    sss = set(arr)
    if len(arr) > len(sss):
        print('not coprime')
        return
    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 > 1:
            pair_wise = False
        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 = list(map(int, input().split()))

    eratosthenes(max(a), a)

if __name__ == "__main__":
    resolve()

Submission status: Wrong Answer

Solution code:
import math

def main():
    N = int(input())
    A = list(map(int, input().split()))
    A = list(set(A))
    cnt = 0
    allgcd = A[0]
    for a in A:
        allgcd = math.gcd(allgcd, a)
        if a % 2 == 0:
            cnt += 1
    if allgcd != 1:
        return "not coprime"
    
    if cnt >= 2:
        return "setwise coprime"

    allprime = set()
    for a in A:
        N = a
        prime, i = set(), 1
        while i * i <= N:
            if N % i == 0:
                prime.add(i)
                prime.add(N//i)
                if i in allprime or (N//i) in allprime:
                    return "setwise coprime"
                if i > 1:
                    allprime.add(i)
                allprime.add(N//i)
            i += 1
    return "pairwise coprime"

print(main())

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(min(1000,n)):
        for j in range(max((n-1000),i),n):
            if math.gcd(a[i],a[j])!=1:
                print('setwise coprime')
                exit()
    print('pairwise coprime')

Submission status: Wrong Answer

Solution code:
import math
def prime_numbers(x):
    if x < 2:
        return []
    prime_numbers = [i for i in range(x)]
    prime_numbers[1] = 0
    for prime_number in prime_numbers:
        if prime_number > math.sqrt(x):
            break
        if prime_number == 0:
            continue
        for composite_number in range(2 * prime_number, x, prime_number):
            prime_numbers[composite_number] = 0
    return [prime_number for prime_number in prime_numbers if prime_number != 0]
def soinnsuu(x):
    s = set()
    for i in primes:
        if i > int(math.sqrt(x)):
            break
        elif x % i == 0:
            while x % i == 0:
                x //= i
            s.add(i)
    s.add(x)
    return s
from math import gcd
n = int(input())
a = list(map(int, input().split()))
g = 0
for i in range(n):
    g = gcd(g, a[i])
primes = prime_numbers(1000000)
cur = soinnsuu(a[0])
f = False
for i in range(1, n):
    s2 = soinnsuu(a[i])
    if len(cur & s2) != 0:
        f = True
        break
    cur |= s2
if not f:
    print("pairwise coprime")
elif g == 1:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6)


def main(input, print):
    N = int(input())
    A = list(map(int, input().split()))
    A = sorted(A)
    m = A[0]
    table = [0] * m
    for i in range(2, m):
        for j in range(N):
            if A[j] % i == 0:
                table[i] += 1
        if table[i] == N:
            print('not coprime')
            return
        if table[i] > 1:
            print('setwise coprime')
            return
    print('pairwise coprime')


if __name__ == '__main__':
    main(sys.stdin.readline, print)

Submission status: Wrong Answer

Solution code:
# Python3 implementation of the approach 
MAXN = 1000001

# Stores smallest prime factor for 
# every number 
spf = [i for i in range(MAXN)] 

# Hash to store prime factors count 
hash1 = [0 for i in range(MAXN)] 

# Function to calculate SPF (Smallest 
# Prime Factor) for every number till MAXN 
def sieve(): 

	# Separately marking spf for 
	# every even number as 2 
	for i in range(4, MAXN, 2): 
		spf[i] = 2

	# Checking if i is prime 
	for i in range(3, MAXN): 

		if i * i < MAXN: 
			break

		# Marking SPF for all numbers 
		# divisible by i 
		if (spf[i] == i): 
			for j in range(i * i, MAXN, i): 

				# Marking spf[j] if it is not 
				# previously marked 
				if (spf[j] == j): 
					spf[j] = i 

# Function to store the prime factors 
# after dividing by the smallest prime 
# factor at every step 
def getFactorization(x): 

	while (x != 1): 
		temp = spf[x] 
		if (x % temp == 0): 

			# Storing the count of 
			# prime factors in hash 
			hash1[spf[x]] += 1
			x = x // spf[x] 

		while (x % temp == 0): 
			x = x // temp 
	

# Function that returns true if there is 
# an element in the array which is coprime 
# with all the other elements of the array 
def hasValidNum(arr, n): 

	# Using sieve for generating 
	# prime factors 
	sieve() 

	for i in range(n): 
		getFactorization(arr[i]) 

	for i in hash1:
		if(i>1):
			return False
	return True

def gcd(a,b): 
    if (b == 0): 
         return a 
    return gcd(b, a%b) 

n=int(input())
arr=list(map(int,input().split()))
if (hasValidNum(arr, n)): 
	print("pairwise coprime") 
else: 
	g=arr[0]
	for i in range(1,n):
		g=gcd(g,arr[i])
	if(g==1):
		print("setwise coprime") 
	else:
		print("not coprime")

Submission status: Wrong Answer

Solution code:
# coding: utf-8
from math import gcd
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

# 関数の呼び出し
prime_list = callIsPrime(10**3)

N=int(input())
A=list(map(int,input().split()))
prime_flg = [True for i in range(10**3)]
pc_flg=True

if len(A)!=len(set(A)):
    pc_flg=False

x = A[-1]

#for i in range(N):
#    x=gcd(x,A[i])

A = list(set(A))
A.sort()

for i in range(len(A)):
    for j in range(len(prime_list)):
        p=prime_list[j]
        if A[i]%p == 0:
            if prime_flg[p]:
                prime_flg[p]=False
            else:
                pc_flg=False


if pc_flg:
    print("pairwise coprime")
else:
    print("not coprime")

Submission status: Wrong Answer

Solution code:
import sys
from math import gcd
input=sys.stdin.readline
#sys.setrecursionlimit(10**6)

def Ed(num,ycnt):
    ycnt[num]+=1
    for i in range(2,int(num**0.5)+1):
        if num%i==0:
            ycnt[i]+=1
            if num//i!=i:
                ycnt[num//i]+=1

def main():
    input()
    a=[int(i) for i in input().split()]

    ycnt=[0]*(10**6+1)
    gsum=a[0]

    for i in a:
        gsum=gcd(gsum,i)
        Ed(i,ycnt)
    #print(ycnt[:max(a)+1])
    if max(ycnt)<2:
        print("pairwise coprime")
    elif gsum==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()))
MOD = 10 ** 9 + 7

g = A[0]
l = A[0]
prod = A[0]
for i in range(1, N):
	g = gcd(g, A[i])
	l = ((l * A[i]) // g) % MOD
	prod = (prod * A[i]) % MOD
	
if g != 1:
	print("not coprime")
else:
	if l == prod:
		print("pairwise coprime")
	else:
		print("setwise coprime")

Submission status: Wrong Answer

Solution code:
from math import gcd

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

g = a[0]
for i in range(1, n):
    g = gcd(g, a[i])
    if g == 1:
        break
else:
    print('not coprime')
    exit()

ind = [-1] * (10**6)

prime = [2, 3, 5, 7]
for i in range(11, 10 ** 6, 2):
    j = 0
    flag = True
    while prime[j] * prime[j] <= i:
        if i % prime[j] == 0:
            flag = False
            break
        else:
            j += 1
    if flag:
        prime.append(i)

for i in range(len(prime)):
    ind[prime[i]] = i

# len(prime) = 78498

tf = [False] * len(prime)

for i in a:
    for j in range(len(prime)):
        if prime[j] * prime[j] > i:
            if tf[ind[i]]:
                print('setwise coprime')
                exit()
            tf[ind[i]] = True
            break

        if i % prime[j] == 0:
            if tf[j]:
                print('setwise coprime')
                exit()

            tf[j] = True
            while i % prime[j] == 0:
                i //= prime[j]

print('pairwise coprime')

Submission status: Wrong Answer

Solution code:
import math
mod = 10 ** 9 + 7

n = int(input())
a = [int(i) for i in input().split()]
set_v = a[0]
pairwise = True
cnt = 0
for i in range(1, n):
    set_v = math.gcd(set_v, a[i])
    if set_v == 1:
        cnt += 1
if cnt == n - 1:
    ans = 'pairwise coprime'
elif set_v == 1:
    ans = 'setwise coprime'
else:
    ans = 'not coprime'
print(ans)

Submission status: Wrong Answer

Solution code:
def prime(n):
    nums = [True]*n
    primes = []
    for i in range(2,n):
        if nums[i]:
            primes.append(i)
            for j in range(2*i,n,i):
                nums[j] = False
    return primes

def main():
    n = int(input())
    A = set(map(int,input().split()))
    Amax = max(A)

    primes = set(prime(Amax+1))
    ct = 0
    for p in primes:
        g = set(())
        temp = p
        while temp <= Amax:
            g.add(temp)
            temp+=p
        
        k = len(g & A)
        if k > ct:
            ct = k
    
    if ct == n:
        print("not coprime")
    elif ct == 1:
        print("pairwise coprime")
    else:
        print("setwise coprime")
main()

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()))
if 1 in a:
    print("not coprime")
    exit()
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:
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('setwise coprime')
else:
    print('not coprime')

Submission status: Wrong Answer

Solution code:
from math import gcd
def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]
p = primes(1000)
c = [0]*1001
# print(len(p))

n = int(input())
a = list(map(int,input().split()))
# a = [10**6]*10**6
g = 0
f = 1
c1 = 0
for i in a:
    g = gcd(g,i)
    if i == 1:
        c1 += 1
    if f == 1:
        for j in p:
            if i%j == 0:
                c[j] += 1
                if c[j] > 1:
                    f = 0
# print(c1)
if len(set(a))+max(0,c1-1) != 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())
A=list(map(int,input().split()))
ans=1
for i in range(N):
    ans*=A[i]
print(ans)

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 > 3 * (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:
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 = 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

from math import gcd
g = 0
for i in arr: g = gcd(g, i)

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