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 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 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 main():
    #l,r,d=map(int,input().split())
    n=int(input())
    a=list(map(int,input().split()))
    sosu=[]
    memo = defaultdict(int)
    for i in range(n):
        if a[i]!=1:
            temp=set(soinsubunkai(a[i]))
        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:
from math import gcd

if __name__ == '__main__':

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

    gcd_ = gcd(A[0], A[1])
    for i in range(2, len(A)):
        gcd_ = gcd(gcd_, A[i])

    set_wise = False
    if gcd_ == 1:
        set_wise = True
    if not(set_wise):
        print("not coprime")
    else:
        pairwise = True
        for i in range(n):
            for j in range(i+1, n):
                gcd_ = gcd(A[i], A[j])
                if gcd_ != 1:
                    pairwise = False
        if pairwise:
            print("pairwise coprime")
        else:
            print("setwise coprime")

Submission status: Time Limit Exceeded

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

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

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

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

    for i in a:
        gsum=gcd(gsum,i)
        Ed(i,ycnt)
    
    for i in range(N):
        if ycnt[i]>=2 and i!=1:
            break
    else:
        print("pairwise coprime")
        exit()
    if gsum==1:
        print("setwise coprime")
    else:print("not coprime")

if __name__=="__main__":main()

Submission status: Time Limit Exceeded

Solution code:
def find_gcd(num1,num2): 
    while(num2 != 0):
        temp = num2
        num2 = num1 % num2
        num1 = temp

    x= num1
    return x 
      
n=int(input())
a=input().split()
i=0
j=1
flag=1
while i<n-1:
    if j==n:
        i+=1
        j=i+1
    else:
        gcd=find_gcd(int(a[i]),int(a[j]))
        if gcd!=1:
            flag=0
            break
        j+=1
if  flag==1:
    print('pairwise coprime')
    
else:
    num1=int(a[0]) 
    num2=int(a[1]) 
    gcd=find_gcd(num1,num2) 
  
    for i in range(2,len(a)): 
        gcd=find_gcd(gcd,int(a[i])) 
    if gcd==1:
        print('setwise coprime')
    else:
        print('not coprime')

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
al = list(map(int, input().split())) 
     
def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]
 
pl = primes(1000)
 
def fact(n):
    arr = []
    temp = n
    for i in pl:
        if temp%i==0:
            while temp%i==0:
                temp //= i
            arr.append(i)
 
    if temp!=1:
        arr.append(temp)
 
    if arr==[]:
        arr.append(n)
 
    return arr
  
dp = [0]*(10**6)
#pairwise
for i in range(n):
    for j in fact(al[i]):
        dp[j] +=1

dpp = dp[2:]
 
if max(dpp)<=1:
    print("pairwise coprime")
 
elif max(dpp) ==n:
    print("not coprime")
    
else:
    print("setwise coprime")

Submission status: Time Limit Exceeded

Solution code:
MOD=10**9+7
import sys
import math
import random
N=int(input())
alist=list(map(int,input().split()))
#alist.sort()
random.shuffle(alist)

all_GCD=alist[0]
for i in range(1,N):
  all_GCD=math.gcd(all_GCD,alist[i])
  if all_GCD==1:
    break
else:
  print("not coprime")
  sys.exit(0)
  
lcm=1
prod=1
for i in range(N):
  lcm=lcm*alist[i]//math.gcd(lcm,alist[i])
  prod*=alist[i]
  if lcm!=prod:    
    print("setwise coprime")
    sys.exit(0)
    
print("pairwise coprime")

Submission status: Time Limit Exceeded

Solution code:
import math

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

lcm = a[0]
pwise_flag = True
for i in range(1,n):
    gcd = math.gcd(lcm,a[i])
    if gcd != 1:
        pwise_flag = False
        break
    else:
        lcm = lcm*a[i]
        
if pwise_flag:
    print('pairwise coprime')
else:
    min_a = min(a)
    swise_flag = False
    
    pf={}
    for i in range(2,int(min_a**0.5)+1):
        while min_a%i==0:
            pf[i]=pf.get(i,0)+1
            min_a//=i
    if min_a>1:pf[min_a]=1
    
    
    for i in range(n):
        del_keys = []
        for prime in pf.keys():
            if a[i]%prime != 0:
                del_keys.append(prime)
        for i in del_keys:
            del pf[i]
    
    if pf.keys():
        print('not coprime')
    else:
        print('setwise coprime')

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# N,M = map(int,sys.stdin.readline().split())
# a = tuple(map(int,sys.stdin.readline().split())) # single line with multi param
# a = tuple(int(sys.stdin.readline()) for _ in range(N)) # multi line with single param
# a = tuple(tuple(map(int,sys.stdin.readline().rstrip().split())) for _ in range(N)) # multi line with multi param
# s = sys.stdin.readline().rstrip()
# N = int(sys.stdin.readline())
# INF = float("inf")
import sys,collections

N = int(sys.stdin.readline())
a = tuple(map(int,sys.stdin.readline().split())) # single line with multi param

from math import gcd

pairwise = True
setwise = True
acc = a[0]
for i in range(N):
    for j in range(i+1,N):
        b = gcd(a[i],a[j])
        if b != 1:
            pairwise = False
    acc = gcd(acc,a[i])
    if acc == 1 and not pairwise:
        print("setwise coprime")
        exit()
if pairwise == True:
    print("pairwise coprime")
# elif setwise == True:
#     print("setwise coprime")
else:
    print("not coprime")

Submission status: Time Limit Exceeded

Solution code:
from math import gcd, sqrt
from collections import defaultdict


def Calc_Divisors(num):
    divisors = []
    for i in range(1, int(sqrt(num)) + 1):
        if num % i == 0:
            if i != 1:
                divisors.append(i)
            if i != num // i:
                divisors.append(num//i)
    # divisors.sort()
    return divisors


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

    s_tmp = A[0]
    p_flag = True
    p_dic = []
    for a in A:
        s_tmp = gcd(s_tmp, a)
        if p_flag:
            tmp = Calc_Divisors(a)
            for t in tmp:
                if t not in p_dic:
                    p_dic.append(t)
                else:
                    p_flag = False
                    continue

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


if __name__ == "__main__":
    main()

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()]

flag1 = True
for i in range(N-1):
  for j in range(i+1,N):
    if gcd(A[i], A[j]) != 1:
      flag1 = False
      break
  if not flag1:
    break
flag2 = False
if not flag1:
  flag2 = True if gcd_list(A) == 1 else False

if flag1:
  print("pairwise coprime")
elif flag2:
  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 = 1000050
	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(primes)


	B=set(range(1,10**6+2))
	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
		#print(a)


	if B:
		ans="not coprime"

	print(ans)





















if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

Solution code:
import math
N = int(input())
A = list(map(int, input().split()))
A.sort()
ans = 0
holdGcd = A[0]
setGcd = A[0]
pairwise = 1
setwise = 1
for i in range(N):
    for j in range(i+1,N):
        if A[i] > A[j]:
            continue
        if setGcd != 1:
            setGcd = math.gcd(setGcd, A[j])
        if pairwise == 1:
            holdGcd = math.gcd(A[i], A[j])
        # print(A[i], A[j], holdGcd, setGcd)
        if holdGcd != 1:
            pairwise = 0
        if pairwise == 0 and setGcd == 1:
            break
    if pairwise == 0 and setGcd == 1:
        break

if setGcd != 1:
    setwise = 0

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

Submission status: Time Limit Exceeded

Solution code:
import math
import itertools
from functools import reduce

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

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

result = 'not coprime'

if gcd(*aaa) == 1:
  result = 'setwise coprime'
  
for a, aa in itertools.combinations(aaa, 2):
  if math.gcd(a, aa) != 1:
    break
else:
  result = 'pairwise coprime'
  
print(result)

Submission status: Time Limit Exceeded

Solution code:
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 = [2]
    limit = int(n**0.5)
    data = [i + 1 for i in range(2, n, 2)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]
    return data
primes = get_sieve_of_eratosthenes(1000000)
smallprimes = [x for x in primes if x < 1000]
used = {}
for prime in primes:
    used[prime] = 0

n = int(input())
a = map(int, input().split())
for ai in a:
    for smallprime in smallprimes:
        if ai % smallprime == 0:
            used[smallprime] += 1
    if ai in primes and ai not in smallprimes:
        used[ai] += 1
pairwise = True
setwise = True
for prime in used:
    if used[prime] > 1:
        pairwise = False
    if used[prime] == n:
        setwise = False
if pairwise:
    print("pairwise coprime")
elif setwise:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-


def factor_osa(A):
    Max = max(A) + 1
    IsPrime = [True] * Max
    MinFactor = [-1] * Max
    Primes = []
    prim = {}
    dica = {}
    mxa = 0
    IsPrime[0], IsPrime[1] = False, False
    MinFactor[0], MinFactor[1] = 0, 1
    for i in range(2, Max):
        if IsPrime[i]:
            MinFactor[i] = i
            Primes.append(i)
            for j in range(i*2, Max, i):
                IsPrime[j] = False
                if MinFactor[j] == -1:
                    MinFactor[j] = i
    ret = []
    for a in A:
        res = []
        while a != 1:
            prime = MinFactor[a]
            exp = 0
            while MinFactor[a] == prime:
                exp += 1
                a //= prime
            res.append((prime, exp))
            if not prime in dica:
                dica[prime] = 1
            else:
                dica[prime] += 1
            mxa = max(mxa, dica[prime])
        ret.append(res)
    return [ret, mxa]

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

aa = factor_osa(a)

from math import gcd        #for python3.8

def Gcd(lt):
    l = len(lt)
    ret = [1]*l
    ret[0] = lt[0]
    for i in range(1,l):
        ret[i] = gcd(ret[i-1], lt[i])
    return ret

if max(a) == 1:
    print('pairwise coprime')
    exit()

if aa[1] == 1:
    print('pairwise coprime')
elif Gcd(a)[-1]==1:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Time Limit Exceeded

Solution code:
from math import gcd
from functools import reduce
def solution(A):
    ret = [gcd(A[i], A[j]) for i in range(len(A)) for j in range(i + 1, len(A))]
    if all([x==1 for x in ret]):
        return 'pairwise coprime'
    else:
        x = reduce(gcd, A)
        if x == 1:
            return 'setwise coprime'
    return 'not coprime'

input()
A = list(map(int, input().split()))
print(solution(A))

Submission status: Time Limit Exceeded

Solution code:

#!/usr/bin/python
# -*- coding: utf-8 -*-

# def
def int_mtx(N):
    x = []
    for _ in range(N):
        x.append(list(map(int,input().split())))
    return np.array(x)

def str_mtx(N):
    x = []
    for _ in range(N):
        x.append(list(input()))
    return np.array(x)

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

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

def print_space(l):
    return print(" ".join([str(x) for x in l]))

# import
import numpy as np
import collections as col

import math
from functools import reduce

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

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

# main code
N = int(input())
A = int_list()

AA = [x for x in A if not x == 1]

b = gcd(*A)

s = set()

if not b == 1:
    print("not coprime")
else:
    num = 0
    for aa in AA:
        v = factorization(aa)
        num += len(v)
        for i in range(0,len(v)):
            s.add(v[i][0])
    
    if len(s) == num:
        print("pairwise coprime")
    else:
        print("setwise coprime")

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
from math import gcd
N = int(input())
A = [int(i) for i in input().split()]
st=set()
pn = [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]

for a in A:
  if a == 1:
    continue
  ary=[]
  d=set()
  while a % 2 == 0:
    d.add(2)
    a//=2
  i=1
  n = 3
  while n * n <= a:
    if a % n == 0:
      a //= n
      d.add(n)
    else:
      i += 1
      if i < len(pn):
        n=pn[i]
      else:
        break
  if a > 1:
    ary.append(a)
    d.add(a)
  if st.isdisjoint(d):
    st = st | d
    continue
  # ------------------------
  n=gcd(A[0],A[1])
  for a in A[2:]:
    n=gcd(n,a)
  if n == 1:
    print("setwise coprime")
  else:
    print("not coprime")
  exit()
 
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())

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:
def main():
    import sys
    input = sys.stdin.buffer.readline
    from math import gcd
    N = int(input())
    A = list(map(int, input().split()))
    A.sort()
    S = 1
    d = dict()
    for x in A:
        S *= x
    flag = True
    for x in A:
        S //= x
        if gcd(S, x) == 1:
            continue
        else:
            flag = False
            break
    if flag:
        print("pairwise coprime")
    else:
        g = A[0]
        for x in A[1:]:
            g = gcd(x, g)
        if g == 1:
            print("setwise coprime")

        else:
            print("not coprime")


main()