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 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
P=list()
N=int(input())
L=list(map(int,input().split()))

gc=L[0]
for i in L:
  gc=gcd(i,gc)
  if gc==1:
    break
if gc!=1:
  print("not coprime")
  exit()



ans=set()
c=0
for i in L:
  c+=len(primeFactor(i))
  ans|=set(primeFactor(i))
if c==len(ans):
  print("pairwise coprime")
else:
  print("setwise coprime")

Submission status: Time Limit Exceeded

Solution code:
def factorization(n):
    if n == 1:
        return {1}
    temp = n
    ans = set()
    SS = [i for i in S if i*2 < n]
    for i in SS:
        if temp % i == 0:
            ans.add(i)
    if temp != 1:
        ans.add(temp)
    return ans

S=set()
L = [True]*(10**6+1)
L[0] = False
L[1] = False
for i in range(2, 10**6+1):
    if L[i]:
        S.add(i)
        for j in range(i*2, 10**6+1, i):
            L[j] = False


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


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

ct = 0
s = set()
for i in range(N):
    tmp = factorization(A[i])-{1}
    ct += len(tmp)
    s |= tmp
    if ct != len(s):
        break
else:
    print('pairwise coprime')
    exit()


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

if L1[0] == 1:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Time Limit Exceeded

Solution code:
import math
from functools import reduce

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

N = int(input())
A_list = [int(_) for _ in input().split()]

is_pairwise = True
is_setwise = False

for i in range(len(A_list)):
    if i < N:
        if sum(map(lambda x:math.gcd(x, A_list[i]), A_list[i+1:N])) != len(A_list[i+1:N]):
            is_pairwise= False
            break
    if not is_pairwise:
        break

if is_pairwise:
    print('pairwise coprime')
else:
    if gcd(*A_list) == 1:
        is_setwise = True
    if is_setwise:
        print('setwise coprime')
    else:
        print('not coprime')

Submission status: Time Limit Exceeded

Solution code:
from sys import *
input=stdin.readline
from math import *
n=int(input())
l=list(map(int,input().split()))
l.sort()
g=l[0]
for i in range(1,n):
    g=gcd(g,l[i])
if(g!=1):
    print("not coprime")
else:
    f=0
    p=l[-1]
    c=0
    for i in l:
        if(i%2==0):
            c+=1
    if(c>=2):
        f=1
    for i in range(n-2,-1,-1):
        if(gcd(p,l[i])!=1):
            f=1
            break
        p*=l[i]
    if(f==1):
        print('setwise coprime')
    else:
        print('pairwise coprime')

Submission status: Time Limit Exceeded

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

from math import gcd

def main():
    n = int(input())
    A = list(map(int , input().split()))
    N = max(A)+1

    sv = [i for i in range(N)]
    for i in range(2 ,int(N**2)+1) :
        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


    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

    if ans == (n*(n-1))//2:
        print("pairwise coprime")
        exit()

    A.sort()
    d = A[0]

    for i in A:
        d = gcd(i,d)
        if d == 1 or d > 10**2:
            break

    if d == 1:
        print("setwise coprime")
    else:
        print("not coprime")

main()

Submission status: Time Limit Exceeded

Solution code:
import math

n = input()
lis = [int(a) for a in input().split(" ")]
lis_len = len(lis)
p_flag = True
s_flag = True

sqrt_max = int(math.sqrt(max(lis)))
for i in range(2, sqrt_max+1):
  mod_lis = [a % i for a in lis]
  non_zero_mod_lis = list(filter(lambda x:x!=0, mod_lis))
  if len(non_zero_mod_lis) <= lis_len-2:
    p_flag = False
  if len(non_zero_mod_lis) == 0:
    s_flag = False
    break
    
    
if p_flag:
  print("pairwise coprime")
elif s_flag:
  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 get_sieve_of_eratosthenes(n):
    prime = []
    limit = 1000
    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]

data=get_sieve_of_eratosthenes(1000000)
def prime_factorization(n):
    arr=[]
    for p in data:
        if p >n:
            break
        if n%p==0:
            arr.append(p)
        
    return arr

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

for i in range(N):
    test=A[i]
    for p in data:
        if p>A[i]:
            break
        if test%p==0:
            dict[p]+=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:
import math
N=int(input())
A=list(map(int,input().split()))
ans1 = A[0]
ans2 = 0
f = True
for i in range(1, N):
    ans1 = math.gcd(ans1, A[i])
    for j in range(i+1, N):
        ans2 = math.gcd(A[i-1],A[j-1])
        if (ans2 > 1):
            f = False

if f:
    print('pairwise coprime')
else:
    if ans1==1:
        print('setwise coprime')
    else:
        print('not coprime')

Submission status: Time Limit Exceeded

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

#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return input().rstrip().decode()
def II(): return int(input())
def FI(): return float(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode()



def main():
	nn=II()
	A=LI()
	ans="pairwise coprime"

	n = 500005
	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=set(primes)

	#print(primes)


	B=set(range(1,5*10**6+5))
	C=set()
	for i in A:
		a=set()
		while i%2==0:
			a.add(2)
			i//=2
		f=3
		while f*f<=i:
			if i in primes:
				break
			elif i%f==0:
				a.add(f)
				i//=f
			else:
				f+=2
		if i!=1:
			a.add(i)
		B&=a
		if C&a:
			ans="setwise coprime"
		C|=a

	if B:
		ans="not coprime"

	print(ans)





















if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

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

counts = [0 for _ in range(max(A)+1)]
for a in A:
  counts[a] += 1

integers = [1 for _ in range(max(A)+1)]
integers[0] = 0
integers[1] = 0
max_count = 0
for i in range(max(A)+1):
   if integers[i] >= 1:
    count = 0
    for j in range(i,max(A)+1,i):
      count += counts[j]
      integers[j] = 0
    max_count = max(max_count,count)

if max_count == N:
  answer = 'not coprime'
elif max_count >= 2:
  answer = 'setwise coprime'
else:
  answer = 'pairwise coprime'

print(answer)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
list1 = list(map(int,input().split()))
list2 = []
def gcd(a,b):
  while b != 0:
    a, b = b, a%b
  return a
a = gcd(list1[0],list1[1])
for i in range(n):
  for j in range(i+1,n):
    g = gcd(list1[i],list1[j])
    if g not in list2:
      list2.append(g)
      a = gcd(a, g)
if list2 == [1]:
  print('pairwise coprime')
else:
  if a == 1:
    print('setwise coprime')
  else:
    print('not coprime')

Submission status: Time Limit Exceeded

Solution code:
def prime_factors(n, used):
    i = 2
    #factors = []
    fackinds = set()
    while i**2 <= n:
        if n % i != 0:
            i += 1
        else:
            if i not in fackinds:
                used[i] += 1
            fackinds.add(i)
            #factors.append(i)
            n = n // i
    if n > 1:
        if n not in fackinds:
            used[n] += 1
        fackinds.add(n)
        #factors.append(n)
    #return fackinds, factors
    return fackinds

import math
def primes(n):
    max = math.sqrt(n)
    candidates = [i for i in range(2, n+1)]
    primes = []
    while candidates[0] <= max:
        primes.append(candidates[0])
        candidates = [candidates[i] for i in range(len(candidates)) if candidates[i] % candidates[0] != 0]
    primes.extend(candidates)
    return primes

def resolve():
    N = int(input())
    A = list(map(int, input().split()))
    prims = primes(10**6)
    used = {}
    for p in prims:
        used[p] = 0

    for a in A:
        fackinds = prime_factors(a, used)
    
    two_over = False
    n_over = False
    for p in prims:
        if used[p] >= 2:
            two_over = True
        if used[p] == N:
            n_over = True
    
    if two_over:
        if n_over:
            print("not coprime")
        else:
            print("setwise coprime")
    else:
        print("pairwise coprime")
    #print(used)

if '__main__' == __name__:
    resolve()

Submission status: Time Limit Exceeded

Solution code:
import math

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

cnt = 0
for i in range(0,N-1):
    for j in range(i+1,N):
        if math.gcd(A[i], A[j]) != 1:
            cnt += 1
            break
    else:
        continue
    break


if cnt == 0:
    print('pairwise coprime')
    exit()

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

if ans == 1:
    print('setwise coprime')
    exit()

print('not coprime')

Submission status: Time Limit Exceeded

Solution code:
import math
N = int( input() )
A = sorted( list(map(int, input().split())))
ans = A[0]
# http://www.ysr.net.it-chiba.ac.jp/~yashiro/sosu/
P = list( map( int, "2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433 439 443 449 457 461 463 467 479 487 491 499 503 509 521 523 541 547 557 563 569 571 577 587 593 599 601 607 613 617 619 631 641 643 647 653 659 661 673 677 683 691 701 709 719 727 733 739 743 751 757 761 769 773 787 797 809 811 821 823 827 829 839 853 857 859 863 877 881 883 887 907 911 919 929 937 941 947 953 967 971 977 983 991 997".split(" ")))
L = []
def factorization(n):
    temp = n
    K = []
    root = int(-(-n**0.5//1))+1
    for p in P:
      if p > root:
        break
      if temp%p==0:
        cnt=0
        while temp%p==0:
          cnt+=1
          temp //= p
        if p in L:
          return True
        K.append( p )
    if temp!=1:
      if temp in L:
        return True
      K.append( temp )
    if L==[]:
      L.append( n )
    L.extend( K )
    return False

cnt = 0
for i in range(1, N):
    ans = math.gcd(ans, A[i])
    if ans == 1:
      break
    else:
      cnt += 1
if ans != 1:
  ret = "not coprime"
else:
  if cnt > 0:
    ret = "setwise coprime"
  else:
    ret = "pairwise coprime"
    for a in A:
      if factorization( a ):
        ret = "setwise coprime"
        break
print( ret )

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
A=list(map(int,input().split(" ")))
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

base=A[0]
condition=0
for i in range(1,len(A),1):
    g=gcd(base,A[i])
    base*=A[i]
    if g!=1:
        condition=1
        break

if condition!=0 and i==1:
    base=A[0]
    for j in range(i,len(A),1):
        base=gcd(base,A[j])
    if base!=1:
        condition=2
ans=["pairwise coprime","setwise coprime","not coprime"]
print(ans[condition])

Submission status: Time Limit Exceeded

Solution code:
import math


def eratosthenes(limit):
    A = [i for i in range(2, limit+1)]
    P = []

    while True:
        prime = min(A)

        if prime > math.sqrt(limit):
            break

        P.append(prime)

        i = 0
        while i < len(A):
            if A[i] % prime == 0:
                A.pop(i)
                continue
            i += 1

    for a in A:
        P.append(a)

    return P


er = eratosthenes(1500)


def make_divisors(n):
    arr = []
    temp = n
    for i in er:
        if i >= int(-(-n**0.5//1))+1:
            break
        if temp % i == 0:
            while temp % i == 0:
                temp //= i
            arr.append(i)

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

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

    a = set(arr)
    if 1 in a:
        a.remove(1)

    return a


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

is_pairwise = True
is_setwise = False

f_set = set()
n_set = set()

for item in a:
    if item in n_set:
        is_pairwise = False
        break
    else:
        if item != 1:
            n_set.add(item)
    for fc in make_divisors(item):
        if fc in f_set:
            is_pairwise = False
            break
        else:
            f_set.add(fc)
    if not is_pairwise:
        break

s_set = make_divisors(a[0])
for item in a[1:]:
    tmp_set = make_divisors(item)
    s_set = s_set & tmp_set
    if len(s_set) == 0:
        is_setwise = True

if is_pairwise:
    print('pairwise coprime')
elif is_setwise:
    print('setwise coprime')
else:
    print('not coprime')

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
import random

N = int(input())
A_s = list(map(int, input().split()))
pc = True
sc = True
M = {}
MAX = 0

for i,A in enumerate(A_s):
    for p in factorization(A):
        if p[0] == 1:
            continue
        if p[0] in M:
            # print()
            M[p[0]] += 1
            pc = False
        else:
            M[p[0]] = 1
        MAX = max(MAX, M[p[0]])
    if not pc and MAX <= i:
        break
else:
    sc = False

if pc:
    print('pairwise coprime')
elif sc:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Time Limit Exceeded

Solution code:
import os
import sys
from math import gcd

import numpy as np


def solve(inp):
    n = inp[0]
    aaa = inp[1:]
    g = 0
    for i in range(n):
        g = gcd(g, aaa[i])
    if g != 1:
        return -1

    PRIMES = (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103,
              107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223,
              227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347,
              349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463,
              467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607,
              613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743,
              751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883,
              887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997)

    one_count = (aaa == 1).sum()
    aaa = np.unique(aaa)

    if max(0, one_count - 1) + len(aaa) != n:
        return 0

    for p in PRIMES:
        multiple_count = 0
        inc_1 = 0
        for i in range(len(aaa)):
            if aaa[i] % p == 0:
                multiple_count += 1
                aaa[i] //= p
                while aaa[i] % p == 0:
                    aaa[i] //= p
                if aaa[i] == 1:
                    inc_1 += 1

        if multiple_count > 1:
            return 0

        if multiple_count == 1:
            one_count += inc_1
            aaa = np.unique(aaa)

    if max(0, one_count - 1) + len(aaa) == n:
        return 1

    return 0


if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC

    cc = CC('my_module')
    cc.export('solve', '(i8[:],)')(solve)
    cc.compile()
    exit()

if os.name == 'posix':
    # noinspection PyUnresolvedReferences
    from my_module import solve
else:
    from numba import njit

    solve = njit('(i8[:],)', cache=True)(solve)
    print('compiled', file=sys.stderr)

inp = np.fromstring(sys.stdin.read(), dtype=np.int64, sep=' ')
ans = solve(inp)
print(['setwise coprime', 'pairwise coprime', 'not coprime'][ans])

Submission status: Time Limit Exceeded

Solution code:
#dt = {} for i in x: dt[i] = dt.get(i,0)+1
import sys;input = sys.stdin.readline
inp,ip = lambda :int(input()),lambda :[int(w) for w in input().split()]

#from fractions import gcd

def gcd(a, b): 
    if a == 0: return b 
    if b == 0: return a 
    k = 0
    while ((a | b) & 1) == 0: 
        a >>= 1
        b >>= 1
        k += 1
    while (a & 1) == 0: 
        a >>= 1
    while b:  
        while (b & 1) == 0: 
            b >>= 1
        if a > b : 
            a,b = b,a
        b = b - a 
    return a << k 

from math import sqrt
def pfact(num):
    d = set()
    if num&1 == 0:
        d.add(2)
    while num&1 == 0:
        num >>= 1
    for i in range(3,int(sqrt(num))+1,2):
        if num%i==0:
            d.add(i)
        while num%i==0:
            num //= i
    if num>2:
        d.add(num)
    return list(d)

n = inp()
x = ip()
t = x[0]
for i in range(1,n):
    t = gcd(t,x[i])
    if t == 1:
        break
if t != 1:
    ans = 'not coprime'
else:
    ans = 'pairwise coprime'
    dt = {i+1:1 for i in range(10**6)}
    for i in x:
        for j in pfact(i):
            if dt[j]:
                dt[j] = 0
            else:
                ans = 'setwise coprime'
                break
print(ans)

Submission status: Time Limit Exceeded

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

from math import gcd

def main():
    n = int(input())
    A = list(map(int , input().split()))
    N = max(A)+1

    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


    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

    if ans == (n*(n-1))//2:
        print("pairwise coprime")
        exit()

    A.sort()
    d = A[0]

    for i in A:
        d = gcd(i,d)
        if d == 1 or d > 10**2:
            break

    if d == 1:
        print("setwise coprime")
    else:
        print("not coprime")

main()

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}

    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 sieve_of_erastosthenes(num):
    input_list = [False if i % 2 == 0 or i % 3 == 0 or i % 5 == 0 else True for i in range(num)]
    input_list[0] = input_list[1] = False
    input_list[2] = input_list[3] = input_list[5] = True
    sqrt = math.sqrt(num)

    for serial in range(3, num, 2):

        if serial >= sqrt:
            return input_list

        for s in range(serial ** 2, num, serial):
            input_list[s] = False


def main():
    N = NI()
    A = NLI()
    ela = sieve_of_erastosthenes(1001)
    ela = [i for i, b in enumerate(ela) if b]

    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:
from sys import *
input=stdin.readline
from math import *
n=int(input())
l=list(map(int,input().split()))
l.sort()
g=l[0]
for i in range(1,n):
    g=gcd(g,l[i])
if(g!=1):
    print("not coprime")
else:
    f=0
    p=l[-1]
    for i in range(n-2,-1,-1):
        if(gcd(p,l[i])!=1):
            f=1
            break
        p*=l[i]
    if(f==1):
        print('setwise coprime')
    else:
        print('pairwise coprime')

Submission status: Time Limit Exceeded

Solution code:
from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce, lru_cache
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def MAP1()  : return map(lambda x:int(x)-1,input().split())
def LIST()  : return list(MAP())
def LIST1() : return list(MAP1())

n = INT()
a = sorted(LIST())

m = 1000
primes = set(range(2, m+1))
for i in range(2, int(m**0.5+1)):
    primes.difference_update(range(i*2, m+1, i))
primes=list(primes)

for i in range(n):
    for x in primes:
        while a[i] % pow(x,2) == 0:
            a[i] //= x

k = 1
flag = 1
for i in range(1, n):
    k *= a[i-1]
    if gcd(k, a[i]) > 1:
        flag = 0
        break

if flag == 1:
    print("pairwise coprime")
    exit()
else:
    g = a[0]
    for i in range(1, n):
        g = gcd(g, a[i])
    if g == 1:
        print("setwise coprime")
    else:
        print("not coprime")

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=list(map(int,input().split()))
mod=10**9+7
import sys
import math
def setwise_coprime(a):
  ans=a[0]
  for i in range(1,n):
    ans=math.gcd(ans,a[i])
  return ans

ruiseki=1

if setwise_coprime(a)==1:
  for i in range(n):
    ruiseki=ruiseki*a[i]
  for i in range(n):
    num=math.gcd(a[i],(ruiseki//a[i])%a[i])
    if num!=1:
      print("setwise coprime")
      sys.exit()
  print("pairwise coprime")
else:
  print("not coprime")
  sys.exit()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import itertools as it
def gcd(a,b):
  while b!=0:
    a,b = b, a%b
  return a
n = int(input())
a = list(map(int, input().split()))
ac = list(it.combinations(a,2))
pw = True
for i,j in ac:
  if gcd(i,j)!=1:
    pw = False
if pw:
  ans = 'pairwise coprime'
elif np.gcd.reduce(a)==1:
  ans = 'setwise coprime'
else:
  ans = 'not coprime'
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#import sys
MOD = 10 ** 9 + 7
INFI = 10**10
#input = sys.stdin.readline
import math
from collections import deque
import itertools
import heapq
#import bisect
from fractions import Fraction
import copy
from functools import lru_cache
from collections import defaultdict
import pprint

#oo=list("ABCDEFGHIJKLMNOPQRSTUVWXYZ")
# ko=list("abcdefghijklmnopqrstuvwxyz")

def sosuhante(n):
    for k in range(2, int(math.sqrt(n))+1):
        if n% k ==0:
            return False
    return True
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

def kingaku(a,b,n):
    keta=len(str(n))
    return a*n+b*keta

def my_index(l, x, default=False):
    if x in l:
        return l.index(x)
    else:
        return default

#    h,w,a,b = map(int, input().split())
#    c = [[0 for j in range(n)] for i in range(n)]

def ret(a):
    c=[None]*(len(a)-1)
    if len(a)==1:
        return a[0]
    elif len(a)==0:
        return 0
    for i in range(1,len(a)):
        c[i-1]=abs(a[i]-a[i-1])
    return ret(c)

def soinsubunkai(n):
    a = []
    i = 1
    while i*i <= n:
        if n % i == 0 and i!=1:
            a.append(i)
            n=n//i

        if n% i !=0 or i==1:
            i += 1
    nokori=[n]
    return a + nokori

def soinsubunkai2(n,m):
    a = []
    i = 1
    for i in m:
        if n % i == 0 and i!=1:
            a.append(i)
            n=n//i

        if n% i !=0 or i==1:
            i += 1
    nokori=[n]
    return a + nokori

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


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

def main():
    #l,r,d=map(int,input().split())
    n=int(input())
    a=list(map(int,input().split()))
    sosu=[]
    ccc=get_sieve_of_eratosthenes(n)
    memo = defaultdict(int)
    for i in range(n):
        if a[i]!=1:
            temp=set(soinsubunkai2(a[i],ccc))
        else:
            temp={}
        for j in temp:
            memo[j]+=1


 #   print(sosu)
 #   print(memo)
 #   print(memo.values())
    if len(memo)>=1:
        mmm=max(memo.values())
    else:
        mmm=1
    if mmm<=1:
        print("pairwise coprime")
    elif mmm<n:
        print("setwise coprime")
    else:
        print("not coprime")








if __name__ == "__main__":

    main()

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)
    C = list(map(lambda x: math.gcd(x[0], x[1]), B))

    if len(list(set(C))) == 1 and list(set(C))[0] == 1:
        print("pairwise coprime")
    elif len(list(set(C))) != 1:
        print("setwise coprime")
    elif len(list(set(C))) == 1:
        print("not coprime")

resolve()