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:
import math
from functools import reduce

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

for i in range(n):
    for j in range(i + 1, n):
        if math.gcd(a_list[i], a_list[j]) != 1:
            if reduce(math.gcd, a_list) == 1:
                print("setwise coprime")
                exit()
            else:
                print("not coprime")
                exit()

print("pairwise coprime")

Submission status: Time Limit Exceeded

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

import fractions
from functools import reduce

def gcd(*numbers):
    return reduce(fractions.gcd, numbers)

gcds = set()

for j in range(1, n):
    for i in range(j):
        if fractions.gcd(As[i],As[j]) != 1:
            gcds.add(fractions.gcd(As[i],As[j]))
if len(gcds) != 0:
    if gcd(*gcds) == 1:
        print("setwise coprime")
    else:
        print("not coprime")
else:
    print("pairwise coprime")

Submission status: Time Limit Exceeded

Solution code:
import itertools
import math


def resolve():
    n = int(input())
    A = list(map(int, input().split()))
    B = itertools.combinations(A, 2)
    new_arr = []
    for b in B:
        c = math.gcd(b[0], b[1])
        if c != 1:
            new_arr.append(c)

    if len(new_arr) == 0:
        print("pairwise coprime")
    elif len(list(set(new_arr))) != 1:
        print("setwise coprime")
    else:
        print("not coprime")

resolve()

Submission status: Time Limit Exceeded

Solution code:
import sys, bisect, math, itertools, heapq, collections
from operator import itemgetter
# a.sort(key=itemgetter(i)) # i番目要素でsort
from functools import lru_cache
# @lru_cache(maxsize=None)
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
mod = 10**9 + 7
eps = 10**-7


def inp():
    '''
    一つの整数
    '''
    return int(input())


def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))


def str_inp():
    '''
    文字列をリストとして読み込む
    '''
    return list(input()[:-1])


def get_sieve_of_eratosthenes(n):
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 2:
        raise ValueError('n is more than 2')
    prime = []
    limit = math.sqrt(n)
    data = [i + 1 for i in range(1, 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]


n = inp()
a = inpl()

data = get_sieve_of_eratosthenes(10**6)
ans = "pairwise coprime"
for i in data:
    coprime = 0
    for j in range(n):
        if a[j] % i == 0:
            coprime += 1
        elif a[j] % i != 0 and (coprime >= 2 or ans == "setwise coprime"):
            break
    if coprime == n:
        ans = "not coprime"
        break
    elif coprime >= 2:
        ans = "setwise coprime"
print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

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


isPairwise = True
isSetwise = True
dict=defaultdict(lambda:0)

for i in range(N):
    arr = prime_factorization(A[i])
    for j in range(len(arr)):
        prime=arr[j][0]
        if prime!=1:
            dict[prime]+=1

for i in dict.values():
    if i==N:
        isPairwise=False
        isSetwise=False
    elif i>1:
        isPairwise=False
    else:
        pass

if isPairwise:
    print('pairwise coprime')
elif isSetwise:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce
from math import gcd


def primes(n):
    is_prime = [i % 2 != 0 and i % 3 != 0 and i % 5 != 0 and i % 7 != 0 for i in range(n + 1)]
    is_prime[1] = False
    is_prime[2] = is_prime[3] = is_prime[5] = is_prime[7] = True
    for p in range(3, int(n**0.5) + 1, 2):
        if not is_prime[p]:
            continue
        for i in range(p**2, n + 1, p):
            is_prime[i] = False
    return [i for i, p in enumerate(is_prime) if p]


def main():
    n = int(input())
    a = [int(i) for i in input().split()]
    if reduce(gcd, a) > 1:
        print("not coprime")
        return
    p = primes(max(max(a), 10))
    for pi in p:
        c = 0
        for ai in a:
            if c > 1:
                print("setwise coprime")
                return
            c += ai % pi == 0
    print("pairwise coprime")


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

def make_divisors(n):
    res = []
    x = n
    y = 2
    while y*y <= x:
        while x % y == 0:
            res.append(y)
            x //= y
        y += 1
    if x > 1:
        res.append(x)
    return res

n = ni()
a = na()

wa = set(make_divisors(a[0]))
s = len(wa)
seki = wa

for i in range(1,n):
    ii = set(make_divisors(a[i]))
    s += len(ii)
    wa = wa | ii
    seki = seki & ii
    if s != len(wa) and len(seki) == 0:
        print('setwise coprime')
        exit()

if len(wa) == s:
    print('pairwise coprime')
elif len(seki) == 0:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
from collections import deque
from collections import defaultdict

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid(h, w, num): return [[int(num)] * w for _ in range(h)]


# Nの素因数分解を辞書で返す
def prime_fact(n, ela):
    if n == 1:
        return {1: 1}

    root = int(math.sqrt(n))
    prime_dict = {}
    for i in ela:
        cnt = 0
        while n % i == 0:
            cnt += 1
            n = n // i
        if cnt:
            prime_dict[i] = cnt
        if n == 1:
            break
    if n != 1:
        prime_dict[n] = 1
    return prime_dict


def prime_eratosthenes(n):
   prime_list = []
   num_list=[]
   for i in range(2, n+1):
       if i not in num_list:
           prime_list.append(i)
           for j in range(i*i, n+1, i):
               num_list.append(j)
   return prime_list


def main():
    N = NI()
    A = NLI()
    ela = prime_eratosthenes(1000)

    if max(A) == 1:
        print("pairwise coprime")
        exit()

    p_cnt = defaultdict(int)
    PD_list = defaultdict(dict)
    for a in A:
        if a == 1:
            continue

        if PD_list[a]:
            AP = PD_list[a]
        else:
            AP = prime_fact(a, ela)
        PD_list[a] = AP
        for apk in AP.keys():
            p_cnt[apk] += 1

    max_p = max(p_cnt.values())
    if max_p == 1:
        print("pairwise coprime")
    elif max_p == N:
        print("not coprime")
    else:
        print("setwise coprime")



if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
from heapq import heapify, heappop, heappush
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

N = getN()
A = getList()

pair = True
semi = True
# not divisible
# 全部互いに素かどうか
judge = [0] * (10 ** 6 + 1)
# エラストテネスの篩
prime = [2]
max = 10 ** 6 + 1
limit = int(math.sqrt(max))
data = [i + 1 for i in range(2, max, 2)]

while limit > data[0]:
    prime.append(data[0])
    data = [j for j in data if j % data[0] != 0]
prime = prime + data

now = A[0]
for i in A[1:]:
    now = gcd(now, i)
if now > 1:
    semi = False

for i in A:
    judge[i] += 1

for i in prime:
    cnt = 0
    for j in range(i, 10 ** 6 + 1, i):
        cnt += judge[j]
    if cnt > 1:
        pair = False
        break

if pair and semi:
    print('pairwise coprime')
elif semi:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Time Limit Exceeded

Solution code:
import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)
def gcd_list(numbers):
    return reduce(math.gcd, numbers)

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

def main():
    flag = True
    LCM = A[-1]
    for i in range(N - 2, -1, -1):
        if gcd(A[i], LCM) != 1:
            flag = False
            break

        LCM *= A[i]

    if flag:
        print("pairwise coprime")
    else:
        if gcd_list(A) == 1:
            print("setwise coprime")
        else:
            print("not coprime")

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

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

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

    return arr
n=int(input())
alist=list(map(int, input().split()))
blist=[0]*1000001
for i in alist:
  for j in factorization(i):
    blist[j[0]]+=1
cnt=1
for i in range(2,1000001):
  cnt=max(cnt,blist[i])
if cnt==1:
  print('pairwise coprime')
else:
  import math
  num=alist[0]
  for i in range(n):
    num=math.gcd(num,alist[i])
  if num==1:
    print('setwise coprime')
  else:
    print('not coprime')

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split()))
m = [0] * (10**6+2)

setwise = True
pairwise = True

for a in A:
    i = 1
    while(a / i > 1):
        if (a % i == 0):
            m[a//i] += 1
        i += 1

for i in range(2, 10**6+1):
    if m[i] >= 2:
        pairwise = False

    if m[i] == N:
        setwise = False
        break

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

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
m=list(map(int,input().split()))
import math
mod=10**12+7
s=m[n-1]
d=m[n-1]

r=0
for i in range(n-2,-1,-1):
    d=math.gcd(m[i],d)
    
    
    if math.gcd(s,m[i])>1:
        r=1
    s*=m[i]
    
    


    
if d>1:
    print('not coprime')
elif r==1:
    print('setwise coprime')
else:
    print('pairwise coprime')

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import collections
from decimal import Decimal # 10進数で考慮できる

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

d = collections.deque()
def LI(): return list(map(int, sys.stdin.readline().split()))

N = int(input())
A = LI()

"""
pairwise coprime 1,3,7,10
setwise coprime 2,3,4,10


coprimeかどうかで全部やる
"""

def primes(n): #試し割り法で各素因数とその指数を求める
    cnt=collections.defaultdict(int)
    for i in range(2,int(n**0.5)+1):
        if n%i==0:
            while n%i==0:
                cnt[i]+=1
                n//=i
    if n!=1:
        cnt[n]+=1
    return cnt


def solve():
    gcd = A[0]
    for a in A:
        gcd = math.gcd(gcd, a)
    if gcd != 1:
        return "not coprime"

    prime_his = []
    for a in A:
        d = primes(a)
        for key in d.keys():
            if key in prime_his:
                return "setwise coprime"
        prime_his = prime_his + list(d.keys())
    
    return "pairwise coprime"

    
print(solve())

Submission status: Time Limit Exceeded

Solution code:
import math
import itertools

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

for a, b in itertools.combinations(A, 2):
    if math.gcd(a, b) != 1:
        a = A[0]
        for _a in A[1:]:
            a = math.gcd(a, _a)
            if a == 1:
                print('setwise coprime')
                break
        else:
            print('not coprime')
        break
else:
    print('pairwise coprime')

Submission status: Time Limit Exceeded

Solution code:
from math import sqrt
N = int(input())
A = list(map(int, input().split()))
M = 10 ** 6
num = [0 for i in range(M)]
num[0] = 1
for i in range(M):
  if num[i] == 0:
    if i + 1 > sqrt(M):
      break
    n = 2 * (i + 1)
    while n <= M:
      num[n-1] = 1
      n += (i + 1)
primes = [p+1 for p in range(M) if num[p] == 0]
l = len(primes)
B = [0 for i in range(l)]
for i in range(N):
  j = 0
  while A[i] > 1:
    if A[i] % primes[j] == 0:
      B[j] += 1
    while A[i] % primes[j] == 0:
      A[i] //= primes[j]
    j += 1
x = 1
y = 1
for i in range(l):
  if B[i] >= 2:
    x = 0
  if B[i] == N:
    y = 0
if x == 1:
  print("pairwise coprime")
elif y == 1:
  print("setwise coprime")
else:
  print("not coprime")

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N=int(input())
A=list(map(int,input().split()))
flag1=True
flag2=True
for i in range(N-1):
    for j in range(i+1,N):
        if np.gcd(A[i],A[j])!=1:
            flag1=False
            break
if np.gcd.reduce(A)!=1:
    flag2=False
if flag1:
    print('pairwise coprime')
elif flag2:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
A = list(map(int, input().split()))
lis = [True for i in range(10**6+1)]
flag = False
for i in range(2, 10**6 + 1):
    if lis[i] == True:
        j = i
        while j <= 10**6:
            lis[j] = False
            j += i
        now = 0
        for a in A:
            if a % i == 0:
                now += 1
        if now == n:
            print("not coprime")
            exit()
        if now > 1:
            flag = True
if flag:
    print("setwise coprime")
else:
    print("pairwise coprime")

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
#import numpy as np
import re
import math
from collections import defaultdict,deque,Counter
from fractions import Fraction
import bisect
import itertools
from itertools import accumulate
from copy import deepcopy

import heapq
import random
import time
import os
import sys
from functools import lru_cache,reduce
readline=sys.stdin.readline
sys.setrecursionlimit(100000)
alp="abcdefghijklmnopqrstuvwxyz"
numbers="0123456789"
mod=int(10**9+7)
inf=int(10**19)
class Set():
    def __init__(self,A=[]):
        self.heap=[]
        self.dic=defaultdict(bool)
        self.size=0
        for a in A:self.add(a)
    
    def __str__(self):
        return str(self.heap)
    
    def add(self,x):
        if not self.find(x):
            heapq.heappush(self.heap,x)
            self.dic[x]=True
            self.size+=1

    def remove(self,x):
        if self.find(x):
            self.dic[x]=False
            self.size-=1

    def find(self,x):
        return self.dic[x]
    
    def top(self):
        while self.heap and self.dic[self.heap[0]]==False:
            heapq.heappop(self.heap)
        if self.heap:return self.heap[0]
        else:return None

    def pop(self):
        ret=None
        if self.heap:
            ret=self.top()
            self.remove(ret)
        return ret
class multiset():
    def __init__(self,A=[]):
        self.heap=[]
        self.dic=defaultdict(int)
        self.size=0
        for a in A:self.add(a)
    
    def __str__(self):
        return str(self.heap)
    
    def add(self,x):
        heapq.heappush(self.heap,x)
        self.dic[x]+=1
        self.size+=1

    def remove(self,x):
        if self.dic[x]>0:
            self.dic[x]-=1
            self.size-=1
    
    def count(self,x):
        return self.dic[x]

    def find(self,x):
        return self.dic[x]>0
    
    def top(self):
        while self.heap and self.dic[self.heap[0]]==0:
            heapq.heappop(self.heap)
        if self.heap:return self.heap[0]
        else:return None

    def pop(self):
        ret=None
        if self.heap:
            ret=self.top()
            self.remove(ret)
        return ret
class Edge():
    def __init__(self,x,y,val=1):
        self.x=x
        self.y=y
        self.val=val
class Point():
    def __init__(self,y,x):
        self.x=x
        self.y=y
class unionfind():
    def __init__(self,n):
        self.n=n
        self.P=[a for a in range(n)]
        self.rank=[0]*n
 
    def find(self,x):
        if(x!=self.P[x]):
            self.P[x]=self.find(self.P[x])
        return self.P[x]
 
    def same(self,x,y):
        return self.find(x)==self.find(y)
 
    def link(self,x,y):
        if self.rank[x]<self.rank[y]:
            self.P[x]=y
        elif self.rank[y]<self.rank[x]:
            self.P[y]=x
        else:
            self.P[x]=y
            self.rank[y]+=1
 
    def unite(self,x,y):
        self.link(self.find(x),self.find(y))
 
    def size(self):
        S=set()
        for a in range(self.n):
            S.add(self.find(a))
        return len(S)
def yn(b):print("yes" if b else "no")
def Yn(b):print("Yes" if b else "No")
def YN(b):print("YES" if b else "NO")
def ispow(a,b):
    now=b
    while now<a:
        now*=b
    return now==a
def getbin(num,size):
    A=[0]*size
    for a in range(size):
        if (num>>(size-a-1))&1==1:
            A[a]=1
        else:
            A[a]=0
    return A
def getfacs(n,mod_=0):
    A=[1]*(n+1)
    for a in range(2,len(A)):
        A[a]=A[a-1]*a
        if(mod_>0):A[a]%=mod_
    return A
def comb(n,r,mod,fac):
    if(n-r<0):return 0
    return (fac[n]*pow(fac[n-r],mod-2,mod)*pow(fac[r],mod-2,mod))%mod
def nextcomb(num,size):
    x=num&(-num)
    y=num+x
    z=num&(~y)
    z//=x
    z=z>>1
    num=(y|z)
    if(num>=(1<<size)):return False
    else:return num
def getprimes(n):
    if n==0:return []
    A=[True]*(n+1)
    A[0]=False
    A[1]=False
    for a in range(2,n+1):
        if A[a]:
            for b in range(a*2,n+1,a):
                A[b]=False
    ret=[]
    for a in range(n+1):
        if(A[a]):ret.append(a)
    return ret
def isprime(num):
    if(num<=1):return False
    i=2
    while i*i<=num:
       if(num%i==0):return False
       i+=1
    return True
def ifelse(b,t,f):return t if b else f
def factorize(n):
    b = 2
    ret=defaultdict(int)
    while b * b <= n:
        while n % b == 0:
            n //= b
            ret[b]+=1
        b+=1
    if n > 1:ret[n]+=1
    return ret
def inputintlist(row=1): 
    if row==1:
        ret=list(map(int,input().split()))
    else:
        ret=[None]*row
        for a in range(row):
            ret[a]=int(input())
    return ret
def inputfloatlist(row=1): 
    if row==1:
        ret=list(map(float,input().split()))
    else:
        ret=[None]*row
        for a in range(row):
            ret[a]=float(input())
    return ret
def istanchouzouka(A):
    f=True
    prev=min(A)-1
    for a in A:
        if prev>=a:
            f=False
        prev=a
    return f
def istanchouhigensyou(A):
    f=True
    prev=min(A)-1
    for a in A:
        if prev>a:
            f=False
        prev=a
    return f
def getallsum(A):
    s=sum(A)
    dp=defaultdict(int)
    dp[0]=1
    for a in range(0,len(A)):
        for b in range(s,-1,-1):
            if b-A[a]>=0:
                dp[b]+=dp[b-A[a]]
    return dp
def yuukoutomukou(edges):
    ret=deepcopy(edges)
    for edge in edges:
        if not edge.x==edge.y:
            ret.append(Edge(edge.y,edge.x,edge.val))
    return ret
def dijkstra(edges,V,start):
    from queue import PriorityQueue
    mincost=[inf]*V
    G=[[] for a in range(V)]
    for edge in edges:
        G[edge.x].append([edge.val,edge.y])
    Q=PriorityQueue()
    Q.put([0,start])#[cost,x]
    while not Q.empty():
        nowcost,nowx=Q.get()
        if mincost[nowx]==inf:
            mincost[nowx]=nowcost
            for cost,y in G[nowx]:
                newcost=nowcost+cost
                Q.put([newcost,y])
    return mincost
def warshallfloyd(edges,V):
    mincost=[[inf for b in range(V)] for a in range(V)]
    for a in range(V):mincost[a][a]=0
    for edge in edges:
        mincost[edge.x][edge.y]=min(mincost[edge.x][edge.y],edge.val)#x→yが複数ある場合のためにmin()する
    for k in range(V):
        for s in range(V):
            for t in range(V):
                if mincost[s][k]==inf or mincost[k][t]==inf:continue
                mincost[s][t]=min(mincost[s][t],mincost[s][k]+mincost[k][t])
    return mincost
def bellemanford(edges,V,start):
    mincost=[inf]*V
    mincost[start]=0
    for _ in range(V):
        for edge in edges:
            if mincost[edge.x]==inf:continue
            mincost[edge.y]=min(mincost[edge.y],mincost[edge.x]+edge.val)
    return mincost
def getmd(x1,y1,x2,y2):return abs(x1-x2)+abs(y1-y2)
def geted(x1,y1,x2,y2):return math.sqrt((x1-x2)**2+(y1-y2)**2)
class fordfulkerson():
    def __init__(self,edges,V,s,t):
        self.V=V
        self.used=[False]*V
        self.G=[[] for a in range(V)]
        self.s=s
        self.t=t
        for edge in edges:
            self.G[edge.x].append({"x":edge.x,"y":edge.y,"cap":edge.val,"rev":len(self.G[edge.y])})
            self.G[edge.y].append({"x":edge.y,"y":edge.x,"cap":0,"rev":len(self.G[edge.x])-1})
    def dfs(self,v,t,f=inf):
        if v==t:return f
        self.used[v]=True
        for a in range(len(self.G[v])):
            x=self.G[v][a]["x"]
            y=self.G[v][a]["y"]
            cap=self.G[v][a]["cap"]
            rev=self.G[y][self.G[x][a]["rev"]]
            if self.used[y] or cap==0:continue
            f2=self.dfs(y,t,min(f,cap))
            if f2>0:
                self.G[v][a]["cap"]-=f2
                rev["cap"]+=f2
                return f2
        return 0
    def maxflow(self):
        flow=0
        while True:
            self.used=[False]*V
            zouka=self.dfs(self.s,self.t)
            if zouka==0:break
            flow+=zouka
        return flow
def zipsort(*args):
    ziplist=sorted(zip(*args))
    for a in range(len(args)):
        for b in range(len(ziplist)):
            args[a][b]=ziplist[b][a]
def zipreverse(*args):
    ziplist=list(zip(*args))
    rev=[]
    for a in range(len(ziplist)-1,-1,-1):
        rev.append(ziplist[a])
    for a in range(len(args)):
        for b in range(len(rev)):
            args[a][b]=rev[b][a]

def to10(A):
    ret=0
    for a in range(len(A)-1,-1,-1):
        ret+=X[a]*2**(N-1-a)
    return ret
######################################################################################################
N=int(input())
A=inputintlist()
s=defaultdict(bool)
f=True

for a in A:
    for b in factorize(a).keys():
        if s[b]:
            f=False
            break
        else:
            s[b]=True
if f:
    print("pairwise coprime")
else:
    G=A[0]
    for a in A:
        G=math.gcd(a,G)
    if G==1:
        print("setwise coprime")
    else:
        print("not coprime")

Submission status: Time Limit Exceeded

Solution code:
def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return set(a)

import math
mod = 10 ** 9 + 7

n = int(input())
a = [int(i) for i in input().split()]
tmp = a[0]
set_v = a[0]
pairwise = True
prime_list = set([])
for i in range(1, n):
    prime = prime_factorize(a[i])
    set_v = math.gcd(set_v, a[i])
    for p in prime:
        if p in prime_list:
            pairwise = False
        prime_list.add(p)
if pairwise == True:
    ans = 'pairwise coprime'
elif set_v == 1:
    ans = 'setwise coprime'
else:
    ans = 'not coprime'
print(ans)

Submission status: Time Limit Exceeded

Solution code:
##https://www.codechef.com/viewsolution/20131475

from math import gcd

N = (10 ** 6) + 100

sv = [i for i in range(N)]
for i in range(2 , N) :
    if i * i >= N : break
    if sv[i] < i : continue
    for j in range(i * i , N , i) :
        sv[j] = min(sv[j] , i)

def getPrimes(a) :
    pr = []
    if a == 1 : return pr
    pr.append(sv[a])
    while a > 1 :
        if sv[a] != pr[-1] :
            pr.append(sv[a])
        a //= sv[a]
    return pr


np = [0] * N
F = [0] * N

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

for a in A :
    pr = getPrimes(a)
    for i in range(1 << len(pr)) :
        prod , nb = 1 , 0
        for j in range(len(pr)) :
            if i & (1<<j) :
                prod *= pr[j]
                nb += 1
        F[prod] += 1
        np[prod] = nb

ans = 0
for i in range(N) :
    cnt = F[i]
    cnt = (cnt * (cnt-1))//2
    if np[i] & 1 : ans -= cnt
    else : ans += cnt

d = A[0]

for i in A:
    d = gcd(d,i)

if ans == (n*(n-1))//2:
    print("pairwise coprime")
elif d == 1:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Time Limit Exceeded

Solution code:
#E

import math

INF=float('inf')
ans1='pairwise coprime'
ans2='setwise coprime'
ans3='not coprime'

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

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

if g!=1:
  print(ans3)
else:
  for i in range(n):
    for j in range(n):
      if i==j:
        continue
      if math.gcd(A[i],A[j])!=1:
        print(ans2)
        exit()
  print(ans1)

Submission status: Time Limit Exceeded

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

is_pairwise_coprime = True
is_setwise_coprime = True
checked = [0]*(N+1)

for i in range(2, N+1):
    if checked[i]:
        continue
    
    tmp = 0
    for j in range(N):
        if A[j]%i == 0:
            tmp += 1
    if tmp > 1:
        is_pairwise_coprime = False
    if tmp == N:
        is_setwise_coprime = False
    
    n = i
    while n < N+1:
        checked[n] = 1
        n += i

if is_pairwise_coprime:
    print('pairwise coprime')
elif is_setwise_coprime:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Time Limit Exceeded

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

A.reverse()
val = A[0]
flg = True
for i in range(1,N):
    if gcd(val,A[i]) != 1:
        flg = False
    val *= A[i]
if flg == True:
    print('pairwise coprime')
    exit()





val = A[0]
for i in range(1,N):
    val = gcd(val,A[i])
if val == 1:
    print('setwise coprime')
    exit()
print('not coprime')

Submission status: Time Limit Exceeded

Solution code:
from math import *
import fractions
import sys
import collections
import itertools
import pprint
from collections import deque
from heapq import *
import copy
input=sys.stdin.readline
N=int(input())
A=list(map(int,input().split()))
n = 10**6
d={}
pairflag=1
setflag=0
#primes = set(range(2, n+1))
#for i in range(2, int(n**0.5+1)):
#    primes.difference_update(range(i*2, n+1, i))
#primes=list(primes)
#print(len(primes))
buf=[0]*(max(A)+10)
seen=[0]*(max(A)+10)
def ggcd(a,b):
    if(b==0):
        return a
    return ggcd(b,a%b)
for num in range(N):
    m=A[num]
    #print(m)
    for i in range(2, int(sqrt(m)) +1):
        while m%i==0:
            if seen[i]==0:
                buf[i]=1
                m //= i
            else:
                pairflag=0
                break
        if pairflag==0:
            break
    if pairflag==1:
        if m>1:
            if seen[m]==0:
                buf[m]=1
            else:
                pairflag=0
                break
    else:
        break
    #    if pairflag==0:
    #        break
    seen=buf[:]
    #print(m,seen,buf,pairflag)
#print(pairflag)

num=A[0]
for i in range(1,N):
    num=ggcd(num,A[i])
if num==1:
    setflag=1
else:
    setflag=0

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

"""
x=list(set(A))
for i in x:
    for j in range(2*i,10**6+1,i):
        if d.get(j)!=None:
            pairflag=0
            break
    if pairflag==0:
        break
print(pairflag)

"""

Submission status: Time Limit Exceeded

Solution code:
import sys

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

a = max(A)
check = 0
for i in range(2,a) :
    B = list(map(lambda x : x%i , A))
    if B.count(0) == N :
        print("not coprime")
        sys.exit()
    elif B.count(0) >= 2 :
        check = 1

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