Problem:


Score : 500 points

Problem Statement

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

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

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

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

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

Constraints

2 \leq N \leq 10^6

1 \leq A_i\leq 10^6

Input

Input is given from Standard Input in the following format:

N
A_1 \ldots A_N

Output

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

Sample Input 1

3
3 4 5

Sample Output 1

pairwise coprime

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

Sample Input 2

3
6 10 15

Sample Output 2

setwise coprime

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

Sample Input 3

3
6 10 16

Sample Output 3

not coprime

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



Sample input:
3
3 4 5


Sample output:
pairwise coprime

Submission status: Wrong Answer

Solution code:
from bisect import *
from collections import *
from itertools import *
import functools
import sys
import math
from decimal import *
from copy import *
from heapq import *
from fractions import *
getcontext().prec = 30
MAX = sys.maxsize
MAXN = 1000010
MOD = 10**9+7
spf = [i for i in range(MAXN)]
spf[0]=-1
def sieve():
    for i in range(2,MAXN,2):
        spf[i] = 2
    for i in range(3,int(MAXN**0.5)+1):
        if spf[i]==i:
            for j in range(i*i,MAXN,i):
                if spf[j]==j:
                    spf[j]=i
def fib(n,m):
    if n == 0:
        return [0, 1]
    else:
        a, b = fib(n // 2)
        c = ((a%m) * ((b%m) * 2 - (a%m)))%m
        d = ((a%m) * (a%m))%m + ((b)%m * (b)%m)%m
        if n % 2 == 0:
            return [c, d]
        else:
            return [d, c + d]
 
def charIN(x= ' '):
    return(sys.stdin.readline().strip().split(x))
 
def arrIN(x = ' '):
    return list(map(int,sys.stdin.readline().strip().split(x)))
 
def ncr(n,r):
    num=den=1
    for i in range(r):
        num = (num*(n-i))%MOD
        den = (den*(i+1))%MOD
 
    return (num*(pow(den,MOD-2,MOD)))%MOD
 
def flush():
    return sys.stdout.flush()




'''*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*'''
sieve()

n = int(input())
a = arrIN()
d = defaultdict(list)

for i in range(n):
    d[spf[a[i]]].append(i)

g = a[0]

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



for i in d.keys():
    if i!=1 and len(d[i])>1:
        if g!=1:
            print('not coprime')
        else:
            print('setwise coprime')
        break
else:
    print('pairwise coprime')

Submission status: Wrong Answer

Solution code:
import sys
readline = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
#mod = 998244353
INF = 10**18
eps = 10**-7


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


def gcdlist(l):
    a = l[0]
    for i in range(1,len(l)):
        a = gcd(a,l[i])
    return a

#nの素因数分解(O(n**0.5)
def prime_factor(n):
    ass = []
    for i in range(2,int(n**0.5)+1):
        while n%i == 0:
            ass.append(i)
            n = n//i
    if n != 1:
        ass.append(n)
    return ass

n = int(readline())
a = list(map(int,readline().split()))
a.sort()
check = [True]*(10**6+5)
p1 = True
for ai in a:
    if not p1:
        break
    dlist = prime_factor(ai)
    for d in dlist:
        if check[d]:
            check[d] = False
        else:
            p1 = False
            break

if p1:
    print("pairwise coprime")
else:
    p2 = gcdlist(a)
    if p2 == 1:
        print("setwise coprime")
    else:
        print("not coprime")

Submission status: Wrong Answer

Solution code:
from bisect import *
from collections import *
from itertools import *
import functools
import sys
import math
from decimal import *
from copy import *
from heapq import *
from fractions import *
getcontext().prec = 30
MAX = sys.maxsize
MAXN = 1000010
MOD = 10**9+7
spf = [i for i in range(MAXN)]
spf[0]=spf[1] = -1
def sieve():
    for i in range(2,MAXN,2):
        spf[i] = 2
    for i in range(3,int(MAXN**0.5)+1):
        if spf[i]==i:
            for j in range(i*i,MAXN,i):
                if spf[j]==j:
                    spf[j]=i
def fib(n,m):
    if n == 0:
        return [0, 1]
    else:
        a, b = fib(n // 2)
        c = ((a%m) * ((b%m) * 2 - (a%m)))%m
        d = ((a%m) * (a%m))%m + ((b)%m * (b)%m)%m
        if n % 2 == 0:
            return [c, d]
        else:
            return [d, c + d]
 
def charIN(x= ' '):
    return(sys.stdin.readline().strip().split(x))
 
def arrIN(x = ' '):
    return list(map(int,sys.stdin.readline().strip().split(x)))
 
def ncr(n,r):
    num=den=1
    for i in range(r):
        num = (num*(n-i))%MOD
        den = (den*(i+1))%MOD
 
    return (num*(pow(den,MOD-2,MOD)))%MOD
 
def flush():
    return sys.stdout.flush()




'''*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*'''
sieve()

n = int(input())
a = arrIN()
d = defaultdict(list)

for i in range(n):
    d[spf[a[i]]].append(i)

g = a[0]

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



for i in d.keys():
    if len(d[i])>1:
        if g!=1:
            print('not coprime')
        else:
            print('setwise coprime')
        break
else:
    print('pairwise coprime')

Submission status: Wrong Answer

Solution code:
def sieve(n):
  is_prime = [True for _ in range(n+1)]
  is_prime[0] = False
  for i in range(2, n+1):
    if is_prime[i-1]:
      j = 2 * i
      while j <= n:
        is_prime[j-1] = False
        j += i
  table = [i for i in range(1, n+1) if is_prime[i-1]]
  return table

N = int(input())
A = list(map(int, input().split()))
Amax = max(A)
lis = [0]*(Amax+1)
for i in range(N):
  lis[A[i]] += 1
table = sieve(Amax)
setwise = False
for t in table:
  p = t
  cnt = 0
  while p<=Amax:
    cnt += lis[p]
    p += t
  if cnt==N:
    print('not comprime')
    break
  if 2<=cnt<N:
    setwise=True
else:
  if setwise==True:
    print('setwise coprime')
  else:
    print('pairwise coprime')

Submission status: Wrong Answer

Solution code:
import math

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

def prime(n):
    p = []
    flag = [True] * (n - 1)
    for i in range(n - 1):
        if flag[i] == True:
            p.append(i + 2)
            num = i
            while num <= n - 2:
                flag[num] = False
                num += i + 2
    return p

p = prime(1000)
flags = [0 for i in range(len(p))]
flag = True
gcd = 0
for i in range(n):
    gcd = math.gcd(gcd, a[i])
if gcd != 1:
    print("not coprime")
else:
    if len(set(a)) != n:
        print("setwise coprime")
    else:
        for i in range(n):
            for j in range(len(p)):
                if a[i] % p[j] == 0:
                    flags[j] += 1
        if max(flags) >= 2:
            print("setwise coprime")
        else:
            print("pairwise coprime")

Submission status: Wrong Answer

Solution code:
from math import gcd
N=int(input())
A=list(map(int, input().split()))

gcda=A[0]
gcdais=True
gcdb=A[0]

for i in range(1,N):
    a=A[i]
    if gcd(gcda, a)!=1:
        gcdais=False
    gcda=a

    gcdb=gcd(gcdb, a)

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

Submission status: Wrong Answer

Solution code:
import sys
from math import gcd
input = sys.stdin.buffer.readline

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


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

p = primes(1003)

g = a[0]
for e in a:
    g = gcd(g,e)

if g != 1:
    print("not coprime")
else:
    a.sort()
    if a[0] == a[-1] and a[0] == 1:
        print("pairwise coprime")
    else:
        s = set()
        for e in a:
            for d in p:
                if e%d == 0:
                    if d in s:
                        print("setwise coprime")
                        exit()
                    s.add(d)
            s.add(e)
        print("pairwise coprime")

Submission status: Wrong Answer

Solution code:

import sys
input = sys.stdin.buffer.readline
from math import gcd

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

# Mまでの素数全列挙(エラトステネスの篩)
def primes(M):
    B = set(A)
    ok = True
    is_prime = [-1 for _ in range(M+1)]
    for m in range(2, M+1):
        if is_prime[m] == -1:
            is_prime[m] = 1
            cnt = 0
            if m in B: cnt += 1
            l = 2
            while m*l <= M:
                if m*l in B:
                    cnt += 1
                is_prime[m*l] = 0
                l += 1
            if cnt > 1:
                ok = False
                break
    return ok

def check():
    k = A[0]
    for a in A:
        k = gcd(a, k)
    return k == 1

if primes(10**6):
    ans = "pairwise coprime"
elif check():
    ans = "setwise coprime"
else:
    ans = "not coprime"
print(ans)

Submission status: Wrong Answer

Solution code:
import sys; input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**7)
from collections import defaultdict
con = 10 ** 9 + 7; INF = float("inf")

from math import gcd

def getlist():
	return list(map(int, input().split()))

#処理内容
def main():
	N = int(input())
	A = getlist()
	GCD = A[0]
	for i in range(N):
		GCD = gcd(GCD, A[i])

	if GCD != 1:
		print("not coprime")
		return

	B = []
	for i in A:
		if i != 1:
			B.append(i)

	B = list(set(B))
	M = len(B)
	if M <= 10 ** 3:
		for i in range(M):
			for j in range(i + 1, M):
				if gcd(B[i], B[j]) != 1:
					print("setwise coprime")
					return
		print("pairwise coprime")
	else:
		print("setwise coprime")

if __name__ == '__main__':
	main()

Submission status: Wrong Answer

Solution code:
from math import gcd
N = int(input())
A = list(map(int, input().split()))

pc = True
g = A[0]
for i in range(1, N):
    if gcd(A[i], A[i-1]) > 1:
        pc = False
    g = gcd(g, A[i])

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

Submission status: Wrong Answer

Solution code:
# ---------------------------iye ha aam zindegi---------------------------------------------
import math
import random
import heapq, bisect
import sys
from collections import deque, defaultdict
from fractions import Fraction
import sys
#import threading
from collections import defaultdict
#threading.stack_size(10**8)
mod = 10 ** 9 + 7
mod1 = 998244353

# ------------------------------warmup----------------------------
import os
import sys
from io import BytesIO, IOBase
sys.setrecursionlimit(300000)

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")


# -------------------game starts now----------------------------------------------------import math
class TreeNode:
    def __init__(self, k, v):
        self.key = k
        self.value = v
        self.left = None
        self.right = None
        self.parent = None
        self.height = 1
        self.num_left = 1
        self.num_total = 1


class AvlTree:

    def __init__(self):
        self._tree = None

    def add(self, k, v):
        if not self._tree:
            self._tree = TreeNode(k, v)
            return
        node = self._add(k, v)
        if node:
            self._rebalance(node)

    def _add(self, k, v):
        node = self._tree
        while node:
            if k < node.key:
                if node.left:
                    node = node.left
                else:
                    node.left = TreeNode(k, v)
                    node.left.parent = node
                    return node.left
            elif node.key < k:
                if node.right:
                    node = node.right
                else:
                    node.right = TreeNode(k, v)
                    node.right.parent = node
                    return node.right
            else:
                node.value = v
                return

    @staticmethod
    def get_height(x):
        return x.height if x else 0

    @staticmethod
    def get_num_total(x):
        return x.num_total if x else 0

    def _rebalance(self, node):

        n = node
        while n:
            lh = self.get_height(n.left)
            rh = self.get_height(n.right)
            n.height = max(lh, rh) + 1
            balance_factor = lh - rh
            n.num_total = 1 + self.get_num_total(n.left) + self.get_num_total(n.right)
            n.num_left = 1 + self.get_num_total(n.left)

            if balance_factor > 1:
                if self.get_height(n.left.left) < self.get_height(n.left.right):
                    self._rotate_left(n.left)
                self._rotate_right(n)
            elif balance_factor < -1:
                if self.get_height(n.right.right) < self.get_height(n.right.left):
                    self._rotate_right(n.right)
                self._rotate_left(n)
            else:
                n = n.parent

    def _remove_one(self, node):
        """
        Side effect!!! Changes node. Node should have exactly one child
        """
        replacement = node.left or node.right
        if node.parent:
            if AvlTree._is_left(node):
                node.parent.left = replacement
            else:
                node.parent.right = replacement
            replacement.parent = node.parent
            node.parent = None
        else:
            self._tree = replacement
            replacement.parent = None
        node.left = None
        node.right = None
        node.parent = None
        self._rebalance(replacement)

    def _remove_leaf(self, node):
        if node.parent:
            if AvlTree._is_left(node):
                node.parent.left = None
            else:
                node.parent.right = None
            self._rebalance(node.parent)
        else:
            self._tree = None
        node.parent = None
        node.left = None
        node.right = None

    def remove(self, k):
        node = self._get_node(k)
        if not node:
            return
        if AvlTree._is_leaf(node):
            self._remove_leaf(node)
            return
        if node.left and node.right:
            nxt = AvlTree._get_next(node)
            node.key = nxt.key
            node.value = nxt.value
            if self._is_leaf(nxt):
                self._remove_leaf(nxt)
            else:
                self._remove_one(nxt)
            self._rebalance(node)
        else:
            self._remove_one(node)

    def get(self, k):
        node = self._get_node(k)
        return node.value if node else -1

    def _get_node(self, k):
        if not self._tree:
            return None
        node = self._tree
        while node:
            if k < node.key:
                node = node.left
            elif node.key < k:
                node = node.right
            else:
                return node
        return None

    def get_at(self, pos):
        x = pos + 1
        node = self._tree
        while node:
            if x < node.num_left:
                node = node.left
            elif node.num_left < x:
                x -= node.num_left
                node = node.right
            else:
                return (node.key, node.value)
        raise IndexError("Out of ranges")

    @staticmethod
    def _is_left(node):
        return node.parent.left and node.parent.left == node

    @staticmethod
    def _is_leaf(node):
        return node.left is None and node.right is None

    def _rotate_right(self, node):
        if not node.parent:
            self._tree = node.left
            node.left.parent = None
        elif AvlTree._is_left(node):
            node.parent.left = node.left
            node.left.parent = node.parent
        else:
            node.parent.right = node.left
            node.left.parent = node.parent
        bk = node.left.right
        node.left.right = node
        node.parent = node.left
        node.left = bk
        if bk:
            bk.parent = node
        node.height = max(self.get_height(node.left), self.get_height(node.right)) + 1
        node.num_total = 1 + self.get_num_total(node.left) + self.get_num_total(node.right)
        node.num_left = 1 + self.get_num_total(node.left)

    def _rotate_left(self, node):
        if not node.parent:
            self._tree = node.right
            node.right.parent = None
        elif AvlTree._is_left(node):
            node.parent.left = node.right
            node.right.parent = node.parent
        else:
            node.parent.right = node.right
            node.right.parent = node.parent
        bk = node.right.left
        node.right.left = node
        node.parent = node.right
        node.right = bk
        if bk:
            bk.parent = node
        node.height = max(self.get_height(node.left), self.get_height(node.right)) + 1
        node.num_total = 1 + self.get_num_total(node.left) + self.get_num_total(node.right)
        node.num_left = 1 + self.get_num_total(node.left)

    @staticmethod
    def _get_next(node):
        if not node.right:
            return node.parent
        n = node.right
        while n.left:
            n = n.left
        return n


# -----------------------------------------------binary seacrh tree---------------------------------------
class SegmentTree:
    def __init__(self, data, default=0, func=lambda a, b: a+b):
        """initialize the segment tree with data"""
        self._default = default
        self._func = func
        self._len = len(data)
        self._size = _size = 1 << (self._len - 1).bit_length()

        self.data = [default] * (2 * _size)
        self.data[_size:_size + self._len] = data
        for i in reversed(range(_size)):
            self.data[i] = func(self.data[i + i], self.data[i + i + 1])

    def __delitem__(self, idx):
        self[idx] = self._default

    def __getitem__(self, idx):
        return self.data[idx + self._size]

    def __setitem__(self, idx, value):
        idx += self._size
        self.data[idx] = value
        idx >>= 1
        while idx:
            self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
            idx >>= 1

    def __len__(self):
        return self._len

    def query(self, start, stop):
        if start == stop:
            return self.__getitem__(start)
        stop += 1
        start += self._size
        stop += self._size

        res = self._default
        while start < stop:
            if start & 1:
                res = self._func(res, self.data[start])
                start += 1
            if stop & 1:
                stop -= 1
                res = self._func(res, self.data[stop])
            start >>= 1
            stop >>= 1
        return res

    def __repr__(self):
        return "SegmentTree({0})".format(self.data)

# -------------------------------iye ha chutiya zindegi-------------------------------------
class Factorial:
    def __init__(self, MOD):
        self.MOD = MOD
        self.factorials = [1, 1]
        self.invModulos = [0, 1]
        self.invFactorial_ = [1, 1]

    def calc(self, n):
        if n <= -1:
            print("Invalid argument to calculate n!")
            print("n must be non-negative value. But the argument was " + str(n))
            exit()
        if n < len(self.factorials):
            return self.factorials[n]
        nextArr = [0] * (n + 1 - len(self.factorials))
        initialI = len(self.factorials)
        prev = self.factorials[-1]
        m = self.MOD
        for i in range(initialI, n + 1):
            prev = nextArr[i - initialI] = prev * i % m
        self.factorials += nextArr
        return self.factorials[n]

    def inv(self, n):
        if n <= -1:
            print("Invalid argument to calculate n^(-1)")
            print("n must be non-negative value. But the argument was " + str(n))
            exit()
        p = self.MOD
        pi = n % p
        if pi < len(self.invModulos):
            return self.invModulos[pi]
        nextArr = [0] * (n + 1 - len(self.invModulos))
        initialI = len(self.invModulos)
        for i in range(initialI, min(p, n + 1)):
            next = -self.invModulos[p % i] * (p // i) % p
            self.invModulos.append(next)
        return self.invModulos[pi]

    def invFactorial(self, n):
        if n <= -1:
            print("Invalid argument to calculate (n^(-1))!")
            print("n must be non-negative value. But the argument was " + str(n))
            exit()
        if n < len(self.invFactorial_):
            return self.invFactorial_[n]
        self.inv(n)  # To make sure already calculated n^-1
        nextArr = [0] * (n + 1 - len(self.invFactorial_))
        initialI = len(self.invFactorial_)
        prev = self.invFactorial_[-1]
        p = self.MOD
        for i in range(initialI, n + 1):
            prev = nextArr[i - initialI] = (prev * self.invModulos[i % p]) % p
        self.invFactorial_ += nextArr
        return self.invFactorial_[n]


class Combination:
    def __init__(self, MOD):
        self.MOD = MOD
        self.factorial = Factorial(MOD)

    def ncr(self, n, k):
        if k < 0 or n < k:
            return 0
        k = min(k, n - k)
        f = self.factorial
        return f.calc(n) * f.invFactorial(max(n - k, k)) * f.invFactorial(min(k, n - k)) % self.MOD


# --------------------------------------iye ha combinations ka zindegi---------------------------------
def powm(a, n, m):
    if a == 1 or n == 0:
        return 1
    if n % 2 == 0:
        s = powm(a, n // 2, m)
        return s * s % m
    else:
        return a * powm(a, n - 1, m) % m


# --------------------------------------iye ha power ka zindegi---------------------------------
def sort_list(list1, list2):
    zipped_pairs = zip(list2, list1)

    z = [x for _, x in sorted(zipped_pairs)]

    return z


# --------------------------------------------------product----------------------------------------
def product(l):
    por = 1
    for i in range(len(l)):
        por *= l[i]
    return por


# --------------------------------------------------binary----------------------------------------
def binarySearchCount(arr, n, key):
    left = 0
    right = n - 1

    count = 0

    while (left <= right):
        mid = int((right + left) / 2)

        # Check if middle element is
        # less than or equal to key
        if (arr[mid] <= key):
            count = mid + 1
            left = mid + 1

        # If key is smaller, ignore right half
        else:
            right = mid - 1

    return count


# --------------------------------------------------binary----------------------------------------
def countdig(n):
    c = 0
    while (n > 0):
        n //= 10
        c += 1
    return c
def binary(x, length):
    y = bin(x)[2:]
    return y if len(y) >= length else "0" * (length - len(y)) + y

def countGreater(arr, n, k):
    l = 0
    r = n - 1

    # Stores the index of the left most element
    # from the array which is greater than k
    leftGreater = n

    # Finds number of elements greater than k
    while (l <= r):
        m = int(l + (r - l) / 2)
        if (arr[m] >= k):
            leftGreater = m
            r = m - 1

        # If mid element is less than
        # or equal to k update l
        else:
            l = m + 1

    # Return the count of elements
    # greater than k
    return (n - leftGreater)


# --------------------------------------------------binary------------------------------------
n=int(input())
l=list(map(int,input().split()))
ma=max(l)
g=0
d=defaultdict(int)
for i in range(n):
    d[l[i]]+=1
    g=math.gcd(g,l[i])
if g>1:
    print("not co-prime")
    sys.exit(0)
prime=[0]*(ma+1)
f=0
for i in range(2,ma+1):
    if prime[i]==1:
        continue
    prime[i]=1
    ans=0
    for j in range(i,ma+1,i):
        ans+=d[j]
    if ans>1:
        f=1
        break
if f==1:
    print("setwise prime")
else:
    print("pairwise co-prime")

Submission status: Wrong Answer

Solution code:
import sys; input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**7)
from collections import defaultdict
con = 10 ** 9 + 7; INF = float("inf")

from math import gcd

def getlist():
	return list(map(int, input().split()))

#処理内容
def main():
	N = int(input())
	A = getlist()
	GCD = A[0]
	for i in range(N):
		GCD = gcd(GCD, A[i])

	if GCD != 1:
		print("not coprime")
		return

	B = []
	for i in A:
		if i != 1:
			B.append(i)

	B = list(set(B))
	M = len(B)
	if M <= 10 ** 3:
		for i in range(M):
			for j in range(i + 1, M):
				if gcd(B[i], B[j]) != 1:
					print("setwise coprime")
					return

	print("pairwise coprime")


if __name__ == '__main__':
	main()

Submission status: Wrong Answer

Solution code:
from math import gcd


def main():
    n = int(input())
    a = list(map(int, input().split()))
    ac_gcd = [a[-1] for _ in range(n)]
    for i in range(n - 2, -1, -1):
        ac_gcd[i] = gcd(a[i], ac_gcd[i + 1])
    if set(ac_gcd[:-1]) == {1}:
        print("pairwise coprime")
    elif ac_gcd[0] == 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()))
t = set(a)
if len(t) != len(a):
    print('not coprime')
    exit()
u = 0
for i in a:
    u = gcd(u, i)
if u != 1:
    print('not coprime')
    exit()
vis = [False] * (10 ** 6 + 1)
for i in a:
    vis[i] = True
cnt = [0] * (10 ** 6 + 1)
for i in range(1, 10 ** 6 + 1):
    for j in range(1, 10 ** 6 + 1):
        if i * j > 10 ** 6:
            break
        if vis[i * j]:
            cnt[i] += 1
if max(cnt[2:]) <= 1:
    print('pairwise coprime')
else:
    print('setwise coprime')

Submission status: Wrong Answer

Solution code:
import math
n=int(input())
a=list(map(int,input().split()))
def s_bunkai(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
num1=a[0]
for i in range(1,n):
    num1=math.gcd(num1,a[i])
cnt=0
num3=set()
yn=0
for i in range(n):
    num2=s_bunkai(a[i])
    cnt+=len(num2)
    for j in range(len(num2)):
        num3.add(num2[j][0])
    if cnt!=len(num3):
        yn=1
        break
if yn==0:
    print("pairwise coprime")
elif num1==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()))

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

for a in A:
    data[a] += 1

pair = True

for i in range(1,10**6+1):
    check = 0
    for j in range(1,(10**6)//i+1):
        check += data[i*j]
    if check>1:
        pair = False

if pair:
    print("pairwise coprime")
else:
    res=A[0]
    for i in range(1,N):
        res=gcd(res,A[i])
    if res==1:
        print("setwise coprime")
    else:
        print("not coprime")

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(500005)
stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().strip()

n = ni()
a = na()

f = [0] * 1000001
for v in a:
    f[v] += 1
for i in range(500000, 1, -1):
    for j in range(i*2, 1000001, i):
        f[i] += f[j]

def gcd(a, b):
    while b > 0:
        c = a % b
        a = b
        b = c
    return a

if max(f[2:]) <= 1:
    print("pairwise coprime")
else:
    x = 0
    for v in a:
        x = gcd(x, v)
    if x == 1:
        print("setwise coprime")
    else:
        print("not coprime")

Submission status: Time Limit Exceeded

Solution code:
import math

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

def gen_primes(limit):
    prime_table = [True] * (limit + 1)
    prime_table[0] = False
    prime_table[1] = False
    for i in range(2, int(limit**.5)+1):
        prime_table[i+i::i] = [False] * (limit//i-1)
    return prime_table

primes = gen_primes(10**6)
factors = []
gcd = a[0]
for A in a:
    for i,p in enumerate(primes[2:], 2):
        if p and A%i == 0:
            factors.append(i)
            break
    gcd = math.gcd(gcd, A)

if len(factors) == len(set(factors)):
    print('pairwise coprime')
elif gcd == 1:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Time Limit Exceeded

Solution code:
#「全ての 1≤i<j≤N について、GCD(Ai,Aj)=1」が成り立つ
#pairwise coprime
#pairwise coprime ではなく、かつ、GCD(A1,…,AN)=1 
#setwise coprime
#それ以外
#not coprime
import math
from collections import Counter

def prime_factorize(n):
    i = 2
    factors = []
    while i*i <= n:
        while n%i == 0:
            n //= i
            factors.append(i)
        i += 1
    if n > 1:
        factors.append(n)
    return Counter(factors)

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

c = []
for i in a:
    c.append(prime_factorize(i))

flg = True
gcd = a[0]
prime_factors = c[0]
for factors, A in zip(c[1:], a[1:]):
    if prime_factors & factors:
        flg = False
    prime_factors |= factors
    gcd = math.gcd(gcd, A)
    
if flg:
    print('pairwise coprime')    
elif gcd == 1:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Time Limit Exceeded

Solution code:
#「全ての 1≤i<j≤N について、GCD(Ai,Aj)=1」が成り立つ
#pairwise coprime
#pairwise coprime ではなく、かつ、GCD(A1,…,AN)=1 
#setwise coprime
#それ以外
#not coprime
n = int(input())
a = list(map(int, input().split()))

import math
for i in range(2, int(max(a)**.5)+1):
    if sum([j%i == 0 for j in a]) >= 2:
        break
else:
    print('pairwise coprime')
    exit()

gcd = a[0]
for i in a[1:]:
    gcd = math.gcd(gcd, i)
    if gcd == 1:
        break
    
if gcd == 1:
    print('setwise coprime')
else:
    print('not coprime')