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: Time Limit Exceeded

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

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

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

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

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

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=sorted(list(map(int,input().split())))
from math import gcd
from functools import reduce
def lcm(x,y):
  return (x*y)//gcd(x,y)
def lcm_list(l):
  return reduce(lcm,l,1)
def gcd_list(l):
    return reduce(gcd,l)
p=1
for i in a:
  p*=i
if p==lcm_list(a):
  print('pairwise coprime')
elif gcd_list(a)==1:
  print('setwise coprime')
else:
  print('not coprime')

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A=list(map(int,input().split()))
from functools import reduce
from math import gcd
g=reduce(lambda x,y:gcd(x,y),A,0)
if g>1:
    print('not coprime')
    exit()
def prime(N):
    p=set(range(2,N+1))
    for i in range(int(N**.5)+1):
        if i in p:
            p-=set(range(i*2,N+1,i))
    return p
p=prime(max(A))
r=1
for a in A:
    p2=p.copy()
    for x in p:
        if a%x==0:
            p2.remove(x)
        while a%x==0:
            a//=x
    p=p2
    if a>1:
        r=0
print(['setwise coprime','pairwise coprime'][r])

Submission status: Time Limit Exceeded

Solution code:
import math
def find_lcm(num1, num2): 
    if(num1>num2): 
        num = num1 
        den = num2 
    else: 
        num = num2 
        den = num1 
    rem = num % den 
    while(rem != 0): 
        num = den 
        den = rem 
        rem = num % den 
    gcd = den 
    lcm = ((num1 * num2)/gcd) 
    return lcm 
n=(int)(input());
l = []
l = [int(item) for item in input().split()]
num1 = l[0] 
num2 = l[1] 
lcm = find_lcm(num1, num2) 
pro = l[0]*l[1]; 
for i in range(2, len(l)): 
    lcm = find_lcm(lcm, l[i]) 
    pro = pro*l[i];
if (pro==lcm):
    print("pairwise coprime")
else:
    gc=math.gcd(l[0],l[1])
    for i in range(2, len(l)):
        gc=math.gcd(gc,l[i])
    if (gc==1):
        print("setwise coprime")
    else:
        print("not coprime")

Submission status: Time Limit Exceeded

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 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]
for i in range(n-2,-1,-1):
	t=gcd(max(a,l[i]),min(a,l[i]))
	if t!=1:
		flag=0
		break
	a=(a*l[i])//t
if flag:
	print("pairwise coprime")
	exit()
a=l[0]
for i in range(1,n):
	a=gcd(max(a,l[i]),min(a,l[i]))
if a==1:
	print("setwise coprime")
	exit()
print("not coprime")

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import math
from functools import reduce

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

ans = True
for i in range(len(A)-1):
  for j in range(i+1, len(A)):
    if math.gcd(A[i], A[j]) != 1:
      ans = False
      break

if ans:
  print('pairwise coprime')
else:
  print('setwise coprime' if reduce(math.gcd, A) == 1 else 'not coprime')

Submission status: Time Limit Exceeded

Solution code:
def factorize(x):
    f = {}
    if x%2==0: f[2]=0
    while x%2==0:
        f[2]+=1
        x//=2
    
    p = 3
    while x>=p*p:
        if x%p==0: f[p]=0
        while x%p==0:
            f[p]+=1
            x//=p
        p+=2
    if x>1: f[x]=1
    return f

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

F = {0:0}

for a in A:
    for f in set(factorize(a)):
        if f not in F: F[f] = 0
        F[f] += 1

m = max(F.values())
if m<=1:
    print('pairwise coprime')
elif m<N:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Time Limit Exceeded

Solution code:
from math import inf, log2


class SegmentTree:
    def __init__(self, array, func=max):
        self.n = len(array)
        self.size = 2**(int(log2(self.n-1))+1) if self.n != 1 else 1
        self.func = func
        self.default = 0 if self.func != min else inf
        self.data = [self.default] * (2 * self.size)
        self.process(array)

    def process(self, array):
        self.data[self.size : self.size+self.n] = array
        for i in range(self.size-1, -1, -1):
            self.data[i] = self.func(self.data[2*i], self.data[2*i+1])

    def query(self, alpha, omega):
        """Returns the result of function over the range (inclusive)!"""
        if alpha == omega:
            return self.data[alpha + self.size]
        res = self.default
        alpha += self.size
        omega += self.size + 1
        while alpha < omega:
            if alpha & 1:
                res = self.func(res, self.data[alpha])
                alpha += 1
            if omega & 1:
                omega -= 1
                res = self.func(res, self.data[omega])
            alpha >>= 1
            omega >>= 1
        return res

    def update(self, index, value):
        """Updates the element at index to given value!"""
        index += self.size
        self.data[index] = value
        index >>= 1
        while index:
            self.data[index] = self.func(self.data[2*index], self.data[2*index+1])
            index >>= 1


# ------------------- fast io --------------------
import os
import sys
from io import BytesIO, IOBase

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

# ------------------- fast io --------------------
from math import gcd, ceil

def pre(s):
    n = len(s)
    pi = [0] * n
    for i in range(1, n):
        j = pi[i - 1]
        while j and s[i] != s[j]:
            j = pi[j - 1]
        if s[i] == s[j]:
            j += 1
        pi[i] = j
    return pi


def prod(a):
    ans = 1
    for each in a:
        ans = (ans * each)
    return ans

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


def binary(x, length=16):
    y = bin(x)[2:]
    return y if len(y) >= length else "0" * (length - len(y)) + y

def get_primes(n):
  m = n+1
  #numbers = [True for i in range(m)]
  numbers = [True] * m #EDIT: faster
  for i in range(2, int(n**0.5 + 1)):
    if numbers[i]:
      for j in range(i*i, m, i):
        numbers[j] = False
  primes = []
  for i in range(2, m):
    if numbers[i]:
      primes.append(i)
  return primes

gp = set(get_primes(10**6))

for _ in range(int(input()) if not True else 1):
    n = int(input())
    #d, t, s = map(int, input().split())
    a = list(map(int, input().split()))
    g = a[0]
    for i in a:
        g = gcd(i, g)
    if g != 1:
        print("not coprime")
        continue
    pos = True
    for i in a:
        if i == 1:continue
        x = i
        b = []
        for j in gp:
            if x % j == 0:b += [j]
            while x % j == 0:
                x = x // j
            if x == 1:break
        if x != 1:
            pos = False
            break
        for each in b:
            gp.remove(each)
    print("pairwise coprime" if pos else "setwise coprime")

Submission status: Time Limit Exceeded

Solution code:
# E - Coprime
from math import gcd

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

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

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

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

Submission status: Time Limit Exceeded

Solution code:
def yakusu(x):
    tmp=int(pow(x, 1/2))+1
    out=set()
    for i in range(1, tmp):
        if x%i==0:
            out.add(i)
            out.add(x//i)
    if pow(x, 1/2)%1==0:
        out.add(pow(x, 1/2))
    out=list(out)
    out.sort()
    return out

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

pairwise=True
X=set()

for a in A:
  tmp=yakusu(a)
  for i in tmp[1:]:
    if i in X:
      pairwise=False
    else:
      X.add(i)
      
import math
tmp=A[0]+0
for a in A[1:]:
  tmp=math.gcd(tmp, a)
  
if tmp==1:
  setwise=True
else:
  setwise=False
  
if pairwise==True:
  print('pairwise coprime')
elif setwise==True:
  print('setwise coprime')
else:
  print('not coprime')

Submission status: Time Limit Exceeded

Solution code:
import math
n=int(input())
arr=list(map(int,input().split()))
count=0
f=1
for i in range(len(arr)):
	for j in range(i+1,len(arr)):
		if math.gcd(arr[i],arr[j])!=1:
			f=0
if f:
	print('pairwise coprime')
else:
	x=arr[0]
	for i in range(1,len(arr)):
		x=math.gcd(x,arr[i])
	if x==1:
		print('setwise coprime')
	else:
		print('not coprime')

Submission status: Time Limit Exceeded

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

from collections import Counter

class Osa_k:
    def __init__(self, n):
        self.n = n
        self.min_factor = [int(x) for x in range(n+1)]
        
        self.is_prime = [True] * (self.n + 1)
        self.is_prime[0] = False
        self.is_prime[1] = False
        for j in range(4, self.n+1, 2):
            self.is_prime[j] = False
            self.min_factor[j] = 2
        for i in range(3, int(self.n**0.5) + 1, 2):
            if not self.is_prime[i]:
                continue
            for j in range(i * 2, self.n + 1, i):
                self.is_prime[j] = False
                if self.min_factor[j] >= i:
                    self.min_factor[j] = i
    
    def calulate(self, x):
        ans = []
        while x > 1:
            key = self.min_factor[x]
            while x%key == 0:
                ans.append(key)
                x //= key
        counter = set(ans)
        return counter
        

def main():
    n = int(input())
    a = list(map(int, input().split()))
    a.sort()
    key = a[0]
    sc = False
    for i in range(1, n):
        key = math.gcd(key, a[i])
    
    if key == 1:
        sc = True
    
    
    pc = True
    osak = Osa_k(10**6+1)
    
    sub = set()
    
    
    for i in range(n):
        key = osak.calulate(a[i])
        if key&sub:
            pc = False
            break
        sub = sub | key
    
    if pc:
        print("pairwise coprime")
    elif sc:
        print("setwise coprime")
    else:
        print("not coprime")

    
    
    
    
    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

def gcd(x, y):
    if x == 0:return y
    else: return gcd(y % x, x)

is_prime = [True] * 1100000

is_prime[0] = is_prime[1] = False

for i in range(2, 1100000):
    if not is_prime[i]:continue
    for j in range(i*i, 1100000, i):
        is_prime[j] = False

small_prime = [p for p in range(1100) if is_prime[p]]
        
g = 0

for a in A:
    g = gcd(g, a)

if g != 1:
    print("not coprime")
    exit()

used = [False] * 1100000
primes = [a for a in A if is_prime[a]]
for p in primes:
    used[p] = True

not_primes = [a for a in A if not is_prime[a]]

for a in not_primes:
    for p in small_prime:
        if a % p != 0:continue
        if used[p]:
            print("setwise coprime")
            exit()
        used[p] = True
        while a % p == 0:
            a //= p
    if a > 1:
        if used[a]:
            print("setwise coprime")
            exit()
        used[a] = True

print("pairwise coprime")

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
# E

import sys
from collections import defaultdict, deque
from heapq import heappush, heappop
import math
import bisect
input = sys.stdin.readline

# 再起回数上限変更
# sys.setrecursionlimit(1000000)

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


def divisor(n: int) -> list:
    res = []
    if n == 1:
        return [1]

    for i in range(1, n):
        if n % i == 0:
            res.append(i)
            if i > 1:
                dic[i]+=1
            if i != n / i:
                res.append(int(n / i))
                dic[int(n / i)] += 1
        if (i + 1) * (i + 1) > n:
            # res.sort()
            return res

for a in A:
    res = divisor(a)

flg_pair = True
flg_step = True

for a in dic.values():
    if a > 1:
        flg_pair = False
    if a == N:
        flg_step = False

if flg_pair:
    print('pairwise coprime')
elif flg_step:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
arr = list(map(int,input().split()))
def find_gcd(x, y): 
    while(y): 
        x, y = y, x % y 
    return x 
def overAllGCD(l):
    num1 = l[0] 
    num2 = l[1] 
    gcd = find_gcd(num1, num2) 
    for i in range(2, len(l)): 
        gcd = find_gcd(gcd, l[i]) 
    return(gcd)
allGCDs = []
for i in range(n):
    for j in range(i+1,n):
        allGCDs.append(find_gcd(arr[i],arr[j]))
import collections
c = collections.Counter(allGCDs)
overGCD = overAllGCD(arr)
if len(c) == 1 and 1 in c:
    print("pairwise coprime")
elif overGCD == 1:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np

def gcd(x,y):
    while y:
        x,y = y , x % y 
    return x


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


gcd_all = a[0]
for i in range(1,n):
    gcd_all = gcd(gcd_all,a[i])
    
if gcd_all>1:
    print("not coprime")
    sys.exit()

amax = a.max()

aflag = np.zeros(amax,np.int64)
aflag[a-1] = 1

for i in range(2,amax+1):
    index = (np.arange(amax//i)+1)*i - 1
    count = aflag[index].sum()
    if count>=2:
        print("setwise coprime")
        sys.exit()
else:
    print("pairwise coprime")

Submission status: Time Limit Exceeded

Solution code:
import math
def a(n):
    arr = set()
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.add(i)

    if temp!=1:
        arr.add(temp)
    if arr==[]:
        arr.add(n)
    return arr
N=int(input())
L=list(map(int,input().split()))
L=list(set(L))
gc=L[0]
for i in L:
  gc=math.gcd(i,gc)
  if gc==1:
    break
if gc!=1:
  print("not coprime")
  exit()
ans=set()
for i in L:
  if a(i)&ans!=set():
    print("setwise coprime")
    exit()
  ans=a(i)|ans
print("pairwise coprime")

Submission status: Time Limit Exceeded

Solution code:
n = input()
As = list(map(int, input().split()))
import math
gcd = As[0]
for a in As[1:]:
    tmp = gcd
    gcd = math.gcd(tmp, a)

if gcd > 1:
    print("not coprime")
    exit()
flg = 0
lcd = As[0]
prod = As[0]
for a in As[1:]:
    if math.gcd(a,lcd) != 1:
        print("setwise coprime")
        exit()
    lcd = a*lcd//math.gcd(a,lcd)
 
print("pairwise coprime")

Submission status: Time Limit Exceeded

Solution code:
import math


n=int(input())
a=list(map(int,input().strip().split()))[:n]
f=0
for i in range(n):
  for j in range(i+1,n):
    if(math.gcd(a[i],a[j])!=1):
      f=1
      break
g=math.gcd(a[0],a[1])
for i in range(2,n):
  g=math.gcd(g,a[i])
#print(g)
if(f==0):
  print("pairwise coprime")
elif(f==1):
  if(g==1):
    print("setwise coprime")
  else:
    print("not coprime")

Submission status: Time Limit Exceeded

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

def gcd(a, b):
    while b: a, b = b, a % b
    return a
def isPrimeMR(n):
    d = n - 1
    d = d // (d & -d)
    L = [2]
    for a in L:
        t = d
        y = pow(a, t, n)
        if y == 1: continue
        while y != n - 1:
            y = (y * y) % n
            if y == 1 or t == n - 1: return 0
            t <<= 1
    return 1
def findFactorRho(n):
    m = 1 << n.bit_length() // 8
    for c in range(1, 99):
        f = lambda x: (x * x + c) % n
        y, r, q, g = 2, 1, 1, 1
        while g == 1:
            x = y
            for i in range(r):
                y = f(y)
            k = 0
            while k < r and g == 1:
                ys = y
                for i in range(min(m, r - k)):
                    y = f(y)
                    q = q * abs(x - y) % n
                g = gcd(q, n)
                k += m
            r <<= 1
        if g == n:
            g = 1
            while g == 1:
                ys = f(ys)
                g = gcd(abs(x - ys), n)
        if g < n:
            if isPrimeMR(g): return g
            elif isPrimeMR(n // g): return n // g
            return findFactorRho(g)
def primeFactor(n):
    i = 2
    ret = {}
    rhoFlg = 0
    while i*i <= n:
        k = 0
        while n % i == 0:
            n //= i
            k += 1
        if k: ret[i] = k
        i += 1 + i % 2
        if i == 101 and n >= 2 ** 20:
            while n > 1:
                if isPrimeMR(n):
                    ret[n], n = 1, 1
                else:
                    rhoFlg = 1
                    j = findFactorRho(n)
                    k = 0
                    while n % j == 0:
                        n //= j
                        k += 1
                    ret[j] = k

    if n > 1: ret[n] = 1
    if rhoFlg: ret = {x: ret[x] for x in sorted(ret)}
    return ret


from collections import defaultdict
def main():
  n = int(input())
  A = tuple(map(int, input().split()))
  x = A[0]
  M1 = defaultdict(int)
  M2 = defaultdict(int)
  for a in A:
      x = gcd(x, a)
      for f, cnt in primeFactor(a).items():
        if cnt >= M1[f]:
          M2[f] = M1[f]
          M1[f] = cnt
        elif cnt >= M2[f]:
          M2[f] = cnt
  if x != 1:
      print("not coprime")
      exit()
  for d in M2.values():
      if d >= 1:
          print("setwise coprime")
          exit()
  print("pairwise coprime")
if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

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

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

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

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

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




    return None

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
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])
cur = a[0]
f = False
for i in range(1, n):
    if gcd(cur, a[i]) != 1:
        f = True
        break
    cur *= a[i] // gcd(cur, a[i])
if not f:
    print("pairwise coprime")
elif g == 1:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Time Limit Exceeded

Solution code:
ma = lambda :map(int,input().split())
lma = lambda :list(map(int,input().split()))
tma = lambda :tuple(map(int,input().split()))
ni = lambda:int(input())
yn = lambda fl:print("Yes") if fl else print("No")
import collections
import math
import itertools
import heapq as hq
ceil = math.ceil
gcd=math.gcd
def factorize(n):
    b = 2
    fct = [(1,1)]
    while b * b <= n:
        cnt =0
        while n % b == 0:
            n //= b
            cnt +=1
        if cnt >=1:
            fct.append((b,cnt))
        b = b + 1
    if n > 1:
        fct.append((n,1))
    return fct

n = ni()
A = lma()
d=collections.Counter()
for i in range(n):
    a = A[i]
    fct = factorize(a)
    for fc,cnt in fct:
        if fc==1:continue
        d[fc]+=1

f1=True # pp or sp
f2=True # sp or other
for num,cnt in d.items():
    if cnt==n:
        f2=False #other
        break
    else:
        if cnt==1:
            pass
        else:
            f1=False
if f2==False:
    print("not coprime")
    exit()
elif f1 and f2:
    print("pairwise coprime")
elif f1==False:
    print("setwise coprime")

Submission status: Time Limit Exceeded

Solution code:
import sys
import io, os
input = sys.stdin.buffer.readline
#input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline

import math
N = 10**6+50

def main():

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

    spf = [-1]*(N+1)
    for i in range(N+1):
        spf[i] = i
    for i in range(2, int(math.sqrt(N))+1):
        if spf[i] == i:
            for j in range(i*2, N+1, i):
                if spf[j] == j:
                    spf[j] = i

    S = set()
    flag = False
    for i, a in enumerate(A):
        s = set()
        while a != 1:
            p = spf[a]
            if p in S:
                #print('setwise coprime')
                #exit()
                flag = True
            s.add(p)
            a //= p
        S = S | s
        if i == 0:
            T = s
        else:
            T = T & s

    #print(S)
    #print(T)
    if len(T) != 0:
        print('not coprime')
    elif flag:
        print('setwise coprime')
    else:
        print('pairwise coprime')

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

def gcd(a, b):
    while b: a, b = b, a % b
    return a
def isPrimeMR(n):
    d = n - 1
    d = d // (d & -d)
    L = [2]
    for a in L:
        t = d
        y = pow(a, t, n)
        if y == 1: continue
        while y != n - 1:
            y = (y * y) % n
            if y == 1 or t == n - 1: return 0
            t <<= 1
    return 1
def findFactorRho(n):
    m = 1 << n.bit_length() // 8
    for c in range(1, 99):
        f = lambda x: (x * x + c) % n
        y, r, q, g = 2, 1, 1, 1
        while g == 1:
            x = y
            for i in range(r):
                y = f(y)
            k = 0
            while k < r and g == 1:
                ys = y
                for i in range(min(m, r - k)):
                    y = f(y)
                    q = q * abs(x - y) % n
                g = gcd(q, n)
                k += m
            r <<= 1
        if g == n:
            g = 1
            while g == 1:
                ys = f(ys)
                g = gcd(abs(x - ys), n)
        if g < n:
            if isPrimeMR(g): return g
            elif isPrimeMR(n // g): return n // g
            return findFactorRho(g)
def primeFactor(n):
    i = 2
    ret = {}
    rhoFlg = 0
    while i*i <= n:
        k = 0
        while n % i == 0:
            n //= i
            k += 1
        if k: ret[i] = k
        i += 1 + i % 2
        if i == 101 and n >= 2 ** 20:
            while n > 1:
                if isPrimeMR(n):
                    ret[n], n = 1, 1
                else:
                    rhoFlg = 1
                    j = findFactorRho(n)
                    k = 0
                    while n % j == 0:
                        n //= j
                        k += 1
                    ret[j] = k

    if n > 1: ret[n] = 1
    if rhoFlg: ret = {x: ret[x] for x in sorted(ret)}
    return ret


from collections import defaultdict
n = int(input())
A = tuple(map(int, input().split()))
x = A[0]
M1 = defaultdict(int)
M2 = defaultdict(int)
for a in A:
    x = gcd(x, a)
    for f, cnt in primeFactor(a).items():
      if cnt >= M1[f]:
        M2[f] = M1[f]
        M1[f] = cnt
      elif cnt >= M2[f]:
        M2[f] = cnt
if x != 1:
    print("not coprime")
    exit()
for d in M2.values():
    if d >= 1:
        print("setwise coprime")
        exit()
print("pairwise coprime")

Submission status: Time Limit Exceeded

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

g = 0
for a in A:
    g = gcd(g,a)
if g > 1:
    print('not coprime')
    exit()

MAXN = 10**6+10
sieve = [0,0] + [1]*MAXN
p = 2
primes = set()
while p*p <= MAXN:
    if sieve[p]:
        primes.add(p)
        for q in range(2*p,MAXN+1,p):
            sieve[q] = 0
    p += 1
for i in range(p,MAXN+1):
    if sieve[i]:
        primes.add(i)

for a in A:
    dels = set()
    for p in primes:
        if p > a: continue
        while a%p==0:
            a //= p
            dels.add(p)
    if a > 1:
        print('setwise coprime')
        exit()
    for p in dels:
        primes.remove(p)
print('pairwise coprime')

Submission status: Time Limit Exceeded

Solution code:
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
import sys
M = 10**6
def main(N, A):
    u = [False] * (M + 1)
    mx = 0
    for n in range(2, M + 1):
        if u[n]: continue
        for nn in range(n, M + 1, n):
            u[nn] = True
        c = 0
        for a in A:
            if a % n == 0:
                c += 1
        if c == N:
            print('not coprime')
            return
        mx = max(mx, c)
    if mx <= 1:
        print('pairwise coprime')
    else:
        print('setwise coprime')

if __name__ == '__main__':
    input = sys.stdin.readline
    N = int(input())
    *A, = map(int, input().split())
    main(N, A)

Submission status: Time Limit Exceeded

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


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

mod=10**9+7




pair_flg=0
set_flg=0
n=I()
A=LI()
t_set=set()
s_set=set(range(2,n+1))
D=defaultdict(set)

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


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

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

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