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:
import sys
import math
from collections import defaultdict, deque, Counter
from copy import deepcopy
from bisect import bisect, bisect_right, bisect_left
from heapq import heapify, heappop, heappush
    
input = sys.stdin.readline
def RD(): return input().rstrip()
def F(): return float(input().rstrip())
def I(): return int(input().rstrip())
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 Init(H, W, num): return [[num for i in range(W)] for j in range(H)]
    
    
def main():
    N = I()
    mylist = LI()
    max_num = max(mylist)
    max_num2 = math.ceil(math.sqrt(max_num))
    D = [True]* (max_num+1)
    D[0] = D[1] = False
    mylist = Counter(mylist)
    setwise = True
    pairwise = True

        
    for i in range(2, max_num+1):
        temp = 0
        if D[i]:
            for j in range(i, max_num+1, i):
                D[j] = False
                
                try:
                    temp+=mylist[j]
                except:
                    pass

            if temp == N:
                print("not coprime")
                sys.exit()
            if temp >= 2:
                pairwise = False

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

            
    
    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import numpy as np
from numba import njit


n = int(input())
arr = np.array(list(map(int, input().split())))


n = 10**6 + 1
primes = set(range(3, n+1, 2))

for i in range(3, int(n**0.5+1)):
    primes.difference_update(range(i*2, n+1, i))
primes.add(2)


@njit
def solve(arr, primes):
    cnt = np.bincount(arr)
    for p in primes:
        if (cnt[p::p]).sum() > 1:
            return False
    else:
        return True


if np.gcd.reduce(arr) != 1:
    print("not coprime")
elif solve(arr, primes):
    print("pairwise coprime")
else:
    print("setwise coprime")

Submission status: Accepted

Solution code:
from math import gcd
n = int(input())
a = [int(i) for i in input().split()]

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

m = max(a)
fac = [1]*(m+1)
for i in range(2,m+1):
    if fac[i] != 1:
      continue
    for j in range(i,m+1,i):
      fac[j] = i
      
s = set()
for i in range(n):
    x = fac[a[i]]
    if x == 1: 
      continue
    if x in s:
      print("setwise coprime")
      exit()
    s.add(x)
print("pairwise coprime")

Submission status: Accepted

Solution code:
import math

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

dp=[0 for _ in range(1000001)]

for d in a:
  dp[d]+=1
  
ch1=0
for i in  range(2,1000001):
  ch=0
  x=i
  while x<=1000000:
    ch+=dp[x]
    x+=i
  if ch>1:
    ch1+=1
    
if ch1==0:
  print('pairwise coprime')
  
else:
  g=a[0]
  for h in range(1,n):
    g=math.gcd(g,a[h])
    
  if g==1:
    print('setwise coprime')
    
  else:
    print('not coprime')

Submission status: Accepted

Solution code:
from math import gcd, sqrt, ceil
from functools import reduce

# def sieve(n):
#     A = list(range(n+1))
#     for i in range(2, n+1 ,2):
#         A[i] = 2
#     for j in range(3, ceil(sqrt(n+1))+1, 2)[::-1]:
#         for i in range(j, n+1, j):
#             A[i] = j
#     return A

# def factorize(n, A):
#     factors = set()
#     while n != 1:
#         f = A[n]
#         factors.add(f)
#         n //= f
#     return factors

def factorize(n):
    factors = set()
    if n % 2 == 0:
        factors.add(2)
        n //= 2
    while n % 2 == 0:
        n //= 2
    for i in range(3, ceil(sqrt(n + 1)) + 1):
        if n % i == 0:
            factors.add(i)
            n //= i
        while n % i == 0:
            n //= i
    if n > 2:
        factors.add(n)
    return factors

_, *aa = map(int, open(0).read().split())

def main(aa):
    pair_co = True
#     A = sieve(10**6)
    all_factors = [0] * (10**6+1)
    for a in aa:
        factors = factorize(a)
#         factors = factorize(a, A)
        for factor in factors:
            if all_factors[factor]:
                pair_co = False
                break
            else:
                all_factors[factor] = 1
        if not pair_co:
            break
    if pair_co:
        return 'pairwise coprime'
    elif reduce(gcd, aa) == 1:
        return 'setwise coprime'
    else:
        return 'not coprime'

print(main(aa))

Submission status: Accepted

Solution code:
import math
from functools import reduce

N = int(input())
A = list(map(int, input().split()))
MAX = 10**6 + 1

cut = [2 for _ in range(MAX)]
for i in range(3, MAX, 2):
    if cut[i] != 2:
        continue
    for j in range(i, MAX, i):
        cut[j] = i

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

already = set()
for a in A:
    now = set()
    while a != 1:
        if cut[a] in already:
            print('setwise coprime')
            exit()
        now.add(cut[a])
        a //= cut[a]
    already |= now

print('pairwise coprime')

Submission status: Accepted

Solution code:
import math


def resolve():
    n = int(input())
    A = list(map(int, input().split()))
    M = max(A) + 1
    C = [0 for i in range(M)]
    for a in A:
        C[a] += 1

    pairwise = True
    for i in range(2, M):
        cnt = 0
        for j in range(i, M, i):
            cnt += C[j]

        if cnt > 1:
            pairwise = False

    if pairwise:
        print("pairwise coprime")
        return

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

    if g == 1:
        print("setwise coprime")
        return

    print("not coprime")

resolve()

Submission status: Accepted

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):
    global dt
    if num&1 == 0:
        num >>= 1
        if dt[2]:
            dt[2] = 0
        else:
            return 'setwise coprime'
    while num&1 == 0:
        num >>= 1
    for i in range(3,int(sqrt(num))+1,2):
        if num%i == 0:
            num //= i
            if dt[i]:
                dt[i] = 0
            else:
                return 'setwise coprime'
        while num%i == 0:
            num //= i
    if num>2:
        if dt[num]:
            dt[num] = 0
        else:
            return 'setwise coprime'
    return 'pairwise coprime'

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:
        if pfact(i) == 'setwise coprime':
            ans = 'setwise coprime'
            break
print(ans)

Submission status: Accepted

Solution code:
from math import gcd, sqrt, ceil
from functools import reduce

def sieve(n):
    A = list(range(n+1))
    for i in range(2, n+1 ,2):
        A[i] = 2
    for j in range(3, ceil(sqrt(n+1))+1, 2)[::-1]:
        for i in range(j, n+1, j):
            A[i] = j
    return A

def factorize(n, A):
    factors = set()
    while n != 1:
        f = A[n]
        factors.add(f)
        n //= f
    return factors

_, *aa = map(int, open(0).read().split())

def main(aa):
    pair_co = True
    A = sieve(10**6)
    all_factors = [0] * (10**6+1)
    for a in aa:
        factors = factorize(a, A)
        for factor in factors:
            if all_factors[factor]:
                pair_co = False
                break
            else:
                all_factors[factor] = 1
        if not pair_co:
            break
    if pair_co:
        return 'pairwise coprime'
    elif reduce(gcd, aa) == 1:
        return 'setwise coprime'
    else:
        return 'not coprime'

print(main(aa))

Submission status: Accepted

Solution code:
# Aはリスト、nはリストの最大値
def f2(n,A):
    s=[int(i) for i in range(0,n+1)]
    a={}
    for i in range(2,int(n**0.5)+1):
        if s[i]!=i:
            continue
        for j in range(i,n+1,i):
            s[j]=i

    for i in range(2,n+1):
        if s[i]==i:
            a[i]=1

    l=len(A)
    p=[[] for i in range(l)]
    for i in range(l):
        x=A[i]
        while x!=1:
            p[i].append(s[x])
            if a[s[x]]==0:
                return False
            x//=s[x]


        for j in p[i]:
            a[j]=0

    return True

from math import gcd
N=int(input())
A=[int(i) for i in input().split()]
a=max(A)
p=f2(a,A)


if p:
    print('pairwise coprime')
else:
    g=A[0]
    for i in range(1,len(A)):
        g=gcd(g,A[i])
        if g==1:
            break
    if g==1:
        print('setwise coprime')
    else:
        print('not coprime')

Submission status: Accepted

Solution code:
from math import gcd

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

g_all = A[0]
for a in A[1:]:
    g_all = gcd(g_all, a)

if g_all > 1:
    print('not coprime')
    quit()

def sieve(n):
    if n <= 1:
        return []
    elif n == 2:
        return [2]
    len_list = (n + 1) // 2
    len_sqrt = int(len_list**0.5) + 1
    flags = [True] * len_list
    flags[0] = False
    for i in range(len_sqrt):
        if flags[i]:
            w = i*2 + 1
            start = (w ** 2) // 2
            for j in range(start, len_list, w):
                flags[j] = False
    return [2] + [i*2+1 for i in range(len_list) if flags[i]]



appeared = [False] * (10**6 + 1)
primes = sieve(10**3)
for a in A:
    if a == 1:
        continue
    for p in primes:
        if a % p == 0:
            if appeared[p]:
                print('setwise coprime')
                quit()
            appeared[p] = True
            while a % p == 0:
                a //= p
    
    if a != 1:
        if appeared[a]:
            print('setwise coprime')
            quit()
        
        appeared[a] = True

print('pairwise coprime')

Submission status: Accepted

Solution code:
import sys
from math import gcd
from functools import reduce

input = sys.stdin.readline

ub = 10 ** 6

smallest_prime_factor = list(range(ub + 1))
for p in reversed(range(2, len(smallest_prime_factor))):
    if p == smallest_prime_factor[p]:
        for i in range(2 * p, len(smallest_prime_factor), p):
            smallest_prime_factor[i] = p


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

ans = ""
prime_factors = set()
for ai in a:
    tmp = ai
    while tmp != 1:
        p = smallest_prime_factor[tmp]
        if p in prime_factors:
            break
        prime_factors.add(p)
        while tmp % p == 0:
            tmp //= p
    else:
        continue
    break
else:
    ans = "pairwise coprime"

if ans == "":
    if reduce(gcd, a) == 1:
        ans = "setwise coprime"
    else:
        ans = "not coprime"
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

def gcd(a, b):
    if a < b:
        return gcd(b, a)
    while b > 0:
        a, b = b, a % b
    return a

def sieve_of_eratosthenes(n):
    sieve = [0] * (n+1)
    sieve[0] = 1 #素数でない
    sieve[1] = 1 #素数でない
    for i in range(2, n):
        if sieve[i] == 0:
            for j in range(2, n // i + 1):
                sieve[i * j] = i
    return sieve

def factorize_by_sieve_of_eratosthenes(x, sieve):
    factor = defaultdict(int)
    while sieve[x]:
        factor[sieve[x]] += 1
        x //= sieve[x]
    factor[x] += 1
    return factor

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

sieve = sieve_of_eratosthenes(a_list[-1])
pairwise = True
setwise = True
primes = set()
x = a_list[0]
for a in a_list:
    x = gcd(x, a)
    if pairwise and a != 1:
        factor = set(factorize_by_sieve_of_eratosthenes(a, sieve).keys())
        if not primes.isdisjoint(factor):
            pairwise = False
        else:
            primes |= factor

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

Submission status: Accepted

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

A = sorted(A,reverse = True)
prime = [0] * (10**6+1)
eratos = [True] * (A[0] + 1)
D = [0] * (A[0]+1)
D[1] = 1
for i in range(2,A[0] + 1):
  if not eratos[i]:
    continue
  else:
    for j in range(i,A[0] + 1,i):
      if not D[j]:
        D[j] = i
      if j!=i:
      	eratos[j] = False
  
for a in A:
  while a!=1:
    x = D[a]
    while a%x==0:
      a//=x
    prime[x] += 1

if max(prime)<=1:
  print('pairwise coprime')
  
elif max(prime)!=N:
  print('setwise coprime')
else:
  print('not coprime')

Submission status: Accepted

Solution code:
from collections import defaultdict
import math

def Sieve_of_Eratosthenes(maxA):
    lst = [-1]*(maxA+1)
    lst[0] = 0
    lst[1] = 1
    for i in range(2, maxA+1):
        if lst[i] == -1:
            for g in range(i, maxA+1, i):
                if lst[g] == -1:
                    lst[g] = i
    return lst

def factorization(n):  # 「n = 1」はダメ！！！
    d = defaultdict(int)
    now = n
    while True:
        if now == lst[now]:
            if now != 1:
                d[now] += 1
            break
        r = lst[now]
        while now % r == 0:
            now //= r
            d[r] += 1
    return d

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

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

if g == 1:
    d = defaultdict(int)
    maxA = max(a)
    lst = Sieve_of_Eratosthenes(maxA)
    for m in a:
        fs = factorization(m)
        for f in fs.keys():
            d[f] += 1
    for f in d.values():
        if f != 1:
            print("setwise coprime")
            exit()
    print("pairwise coprime")
else:
    print("not coprime")

Submission status: Accepted

Solution code:
from math import gcd

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

g_all = A[0]
for a in A[1:]:
    g_all = gcd(g_all, a)

if g_all > 1:
    print('not coprime')
    quit()

def sieve(n):
    is_prime = [True for _ in range(n+1)]
    is_prime[0] = False
    for i in range(2, n+1):
        if is_prime[i-1]:
            j = 2 * i
            while j <= n:
                is_prime[j-1] = False
                j += i
    table = [ i for i in range(1, n+1) if is_prime[i-1]]
    return is_prime, table


appeared = [False] * (10**6 + 1)
primes = sieve(10**3)[1]
for a in A:
    if a == 1:
        continue
    for p in primes:
        if a % p == 0:
            if appeared[p]:
                print('setwise coprime')
                quit()
            appeared[p] = True
            while a % p == 0:
                a //= p
    
    if a != 1:
        if appeared[a]:
            print('setwise coprime')
            quit()
        
        appeared[a] = True

print('pairwise coprime')

Submission status: Accepted

Solution code:
import sys
N = int(input())
A = list(map(int, input().split())) 
MAX = 10**6

not_pairwise_coprime = False #pairwise coprimeでないことを示すbool値(のちに更新)

# Aの要素に重複がある場合、少なくともpairwise coprimeではない
Ct = [0 for _ in range(MAX+1)]
for a in A:
  Ct[a] += 1 
if max(Ct[2:MAX+1]) > 1:
  not_pairwise_coprime = True
  
if max(Ct[2:MAX+1]) == N: # 全ての要素が等しい場合(例外処理)
  print("not coprime")
  sys.exit()
  
A = set(A) #集合型に書き換える(「q in A」をO(1)で判定するため)
N = len(A)

for p in range(2,MAX+1):
  ct = 0 #pの倍数の個数を求める
  for q in range(p,MAX+1,p): #qはpの倍数全てを走る
    if q in A:
      ct += 1
  
  # ct = Nのとき、pはすべてのA_nの約数。つまり、Aはnot coprime
  if ct == N:
    print("not coprime")
    sys.exit()
  
  # 2 <= ct < Nのとき、pは2つ以上のA_nの約数。つまり、Aはpairwise coprimeではない。
  # setwise coprimeか、not coprimeかを判定するため、次のpを調べる必要あり。 
  elif ct >= 2:
    not_pairwise_coprime = True
  
  # ct <= 1のとき、pはどの２つのA_nの公約数にも一致しない。次のpを調べる必要あり。
  #else: continue
  
  
# ループが途中で終わるのは、not coprimeの場合であり、その場合に限る。
# したがって、この時点で可能性があるのは、setwise coprimeかpairwise coprimeのどちらか。
print("setwise coprime" if not_pairwise_coprime else "pairwise coprime")

Submission status: Accepted

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)

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

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

    return set(arr)

import math
N=int(input())
A=list(map(int,input().split()))
ans=['pairwise coprime','setwise coprime','not coprime']
k=0
s=factorization(A[0])
for a in A[1:]:
    tmp=factorization(a)-{1}
    if s&tmp==set():
        s|=tmp
    else:
        k=-1
        break
if k==-1:
    g=A[0]
    for a in A[1:]:
        g=math.gcd(g,a)
    if g==1:
        k=1
    else:
        k=2
print(ans[k])

Submission status: Accepted

Solution code:
n = raw_input()
def gcd(a,b):
	if b == 0:
		return a
	return gcd(b,a%b)

def g(ais): return reduce(gcd, ais) == 1

def f(ais):
	seen = set()
	for ai in ais:
		factor =2
		oi = ai
		while(ai != 1 and factor * factor <= oi):
			if ai % factor == 0:
				if factor in seen:
					return False
				while(ai % factor == 0):
					ai /= factor
				seen.add(factor)
			factor +=1
		if ai != 1:
			if ai in seen: return False
			seen.add(ai) 
	return True

ais = map(int, raw_input().split())

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

Submission status: Accepted

Solution code:
from math import gcd
n = int(input())
a = [int(i) for i in input().split()]

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

m = max(a)
fac = [1]*(m+1)
for i in range(2,m+1):
    if fac[i] != 1: continue
    for j in range(i,m+1,i): fac[j] = i
s = set()
for i in range(n):
    x = fac[a[i]]
    if x == 1: continue
    if x in s:
        print("setwise coprime")
        exit()
    s.add(x)
print("pairwise coprime")

Submission status: Accepted

Solution code:
import sys
from math import gcd

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 19
MOD = 10 ** 9 + 7
EPS = 10 ** -10

def factorize(num: int) -> dict:
    """ 素因数分解 """
    from math import sqrt
    from collections import Counter

    d = Counter()
    for i in range(2, int(sqrt(num))+1):
        while num % i == 0:
            num //= i
            d[i] += 1
        if num == 1:
            break
    if num != 1:
        d[num] += 1
    return d

N = INT()
A = LIST()

def check(se, fact):
    for k in fact:
        if k not in se:
            se.add(k)
        else:
            return False
    return True

is_pc = 1
se = set()
for a in A:
    fact = factorize(a)
    if not check(se, fact):
        is_pc = 0
        break

is_sc = 1
g = 0
for a in A:
    g = gcd(g, a)
if g != 1:
    is_sc = 0

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

Submission status: Accepted

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

#pairwiseかどうかを調べる
memo = [1]*(10**6+1)
memo[0] = 0
memo[1] = 0
for i in range(2,10**6+1):
    if memo[i] == 1:
        flag = False
        if i in countA:
            if countA[i] >= 2:
                break
            flag = True
        for j in range(i*2,10**6+1,i):
            if j in countA:
                if countA[j] >= 2:
                    break
                if flag:
                    break
                else:
                    flag = True
            memo[j] = 0
        else:
            continue
        break
else:
    print("pairwise coprime")
    exit()



#setwise coprimeを判断
def gcd(a,b):
    return a if b==0 else gcd(b,a%b)

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

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
def gcd(a,b):
    if b == 0:
        return a
    else:
        return gcd(b,a%b)

n = int(input())
a_list = list(map(int, input().split()))
a_list.sort()
ans2 = a_list[0]
for i in range(1, n):
    ans2 = gcd(ans2, a_list[i])
    if ans2 == 1:
        break

if ans2 != 1:
    print("not coprime")
else:
    flag = 1
    max_a = a_list[n - 1] + 1
    num_flag_list = [True] * max_a
    d_list = list(range(0, max_a))
    d_list[0] = 1
    num_flag_list[0] = num_flag_list[1] = False
    for i in range(2, int(max_a**0.5) + 1):
        if num_flag_list[i]:
            for j in range(i**2, max_a, i):
                if num_flag_list[j] == True:
                    num_flag_list[j] = False
                    d_list[j] = i
    p_set = set()
    for a in a_list:
        if a == 1:
            continue
        temp_p_set = set()
        while True:
            p = d_list[a]
            if p not in temp_p_set:
                if p in p_set:
                    flag = 0
                    break
            temp_p_set.add(p)
            p_set.add(p)
            a = a // p
            if a == 1:
                break
        if flag == 0:
            break
        
    if flag == 1:
        print("pairwise coprime")
    else:
        print("setwise coprime")

Submission status: Accepted

Solution code:
import math

class SieveOfEratosthenes:
    def __init__(self, V):
        self.is_prime = [True] * (V + 1)
        self.primes = []
        for i in range(2, V + 1):
            if self.is_prime[i]:
                self.primes.append(i)
                for j in range(i * i, V + 1, i):
                    self.is_prime[j] = False
    
    def factorize(self, x):
        assert x > 1
        result = []
        for p in self.primes:
            exp = 0
            while x % p == 0:
                exp += 1
                x = x // p
            if exp > 0:
                result.append((p, exp))
            if p * p > x:
                break
        if x > 1:
            result.append((x, 1))
        return result


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

    if all(a == 1 for a in A):
        return 'pairwise coprime'

    gcd_all = 0
    for a in A:
        gcd_all = math.gcd(gcd_all, a)

    if gcd_all > 1:
        return 'not coprime'
    
    sieve = SieveOfEratosthenes(max(A))
    used_primes = set()
    for a in A:
        if a != 1:
            factors = sieve.factorize(a)
            for (p, e) in factors:
                if p in used_primes:
                    return 'setwise coprime'
                used_primes.add(p)
    
    return 'pairwise coprime'

print(solve())

Submission status: Accepted

Solution code:
import math
import numpy as np

class SieveOfEratosthenes:
    def __init__(self, V):
        self.is_prime = np.ones(V + 1, dtype=bool)
        self.is_prime[4::2] = False
        self.is_prime[9::3] = False
        self.is_prime[25::5] = False
        self.primes = [2, 3, 5]
        for i in range(7, V + 1, 2):
            if self.is_prime[i]:
                self.primes.append(i)
                self.is_prime[i * i::i] = False
    
    def factorize(self, x):
        assert x >= 1
        if x == 1:
            return [(1, 1)]
        result = []
        for p in self.primes:
            exp = 0
            while x % p == 0:
                exp += 1
                x = x // p
            if exp > 0:
                result.append((p, exp))
            if p * p > x:
                break
        if x > 1:
            result.append((x, 1))
        return result


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

    if all(a == 1 for a in A):
        return 'pairwise coprime'

    gcd_all = 0
    for a in A:
        gcd_all = math.gcd(gcd_all, a)

    if gcd_all > 1:
        return 'not coprime'
    
    sieve = SieveOfEratosthenes(max(A))
    used_primes = set()
    for a in A:
        if a != 1:
            factors = sieve.factorize(a)
            for (p, e) in factors:
                if p in used_primes:
                    return 'setwise coprime'
                used_primes.add(p)
    
    return 'pairwise coprime'

print(solve())

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 math import gcd
from functools import reduce
def resolve():
    n = int(input())
    A = list(map(int, input().split()))

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

    M = max(A)
    dist = [0] * (M + 1)
    for a in A:
        dist[a] += 1

    sieve = [True] * (M + 1)
    for p in range(2, M + 1):
        if not sieve[p]:
            continue
        c = 0
        for i in range(p, M + 1, p):
            c += dist[i]
            sieve[i] = False
        if c >= 2:
            print("setwise coprime")
            return

    print("pairwise coprime")
resolve()

Submission status: Accepted

Solution code:
n = int(input())
*a,=map(int, input().split())
mapa=[0]*(10**6+1)

n0 = 10**6
primes = [0]*(n0+1)
for i in range(2, n0+1):
    if primes[i]==0:
        x=i
        multi=1
        while x<=n0:
            if primes[x]==0:
                primes[x]=i
            x//=multi
            multi+=1
            x*=multi

def func(m):
    while m>1:
        mapa[primes[m]]+=1
        pm=primes[m]
        while m>1 and m%pm==0:
            m//=pm

for ai in a:
    func(ai)

tmp=max(mapa)

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

Submission status: Accepted

Solution code:
import sys
import math
import fractions
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 not input_list[serial]:
            continue

        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)
    ela2 = [i for i, b in enumerate(ela) if b]

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

    g = A[0]
    for a in A:
        g = math.gcd(g, a)
    if g > 1:
        print("not coprime")
        exit()

    SA = set(A)
    SA.discard(1)
    if len(SA) >= 90000:
        print("setwise coprime")
        exit()

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

        if PD_list[a]:
            AP = PD_list[a]
        else:
            AP = prime_fact(a, ela2)
            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: Accepted

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):
    global dt
    if num&1 == 0:
        num >>= 1
        if dt[2]:
            dt[2] = 0
        else:
            return 'setwise coprime'
    while num&1 == 0:
        num >>= 1
    for i in range(3,int(sqrt(num))+1,2):
        if num%i == 0:
            num //= i
            if dt[i]:
                dt[i] = 0
            else:
                return 'setwise coprime'
        while num%i == 0:
            num //= i
    if num>2:
        if dt[num]:
            dt[num] = 0
        else:
            return 'setwise coprime'
    return 'pairwise coprime'

n = inp()
x = ip()
x.sort(reverse=True)
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:
        if pfact(i) == 'setwise coprime':
            ans = 'setwise coprime'
            break
print(ans)