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
import bisect as bi
import math
from collections import defaultdict as dd
import heapq
import itertools
input=sys.stdin.readline
from random import randint
##import numpy as np
sys.setrecursionlimit(10**7)
mo=10**9+7
def cin():
    return map(int,sin().split())
def ain():            
    return list(map(int,sin().split()))
def sin():
    return input()
def inin():
    return int(input())
def gcd(a,b): 
    if a == 0: 
        return b 
    return gcd(b % a, a) 
def lcm(a,b): 
    return (a*b) //gcd(a,b) 
for _ in range(1):
    n=inin()
    l=ain()
    f1,f2=0,0
    gc=lc=l[0]
    for i in range(1,n):
        gc=gcd(gc,l[i])
        if(f1==0):
            if(gcd(l[i],lc)!=1):f1=1
        if(f1==0):lc=lcm(lc,l[i])
    if(gc!=1):print("not coprime")
    else:
        if(f1):
            print("setwise coprime")
        else:
            print("pairwise coprime")
        
        
    
    
    

 
    
    
    
    
        
        
    
    
    
    


    




##def msb(n):n|=n>>1;n|=n>>2;n|=n>>4;n|=n>>8;n|=n>>16;n|=n>>32;n|=n>>64;return n-(n>>1) #2 ki power
##def pref(a,n,f):             
##    pre=[0]*n
##    if(f==0):         ##from beginning
##        pre[0]=a[0]
##        for i in range(1,n):
##            pre[i]=a[i]+pre[i-1]
##    else:              ##from end
##        pre[-1]=a[-1]
##        for i in range(n-2,-1,-1):
##            pre[i]=pre[i+1]+a[i]
##    return pre
##maxint=10**24 
##def kadane(a,size): 
##    max_so_far = -maxint - 1
##    max_ending_here = 0
##       
##    for i in range(0, size): 
##        max_ending_here = max_ending_here + a[i] 
##        if (max_so_far < max_ending_here): 
##            max_so_far = max_ending_here 
##  
##        if max_ending_here < 0: 
##            max_ending_here = 0   
##    return max_so_far
##def power(x, y):
##    if(y == 0):return 1
##    temp = power(x, int(y / 2))%mo
##    if (y % 2 == 0):return (temp * temp)%mo 
##    else:
##        if(y > 0):return (x * temp * temp)%mo 
##        else:return ((temp * temp)//x )%mo

Submission status: Time Limit Exceeded

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

pairwise = True
setwise = False


seki = 1
for i in range(N):
    seki *= A[i]
tmp = 0

for j in range(N):
    gcd = fractions.gcd(A[j],seki//A[j])
    if gcd != 1:
        pairwise = False
        if tmp == 0:
            tmp = gcd
        else:
            tmp = fractions.gcd(gcd,tmp)

    else:
        setwise = True

if tmp == 1:
    setwise = True

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

Submission status: Time Limit Exceeded

Solution code:
import math
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]]
n = int(input())
a = list(map(int, input().split()))
b = a[0]
for i in range(1, n): b = math.gcd(b, a[i])
if b != 1: print("not coprime")
else:
    data = primes(10**6)
    count = [0]*(len(data))
    for i in range(n):
        for j in range(len(data)):
            if a[i]%data[j] == 0: count[j] += 1
    x = 0
    for i in range(1, len(count)):
        x = max(x, count[i])
    print("setwise coprime") if x > 1 else print("pairwise coprime")

Submission status: Time Limit Exceeded

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

from math import gcd

g = a[0]
l = 1
f = True
for i in range(n):
    if f:
        x = gcd(a[i],l)
        if x!=1:
            f = False
        l = l*a[i]//x
    g = gcd(g,a[i])

if f:
    print('pairwise coprime')
elif g==1:
    print('setwise coprime')
else:
    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]
L = []
def factorization(n):
    temp = n
    K = []
    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
        if i in L:
          return True
        K.append( i )
    if temp!=1:
      if temp in L:
        return True
      K.append( temp )
    if L=={}:
      L[n] = 1
    L.extend( K )
    return False

for i in range(1, N):
    ans = math.gcd(ans, A[i])
    if ans == 1:
      break
if ans != 1:
  ret = "not 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:
import math
from functools import reduce

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

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

for i in range(n):
    is_pair_wise_coprime = True
    for j in range(i + 1, n):
        if math.gcd(numbers[i], numbers[j]) != 1:
            is_pair_wise_coprime = False
            break
    if not is_pair_wise_coprime:
        break
else:
    print('pairwise coprime')
    exit(0)

if gcd(numbers) == 1:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Time Limit Exceeded

Solution code:
import math
N = int(input())
Alst = list(map(int, input().split()))
l = len(Alst)

k = Alst[0]
for i in range(1, l):
    k = math.gcd(k, Alst[i])

if k == 1: 
    c = False
    for i in range(l):
        for j in range(i+1, l):
            k = math.gcd(Alst[i], Alst[j])
            if k != 1:
                c = True
                break
        if c:
            break

    if c:
        print('setwise coprime')

    else:
        print('pairwise coprime')

else:
    print('not coprime')

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9+7
lim = 200000
inv_t = [-1 for i in range(lim+1)]
factrial = [-1 for i in range(lim+1)]
factrial_inv = [-1 for i in range(lim+1)]


def mod_inv(x, mod=MOD):
    y, u, v, _x = mod, 1, 0, x
    while y:
        t = _x//y
        _x -= t*y
        _x, y = y, _x
        u -= t*v
        u, v = v, u
    u %= mod
    if u < 0:
        u += mod
    return u


def mod_pow(a, n, mod=MOD):
    res = 1
    while n:
        if n & 1:
            res = res*a % mod
        a = a*a % mod
        n >>= 1
    return res


def COMinit(max=lim, mod=MOD):
    factrial[0] = factrial_inv[0] = 1
    factrial[1] = factrial_inv[1] = 1
    inv_t[0] = inv_t[1] = 1
    for i in range(2, max):
        factrial[i] = factrial[i-1]*i % mod
        inv_t[i] = -inv_t[mod % i]*(mod//i) % mod
        factrial_inv[i] = factrial_inv[i-1]*inv_t[i] % mod


def comb(a, b, mod=MOD):
    if a < b:
        return 0
    if factrial[0] == -1:
        COMinit()
    return (factrial[a]*factrial_inv[b]*factrial_inv[a-b]) % mod


def prime_factor(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())
a = [int(_) for _ in input().split()]

ans = [0 for i in range(10**6)]
for i in range(n):
    temp = a[i]
    for i in range(2, int(-(-n**0.5//1))+1):
        f = True
        if temp % i == 0:
            ans[i] += 1
            while temp % i == 0:
                temp //= i
    if temp != 1:
        ans[temp] += 1


# print(ans[0:10])


if max(ans) == n:
    print("not coprime")
elif max(ans) == 1:
    print("pairwise coprime")
else:
    print("setwise coprime")

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
N = int(input())
A = list(map(int,input().split()))
def prime_factorize(n):
    a = deque()
    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 a
PA = deque()
c = 0
k = 0
mflag = 12
mnum = 0
for i in range(N):
  tA = A[i]
  a = prime_factorize(tA)
  a = set(a)
  PA.extend(a)
  la = len(a)
  c += la
  if la < mflag:
    mflag = la
    mnum = A[i]
am = set(PA)
cm = len(am)
if cm == c:
  print('pairwise coprime')
  sys.exit()
A.remove(mnum)  
am = prime_factorize(mnum)
am = set(am)
lA = len(A)
for i in am:
  k = 0
  for j in range(lA):
    if A[j] % i == 0:
      k += 1
  if k == lA:
    print('not coprime')
    sys.exit()
print('setwise 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 = list(map(int, input().split()))

pc_flag = True
for i in range(n):
  for j in range(n):
    if (j >= i):
      continue
    if (gcd(a[i], a[j]) != 1):
      pc_flag = False

if (pc_flag):
  print("pairwise coprime")
  exit()

if (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(" ")))
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
base=A[0]
if condition!=0:
    for i in range(1,len(A),1):
        base=gcd(base,A[i])
    if base==1:
        condition=1
    else:
        condition=2

ans=["pairwise coprime","setwise coprime","not coprime"]
print(ans[condition])

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import sys
import math

input = sys.stdin.readline

# 素因数分解O(√n)


def primeFactor(n):
    res = defaultdict(lambda: 0)
    for i in range(2, int(n**0.5)+1):
        while n % i == 0:
            res[i] += 1
            n = n // i
    if n != 1:
        res[n] = 1
    return res


def main():
    N = int(input())
    A = list(map(int, input().split()))
    primes = defaultdict(lambda: 0)
    pairs = True
    setp = True
    for i in range(N):
        pf = primeFactor(A[i])
        for k in pf.keys():
            primes[k] += 1
            if primes[k] != 1:
                pairs = False
            if primes[k] == N:
                setp = False
    if pairs:
        print('pairwise coprime')
    elif setp:
        print('setwise coprime')
    else:
        print('not coprime')


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def find_gcd(x, y): 
    while(y): 
        x, y = y, x % y 
  
    return x

n = int(input())
arr = list(map(int, input().split()))
coprime = []
gcd = find_gcd(arr[0], arr[1])
for i in range(2,n):
    gcd = find_gcd(gcd, arr[i])

if gcd != 1:
    print("not coprime")
else:
    for i in range(n-1):
        for j in range(i+1, n):
            if find_gcd(arr[i],arr[j]) != 1 and gcd == 1:
                print('setwise coprime')
                exit()
    print('pairwise coprime')

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N = int(input())
Ai = list(map(int, input().split(" ")))
pairwiseI = False
for i in range(N - 1):
    if pairwiseI:
        break
    for k in range(i + 1, N):
        if np.gcd(Ai[i], Ai[k]) != 1:
            pairwiseI = True
            break
if (not pairwiseI) == True:
    print("pairwise coprime")
else:
    gcdall = Ai[0]
    for i in range(1, N):
        gcdall = np.gcd(gcdall, np.gcd(Ai[i-1], Ai[i]))
    if gcdall == 1:
        print("setwise coprime")
    else:
        print("not coprime")

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int,input().split()))
l = [0 for _ in range(10**6+2)]
def fac(n):
    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
            l[i] += 1
    if temp!=1:
        l[temp] += 1

for i in range(n):
    fac(a[i])
bit = 0
for i in l:
    if i==n:
        print("not coprime")
        exit()
    if i!=0 and i!=1:
        bit =1 

if bit==1:
    print("setwise coprime")
else:
    print("pairwise coprime")

Submission status: Time Limit Exceeded

Solution code:
def main():
    n = int(input())
    a = sorted(list(map(int,input().split())))
    p = [i for i in range(2,a[-1]+1)]
    for i in range(len(p)-1):
        if p[i]==0:
            continue
        for j in range(i+1,len(p)):
            if p[j]%p[i] == 0:
                p[j]=0
    prm = []
    for p_ in p:
        if p_ != 0:
            prm.append(p_)
    for p in prm:
        cnt = 0
        for a_ in a:
            if a_%p==0:
                cnt += 1
        if cnt == n:
            print('not coprime')
            return
        if cnt > 1:
            print('setwise coprime')
            return
    print('pairwise coprime')


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
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]
import math
n=int(input())
alist=list(map(int, input().split()))
blist=[0]*1000001
for i in alist:
  for j in make_divisors(i):
    blist[j]+=1
cnt=1
for i in range(2,1000001):
  cnt=max(cnt,blist[i])
if cnt==1:
  print('pairwise coprime')
else:
  num=alist[0]
  for i in range(n):
    num=math.gcd(num,alist[i])
  if num==1:
    print('setwise coprime')
  else:
    print('not coprime')