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: Accepted

Solution code:
MAX_A = 10**6 + 1
MAX_P = MAX_A // 2
is_prim = [i%2==1 for i in range(MAX_P)]
is_prim[1] = False; is_prim[2] = True
for i in range(3, MAX_P):
    if not is_prim[i]: continue
    for j in range(i+i, MAX_P, i): is_prim[j] = False

def solve():
    C = [0] * MAX_A
    for a in A: C[a] += 1
    pairwise = True
    for p in [i for i in range(MAX_P) if is_prim[i]]:
        if sum(C[p::p]) > 1: pairwise = False
    if pairwise: return 'pairwise'
    from math import gcd
    g = 0
    for a in A: g = gcd(g, a)
    if g == 1: return 'setwise'
    return 'not'

n = int(input())
A = [*map(int, input().split())]
print(solve(), 'coprime')

Submission status: Accepted

Solution code:
import sys,bisect,string,math,time,functools,random,fractions
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
rep=range;R=range
def Golf():n,*t=map(int,open(0).read().split())
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def MI():return map(int,input().split())
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def NLI(n):return [[int(i) for i in input().split()] for i in range(n)]
def NLI_(n):return [[int(i)-1 for i in input().split()] for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def RA():return map(int,open(0).read().split())
def RLI(n=8,a=1,b=10):return [random.randint(a,b)for i in range(n)]
def RI(a=1,b=10):return random.randint(a,b)
def Rtest(T):
    case,err=0,0
    for i in range(T):
        inp=INP()
        a1,ls=naive(*inp)
        a2=solve(*inp)
        if a1!=a2:
            print((a1,a2),inp)
            err+=1
        case+=1
    print('Tested',case,'case with',err,'errors')
def GI(V,E,ls=None,Directed=False,index=1):
    org_inp=[];g=[[] for i in range(V)]
    FromStdin=True if ls==None else False
    for i in range(E):
        if FromStdin:
            inp=LI()
            org_inp.append(inp)
        else:
            inp=ls[i]
        if len(inp)==2:
            a,b=inp;c=1
        else:
            a,b,c=inp
        if index==1:a-=1;b-=1
        aa=(a,c);bb=(b,c);g[a].append(bb)
        if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1):
    #h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1) # sample usage
    mp=[boundary]*(w+2);found={}
    for i in R(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[boundary]+[mp_def[j] for j in s]+[boundary]
    mp+=[boundary]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def accum(ls):
    rt=[0]
    for i in ls:rt+=[rt[-1]+i]
    return rt
def bit_combination(n,base=2):
    rt=[]
    for tb in R(base**n):s=[tb//(base**bt)%base for bt in R(n)];rt+=[s]
    return rt
def gcd(x,y):
    if y==0:return x
    if x%y==0:return y
    while x%y!=0:x,y=y,x%y
    return y
def YN(x):print(['NO','YES'][x])
def Yn(x):print(['No','Yes'][x])
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)

mo=10**9+7
#mo=998244353
inf=float('inf')
FourNb=[(-1,0),(1,0),(0,1),(0,-1)];EightNb=[(-1,0),(1,0),(0,1),(0,-1),(1,1),(-1,-1),(1,-1),(-1,1)];compas=dict(zip('WENS',FourNb));cursol=dict(zip('LRUD',FourNb))
l_alp=string.ascii_lowercase
#sys.setrecursionlimit(10**9)
read=sys.stdin.buffer.read;readline=sys.stdin.buffer.readline;input=lambda:sys.stdin.readline().rstrip()

########################################################################################################################################################################
# Verified by
# https://yukicoder.me/problems/no/979
# https://atcoder.jp/contests/abc152/tasks/abc152_e

## return prime factors of N as dictionary {prime p:power of p}
## within 2 sec for N = 2*10**20+7
def primeFactor(N):
    i,n=2,N
    ret={}
    d,sq=2,99
    while i<=sq:
        k=0
        while n%i==0:
            n,k,ret[i]=n//i,k+1,k+1
        if k>0 or i==97:
            sq=int(n**(1/2)+0.5)
        if i<4:
            i=i*2-1
        else:
            i,d=i+d,d^6
    if n>1:
        ret[n]=1
    return ret

## return divisors of n as list
def divisor(n):
    div=[1]
    for i,j in primeFactor(n).items():
        div=[(i**k)*d for d in div for k in range(j+1)]
    return div

## return the list of prime numbers in [2,N], using eratosthenes sieve
## around 800 ms for N = 10**6  by PyPy3 (7.3.0) @ AtCoder
def PrimeNumSet(N):
    M=int(N**0.5)
    seachList=[i for i in range(2,N+1)]
    primes=[]
    while seachList:
        if seachList[0]>M:
            break
        primes.append(seachList[0])
        tmp=seachList[0]
        seachList=[i for i in seachList if i%tmp!=0]
    return primes+seachList


## retrun LCM of numbers in list b
## within 2sec for no of B = 10*5  and  Bi < 10**6
def LCM(b,mo=10**9+7):
    prs=PrimeNumSet(max(b))
    M=dict(zip(prs,[0]*len(prs)))
    for i in b:
        dc=primeFactor(i)
        for j,k in dc.items():
            M[j]=max(M[j],k)
    
    r=1
    for j,k in M.items():
        if k!=0:
            r*=pow(j,k,mo)
            r%=mo
    return r

show_flg=False
show_flg=True

ans=0

N=10**6
pr=PrimeNumSet(N)

n=I()
a=LI()
g=a[0]
for i in range(n-1):
    g=gcd(g,a[i+1])


A=max(a)
d=[[]for i in range(A+1)]
for p in pr:
    for j in range(1,A//p+1):
        d[p*j]+=p,


inc=dict()


if g==1:
    k=0
    for i in range(n):
        for p in d[a[i]]:
            if p in inc:
                k=1
                print(['pairwise coprime','setwise coprime','not coprime'][k])
                exit()
            inc[p]=1
else:
    k=2

print(['pairwise coprime','setwise coprime','not coprime'][k])

Submission status: Accepted

Solution code:
from math import gcd # Python3.6以降
# --------------------------------------------------------------

# n以下の素数列挙: O-nlogn
def primes(n):
    prs = []
    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
    for i in range(len(is_prime)):
        if is_prime[i]:
            prs.append(i)
    return prs

n    = int(input())
lis  = list(map(int,input().split()))
A    = 10**6
nlis = [0]*A
flg_pairwise = True

for i in range(n):
    nlis[lis[i]-1] += 1

for i in primes(A):
    cnt = 0
    for j in range(i-1,A,i):
        cnt += nlis[j]
    if cnt > 1:
        flg_pairwise = False
        break

if flg_pairwise:
    print('pairwise coprime')
else:
    for i in range(n-1):
        if i==0:
            tmp = gcd(lis[i],lis[i+1])
        else:
            tmp = gcd(tmp,lis[i+1])

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

Submission status: Accepted

Solution code:
from math import gcd # Python3.6以降
# --------------------------------------------------------------

# n以下の素数列挙: O-nlogn
# def primes(n):
#     prs = []
#     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
#     for i in range(len(is_prime)):
#         if is_prime[i]:
#             prs.append(i)
#     return prs

n    = int(input())
lis  = list(map(int,input().split()))
A    = 10**6
nlis = [0]*A
flg_pairwise = True

for i in range(n):
    nlis[lis[i]-1] += 1

for i in range(2,A):
    cnt = 0
    for j in range(i-1,A,i):
        cnt += nlis[j]
    if cnt > 1:
        flg_pairwise = False
        break

if flg_pairwise:
    print('pairwise coprime')
else:
    for i in range(n-1):
        if i==0:
            tmp = gcd(lis[i],lis[i+1])
        else:
            tmp = gcd(tmp,lis[i+1])

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

Submission status: Accepted

Solution code:
MAX_A = 10**6 + 1
is_prim = [True] * (MAX_A//2)
is_prim[0] = is_prim[1] = False
for i in range(2, MAX_A//2):
    if not is_prim[i]: continue
    for j in range(i+i, MAX_A//2, i): is_prim[j] = False

def solve():
    C = [0] * MAX_A
    for a in A: C[a] += 1
    pairwise = True
    for p in [i for i in range(MAX_A//2) if is_prim[i]]:
        if sum(C[p::p]) > 1: pairwise = False
    if pairwise: return 'pairwise'
    from math import gcd
    g = 0
    for a in A: g = gcd(g, a)
    if g == 1: return 'setwise'
    return 'not'

n = int(input())
A = [*map(int, input().split())]
print(solve(), 'coprime')

Submission status: Accepted

Solution code:
MAX_A = 10**6 + 1
is_prim = [True] * MAX_A
is_prim[0] = is_prim[1] = False
for i in range(2, MAX_A):
    if not is_prim[i]: continue
    for j in range(i+i, MAX_A, i): is_prim[j] = False

def solve():
    C = [0] * MAX_A
    for a in A: C[a] += 1
    pairwise = True
    for p in [i for i in range(MAX_A) if is_prim[i]]:
        if sum(C[p::p]) > 1: pairwise = False
    if pairwise: return 'pairwise'
    from math import gcd
    g = 0
    for a in A: g = gcd(g, a)
    if g == 1: return 'setwise'
    return 'not'


n = int(input())
A = [*map(int, input().split())]
print(solve(), 'coprime')

Submission status: Accepted

Solution code:
MAX_A = 10**6 + 1
is_prim = [True] * MAX_A
is_prim[0] = is_prim[1] = False
for i in range(2, MAX_A):
    if not is_prim[i]: continue
    for j in range(i+i, MAX_A, i): is_prim[j] = False
prim = [i for i in range(MAX_A) if is_prim[i]]

def solve():
    C = [0] * MAX_A
    for a in A: C[a] += 1
    pairwise = True
    for p in prim:
        if sum(C[p::p]) > 1: pairwise = False
    if pairwise: return 'pairwise'
    from math import gcd
    g = 0
    for a in A: g = gcd(g, a)
    if g == 1: return 'setwise'
    return 'not'


n = int(input())
A = [*map(int, input().split())]
print(solve(), 'coprime')

Submission status: Accepted

Solution code:
import functools
from math import gcd
N = int(input())
A = list(map(int, input().split()))
MAX = 10 ** 6 + 10

if functools.reduce(gcd, A) != 1:
    print("not coprime")
    exit()

prime_list = [i for i in range(MAX + 1)]
p = 2
while p * p <= MAX:
    if prime_list[p] == p:
        for q in range(2*p, MAX+1, p):
            if prime_list[q] == q:
                prime_list[q] = p
    p += 1

prime = set()
for a in A:
    tmp = set()
    while a > 1:
        tmp.add(prime_list[a])
        a //= prime_list[a]
    for p in tmp:
        if p in prime:
            print("setwise coprime")
            exit()
        prime.add(p)
else:
    print("pairwise coprime")

Submission status: Accepted

Solution code:
import math

MAX=10**6+3
table = list(range(MAX))
i=2
n=MAX
while i<n:
    table[i] = 2
    i+=2
p=3
while p*p<=n:
    if table[p]<p:
        p+=2
        continue
    x=p
    while x<=n:
        table[x]=p
        x+=p
    p+=2


def primeFactorSet(n):
    result = set()
    while table[n]!=1:
        result.add(table[n])
        n //= table[n]
    return result
    

n = int(input())
A = list(map(int,input().split()))
pairwise = True
flags = [False for _ in range(MAX)]

for i in range(n):
    a=A[i]
    if pairwise:
        t = primeFactorSet(a)
        for p in t:
            if flags[p]:
                pairwise = False
                break
            flags[p]=True
    if i==0:
        g=a
    else:
        g=math.gcd(g,a)
    
if g>1:
    print("not coprime")
elif pairwise:
    print("pairwise coprime")
else:
    print("setwise coprime")

Submission status: Accepted

Solution code:
# Date [ 2020-08-29 21:59:01 ]
# Problem [ e.py ]
# Author Koki_tkg
# After Contest

import sys
import math
# import bisect
# import numpy as np
# from decimal import Decimal
# from numba import njit, i8, u1, b1 #JIT compiler
# from itertools import combinations, product
# from collections import Counter, deque, defaultdict

# sys.setrecursionlimit(10 ** 6)
MOD = 10 ** 9 + 7
INF = 10 ** 9
PI = 3.14159265358979323846

def read_str():      return sys.stdin.readline().strip()
def read_int():      return int(sys.stdin.readline().strip())
def read_ints():     return map(int, sys.stdin.readline().strip().split())
def read_ints2(x):   return map(lambda num: int(num) - x, sys.stdin.readline().strip().split())
def read_str_list(): return list(sys.stdin.readline().strip().split())
def read_int_list(): return list(map(int, sys.stdin.readline().strip().split()))
def GCD(a: int, b: int) -> int: return b if a%b==0 else GCD(b, a%b)
def LCM(a: int, b: int) -> int: return (a * b) // GCD(a, b)

# osa_k 法 O(NloglogN + logA)
class PrimeFactorization():
    def __init__(self, num):
        self.num = num
        self.factor_table = [0] * (num + 1)
        self.eratosthenes()

    def eratosthenes(self):
        for i in range(2, self.num + 1):
            if self.factor_table[i] == 0:
                self.factor_table[i] = i
                for j in range(i * i, self.num + 1, i):
                    if self.factor_table[j] == 0:
                        self.factor_table[j] = i
    
    def factorization(self, a):
        now = a
        ret = []
        while now > 1:
            cnt = 0
            prime = self.factor_table[now]
            while now % prime == 0:
                cnt += 1
                now //= prime
            ret.append((prime, cnt))
        return ret

def Main():
    n = read_int()
    a = read_int_list()
    max_num = max(a)

    pf = PrimeFactorization(max_num + 1)
    used_prime = [False] * (max_num + 1)
    for x in a:
        factor = pf.factorization(x)
        for prime, cnt in factor:
            if used_prime[prime]:
                break
            used_prime[prime] = True
        else:
            continue
        break
    else:
        print('pairwise coprime')
        exit()

    gcd_num = a[0]
    for x in a[1:]:
        gcd_num = math.gcd(gcd_num, x)
    print('setwise coprime' if gcd_num == 1 else 'not coprime')

if __name__ == '__main__':
    Main()

Submission status: Accepted

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

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

#エラストテネスのふるい
def create_sieve(n):
  sieve=[0]*(n+1)
  for i in range(2,n+1):
    if sieve[i]==0:
      for j in range(i*i,n+1,i):
        sieve[j]=i
  return sieve

#高速素因数分解
def fast_factorization(n, sieve):
  prime={}
  while n>1:
    p=sieve[n]
    #nが素数の場合
    if p==0:
      prime[n]=prime.get(n,0)+1
      break
    #nが素数ではない場合
    else:
      prime[p]=prime.get(p,0)+1
      n=n//p
  return prime

check=set()
if setwise_coprime(a)==1:
  #素因数のダブリをcheck
  sieve=create_sieve(10**6)
  for i in range(n):
    if a[i]!=1:
      s=fast_factorization(a[i], sieve)
      for i in s:
        if i in check:
          print("setwise coprime")
          sys.exit()
        else:
          check.add(i)
  print("pairwise coprime")    
else:
  print("not coprime")

Submission status: Accepted

Solution code:
from fractions import gcd

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

A = max(As)
lst = [0]*(A+1)
rlt = [0]*(A+1)

for i in range(2, A+1):
  if lst[i] > 0:
    continue
  j = 1
  while i*j <= A:
    if lst[i*j] == 0:
      lst[i*j] = i
    j += 1
  if j == 1:
    break
    
for a in As:
  tmp = -1
  while a > 1:
    if tmp != lst[a]:
      rlt[lst[a]] += 1
      tmp = lst[a]
    a //= lst[a]

r = max(rlt) 

if r < 2:
  print('pairwise coprime')
elif r < N:
  print('setwise coprime')
else:
  print('not coprime')

Submission status: Accepted

Solution code:
import math
from functools import reduce

n = int(input())
a_list = list(map(int, input().split()))
max = 10 ** 6 + 1
memo = [0] * max

for a in a_list:
    memo[a] += 1

for i in range(2, max):
    if sum(memo[i::i]) > 1:
        if reduce(math.gcd, a_list) == 1:
            print("setwise coprime")
            exit()
        else:
            print("not coprime")
            exit()

print("pairwise coprime")

Submission status: Accepted

Solution code:
# pythonの場合、ライブラリ関数でgcdがある？ただし、配列まとめてというわけではない模様
from math import gcd

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

	pc = True
	maxA = max(A)

	cnts = [ 0 for _ in range(maxA+1) ]
	for a in A:
		cnts[a] += 1
	for i in range(2,maxA):
		if pc:
			# 素因数ごとに、A内での登場回数を数える
			# 2つあったらその2つのcommon dividerとして、1以外にそれがあることが確定する
			cnt = 0
			for j in range(i,maxA+1,i):
				cnt += cnts[j]
				if 1 < cnt:
					# Aの素因数で重複があれば、pcでない
					pc = False
					break

	sc = False

	if pc == False:
		gcdResult = 0
		for a in A:
			# 配列全要素に対してgcdを呼んでるが、結果的に、それが1になればsc、ならなければnot sc
			gcdResult=gcd(gcdResult,a)
		if gcdResult == 1:
			sc = True

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






if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
li = [0] * 1100000
is_prime = [True] * 1100000
is_prime[0] = is_prime[1] = False
for i in a:
    li[i] += 1
is_pairwise = True
for i in range(2, 1100000):
    if is_prime[i]:
        cnt = 0
        for j in range(i, 1100000, i):
            is_prime[j] = False
            cnt += li[j]
        if cnt == n:
            print("not coprime")
            exit()
        if cnt > 1:
            is_pairwise = False
if is_pairwise:
    print("pairwise coprime")
else:
    print("setwise coprime")

Submission status: Accepted

Solution code:
import math
from functools import reduce
L = 10**6 + 1
n = int(input())
a_list = list(map(int, input().split()))
memo = [0] * L

for a in a_list:
    memo[a] += 1

for i in range(2, L):
    if sum(memo[i::i]) > 1:
        if reduce(math.gcd, a_list) == 1:
            print("setwise coprime")
            exit()
        else:
            print("not coprime")
            exit()

print("pairwise coprime")

Submission status: Accepted

Solution code:
import math

MAX_N = 10**6+10

N = int(input())
A = list(map(int,input().split()))
B = [0] * MAX_N
for a in A:
    B[a] += 1

cnt = [0] * MAX_N
for i in range(2,MAX_N):
    for d in range(i, MAX_N, i):
        cnt[i] += B[d]

if N in cnt:
    print("not coprime")
else:
    for c in cnt:
        if c > 1:
            print("setwise coprime")
            exit()
    print("pairwise coprime")

Submission status: Accepted

Solution code:
def e_coprime():
    from math import gcd
    from functools import reduce
    N = int(input())
    A = [int(i) for i in input().split()]

    def sieve(n):
        ret = list(range(n + 1))
        for j in range(2, int(n**0.5) + 1):
            for k in range(j, n + 1, j):
                if k == ret[k]:
                    ret[k] = j
        return ret

    d = sieve(max(A))
    prime_factor = set()
    for a in A:
        t = set()
        while a > 1:
            t.add(d[a])
            a //= d[a]
        if prime_factor & t:
            break
        prime_factor |= t
    else:
        return 'pairwise coprime'

    if reduce(lambda x, y: gcd(x, y), A) == 1:
        return 'setwise coprime'
    return 'not coprime'

print(e_coprime())

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**6)
INF = 10 ** 9 + 1  # sys.maxsize # float("inf")
MOD = 10 ** 9 + 7


def debug(*x):
    print(*x, file=sys.stderr)


def precompute():
    maxAS = 1000000
    eratree = [0] * (maxAS + 10)
    for p in range(2, maxAS + 1):
        if eratree[p]:
            continue
        # p is prime
        eratree[p] = p
        x = p * p
        while x <= maxAS:
            if not eratree[x]:
                eratree[x] = p
            x += p

    import pickle
    pickle.dump(eratree, open("eratree.pickle", "wb"))


def solve(N, AS):
    import pickle
    eratree = pickle.load(open("eratree.pickle", "rb"))
    num_division = 0

    from collections import defaultdict
    count = defaultdict(int)
    for a in AS:
        factors = []
        while a > 1:
            d = eratree[a]
            factors.append(d)
            a //= d
            num_division += 1
        # debug(": ", factors)
        for f in set(factors):
            count[f] += 1

    # debug(": num_division", num_division)
    if any(x == N for x in count.values()):
        return "not coprime"
    if any(x >= 2 for x in count.values()):
        return "setwise coprime"
    return "pairwise coprime"


def main():
    # parse input
    N = int(input())
    AS = list(map(int, input().split()))
    print(solve(N, AS))


# tests
T1 = """
3
3 4 5
"""
TEST_T1 = """
>>> as_input(T1)
>>> main()
pairwise coprime
"""

T2 = """
3
6 10 15
"""
TEST_T2 = """
>>> as_input(T2)
>>> main()
setwise coprime
"""

T3 = """
3
6 10 16
"""
TEST_T3 = """
>>> as_input(T3)
>>> main()
not coprime
"""

T4 = """
3
100000 100001 100003
"""
TEST_T4 = """
>>> as_input(T4)
>>> main()
pairwise coprime
"""


def _test():
    import doctest
    doctest.testmod()
    g = globals()
    for k in sorted(g):
        if k.startswith("TEST_"):
            doctest.run_docstring_examples(g[k], g, name=k)


def as_input(s):
    "use in test, use given string as input file"
    import io
    f = io.StringIO(s.strip())
    g = globals()
    g["input"] = lambda: bytes(f.readline(), "ascii")
    g["read"] = lambda: bytes(f.read(), "ascii")


input = sys.stdin.buffer.readline
read = sys.stdin.buffer.read

if sys.argv[-1] == "-t":
    print("testing")
    _test()
    sys.exit()

if sys.argv[-1] == 'ONLINE_JUDGE':
    precompute()
elif sys.argv[-1] != "DONTCALL":
    import subprocess
    subprocess.call("pypy3 Main.py DONTCALL", shell=True, stdin=sys.stdin, stdout=sys.stdout)
else:
    main()

Submission status: Accepted

Solution code:
from math import gcd
n = int(input())
A = list(map(int, input().split()))
min_A = min(A)
max_A = max(A)

def is_pairwise():
    arr = [0] * (max_A + 1)
    for a in A:
        arr[a] += 1
    max_counter = 0
    for num in range(2, max_A + 1):
        counter = 0
        for i in range(1, 10**6 + 1):
            try:
                counter += arr[num * i]
            except:
                break
        max_counter = max(max_counter, counter)
    if max_counter == 1:
        return True
    else:
        return False

if min_A == 1 and max_A == 1:
    print("pairwise coprime")
elif min_A == 1 and max_A != 1:
    A = [num for num in A if num != 1]
    if is_pairwise():
        print("pairwise coprime")
    else:
        print("setwise coprime")
else:
    if is_pairwise():
        print("pairwise coprime")
    else:
        g = A[0]
        for a in A:
            g = gcd(a, g)
        if g == 1:
            print("setwise coprime")
        else:
            print("not coprime")

Submission status: Accepted

Solution code:
N = int(input())
A = [int(x) for x in input().split()]

# M以下の整数の素因数分解を高速に
# 前処理O(MloglogM)
# 一計算O(logK)
def mae_syori(M):
    D = [0] * (M + 1)
    for i in range(2, M+1):
        if D[i] != 0: continue
    #     print(i, list(range(i*2, M + 1, i)))
        for j in range(i*2, M+1, i):
            if D[j] == 0:
                D[j] = i
    return D

def p_bunkai(K):
    assert 2 <= K <= len(D)-1
    k = K
    ret = []
    while True:
        if k == 1:
            break
        if D[k] == 0:
            ret.append((k, 1))
            break
        else:
            p = D[k]
            count = 0
            while k % p == 0:
                count += 1
                k //= p
            ret.append((p, count))
    return ret
 

# 最大公約数
# ユークリッドの互除法
def my_gcd(a, b):
    if b == 0:
        return a
    else:
        return my_gcd(b, a%b)

c_gcd = A[0]
for a in A:
    c_gcd = my_gcd(c_gcd, a)

if c_gcd == 1:
    max_A = max(A)
    D = mae_syori(max_A)
    yakusu = set()
    ok = True
    for a in A:
        if a == 1: continue
        p_bunkai_result = p_bunkai(a)
        p_list = [p[0] for p in p_bunkai_result]
        for p in p_list:
            if p not in yakusu:
                yakusu.add(p)
            else:
                ok = False
        if not ok:
            break
    if ok:
        print('pairwise coprime')
    else:
        print('setwise coprime')
else:
    print('not coprime')

Submission status: Accepted

Solution code:
def primes(n):
    is_prime = [-1] * (n + 1)
    is_prime[0] = 0
    is_prime[1] = 1
    for i in range(2, n + 1):
        if is_prime[i] != -1:
            continue
        for j in range(i, n + 1, i):
            if is_prime[j] == -1:
                is_prime[j] = i
    return is_prime

n = int(input())
a = list(map(int,input().split()))
s = primes(max(a))
d = {}
for i in a:
    now = i
    while s[now] != 1:
        t = s[now]
        d[t] = d.get(s[now],0) + 1
        while now % t == 0:
            now //= t
            
                
            
    
flag = True
for v in d.values():
    if v == n:
        print("not coprime")
        exit()
    elif v > 1:
        flag = False

if flag:
    print("pairwise coprime")
else:
    print("setwise coprime")

Submission status: Accepted

Solution code:
import sys
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()
from functools import reduce
from math import gcd
def resolve():
    n = int(input())
    A = list(map(int, input().split()))

    if reduce(gcd, A) != 1:
        print("not coprime")
        return

    M = max(A)
    sieve = list(range(M + 1))
    primes = []

    for i in range(2, M + 1):
        if sieve[i] == i:
            primes.append(i)
        j = 0
        for p in primes:
            if not (p <= sieve[i] and i * p <= M):
                break
            sieve[i * p] = p

    used = set()
    for a in A:
        primes = set()
        while a > 1:
            p = sieve[a]
            primes.add(p)
            a //= p
        for p in primes:
            if p in used:
                print("setwise coprime")
                return
            used.add(p)

    print("pairwise coprime")
resolve()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
def main():
    from math import gcd

    N = int(input())
    A = []
    INF = 10 ** 6 + 5
    frequency = [0] * INF
    for a in [int(x) for x in input().split()]:
        A.append(a)
        frequency[a] += 1
    
    pairwise = True
    for i in range(2, INF):
        cnt = 0
        for j in range(i, INF, i):
            cnt += frequency[j]
        if cnt > 1:
            pairwise = False
    if pairwise:
        print("pairwise coprime")
        return

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
MAX_A = 10**6 + 1

def prim_gen():
    num = [i%2==1 for i in range(MAX_A)]
    num[0] = False; num[2] = True
    prim = set()
    prim.add(2)
    for i in range(3, MAX_A, 2):
        if num[i]: prim.add(i)
        for j in range(i+i, MAX_A, i): num[j] = False
    return prim

def solve():
    C = [0] * MAX_A
    for a in A: C[a] += 1
    pairwise = True
    for p in prim:
        if sum(C[p:MAX_A:p]) > 1: pairwise = False
    if pairwise: return 'pairwise'
    from math import gcd
    g = 0
    for a in A: g = gcd(g, a)
    if g == 1: return 'setwise'
    return 'not'

n = int(input())
A = [*map(int, input().split())]
prim = prim_gen()
print(solve(), 'coprime')

Submission status: Accepted

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

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

NMAX = 10**6+2
divisors = [i for i in range(NMAX+1)]
p=2
while p*p <=NMAX:
    if divisors[p]==p:
        for r in range(2*p,NMAX+1,p):
            if divisors[r]==r:
                divisors[r]=p
    p+=1
    
from collections import defaultdict
def soinsu_osak(to_devide):
    d = defaultdict(int)
    while to_devide>1:
        d[divisors[to_devide]]+=1
        to_devide //= divisors[to_devide]
    return list(d.keys())

been=[0]*NMAX
pair_wise=True
f=False
for aa in A:
    soinsu = soinsu_osak(aa)
    for s in soinsu:
        if been[s]==0:
            been[s]=1
        else:
            pair_wise=False
            f=True
            break
    if f:
        break

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

Submission status: Accepted

Solution code:
n = int(input())
A = [*map(int, input().split())]
def solve():
    MAX_A = 10**6 + 1
    C = [0] * MAX_A
    for a in A: C[a] += 1
    pairwise = True
    if sum(C[2:MAX_A:2]) > 1: pairwise = False
    for i in range(3, MAX_A, 2):
        if sum(C[i:MAX_A:i]) > 1: pairwise = False
    if pairwise: return 'pairwise'
    from math import gcd
    g = 0
    for a in A: g = gcd(g, a)
    if g == 1: return 'setwise'
    return 'not'
print(solve(), 'coprime')

Submission status: Accepted

Solution code:
#E
from math import gcd
N=int(input())
A=list(map(int,input().split()))
GCD=A[0]
for i in range(1,N):
    GCD=gcd(GCD,A[i])
    
def Fast_PFact(n):
    List=[0 for i in range(n+1)]
    List[1]=1
    for i in range(2,n+1):
        if List[i]==0:
            cnt=1
            while i*cnt<=n:
                List[i*cnt]=i
                cnt+=1
    return List

if GCD==1:
    P=Fast_PFact(10**6)
    L=[False for i in range(10**6+1)]
    flag=False
    for i in range(N):
        a=A[i]
        while a>1:
            if L[P[a]]:
                flag=True
                break
                
            else:
                L[P[a]]=True
                divisor=P[a]
                while divisor==P[a]:
                    a=int(a/divisor)        
    if flag:
        ans="setwise coprime"
    else:
        ans="pairwise coprime"
else:
    ans="not coprime"
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
A = [*map(int, input().split())]
def solve():
    MAX_A = 10**6 + 1
    C = [0] * MAX_A
    for a in A: C[a] += 1
    pairwise = True
    for i in range(2, MAX_A):
        if sum(C[i:MAX_A:i]) > 1: pairwise = False
    if pairwise: return 'pairwise'
    from math import gcd
    g = 0
    for a in A: g = gcd(g, a)
    if g == 1: return 'setwise'
    return 'not'
print(solve(), 'coprime')