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
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり


N = I()
A = LI()

from math import gcd

g = 0  # Aiたちの最大公約数
for i in range(N):
    g = gcd(g,A[i])

if g != 1:
    print('not coprime')
    exit()

B = []
for i in range(N):
    if A[i] != 1:
        B.append(A[i])
N = len(B)
# 以下、このB,Nで考えれば良い

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

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

if N > 78498:  # 78498は10**6以下の素数の個数
    print('setwise coprime')
    exit()

C = [0]*(10**6+1)  # C[i] = 1 ⇔ Bの元に素因数iを持つものが存在する

for i in range(N):
    b = B[i]
    for p in primes:
        if b % p == 0:
            if C[p] == 1:
                print('setwise coprime')
                exit()
            else:
                C[p] = 1
            while b % p == 0:
                b //= p
    if b != 1:
        if C[b] == 1:
            print('setwise coprime')
            exit()
        else:
            C[b] = 1

print('pairwise coprime')

# 計算量 O(min(N,A/logA)*√A/logA) ?

Submission status: Accepted

Solution code:
import math

def primelis(n):
    a = []
    if n % 2 == 0:
        a.append(2)
        while n%2==0:
          n=n//2
    f = 3
    while f * f <= n:
      if n%f==0:
        a.append(f)
        while n%f==0:
          n=n//f
    if n != 1:
        a.append(n)
    return a



n=int(input())

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

gcd=A[0]

for i in range(n-1):
  gcd=math.gcd(gcd,A[i+1])

d=[0 for i in range(10**6+1)]

for i in range(2,10**6+1):
  if d[i]==0:
    j=1
    while i*j<=10**6:
      d[i*j]=i
      j+=1

nglis=[0 for i in range(10**6+1)]

if gcd!=1:
  print("not coprime")
else:
  check=0
  for i in range(n):
    if nglis[A[i]]==1:
      check=1
      break
    else:
      ai=A[i]
      while ai!=1:
        j=1
        while d[ai]*j<=10**6:
          nglis[d[ai]*j]=1
          j+=1
        ai=ai//d[ai]
  if check==1:
    print("setwise coprime")
  else:
    print("pairwise coprime")

Submission status: Accepted

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

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

def sieve_optimized(limit):
    # Preprocessing step takes O(N log log N) time complexity.
    n = limit
    # Filimitd all primes upto n  (including n)
    sievebound = (n-1)//2
    sieve = [-1]*(sievebound + 1)
    # sieve[0] = True
    crosslimit = (int(sievebound**0.5) - 1)
    for i in range(1, crosslimit + 1):
        if sieve[i] == -1:
            for j in range(2*i*(i+1), sievebound + 1, 2*i+1):
                sieve[j] = 2*i + 1
    return sieve

def factorization(n, sieve):
    # Factorisaton query takes O(log N) time after preprocessing.
    divs = [1]
    while n!=1:
        if n&1:
            div = sieve[(n-1)//2]
            if div == -1:
                divs.append(n)
                break
            else:
                n //= div
                divs.append(div)
        else:
            n >>= 1
            divs.append(2)

    return divs

maxnum = 10**6 + 1
sieve = sieve_optimized(maxnum)

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

seen = dict()
maxval = 0
for i in nums:
    factors = factorization(i, sieve)
    if len(factors) <= 1: continue
    for f in set(factors[1:]):
        if f in seen:
            seen[f] += 1
            maxval = max(maxval, seen[f])
        else:
            seen[f] = 1


if maxval == n:
    print('not coprime')

elif 1 < maxval < n:
    print('setwise coprime')

else:
    print('pairwise 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()

# https://qiita.com/Kiri8128/items/eca965fe86ea5f4cbb98
def isPrimeMR(n):
    d = n - 1
    d = d // (d & -d)
    L = [2]
    for a in L:
        t = d
        y = pow(a, t, n)
        if y == 1: continue
        while y != n - 1:
            y = (y * y) % n
            if y == 1 or t == n - 1: return 0
            t <<= 1
    return 1
def findFactorRho(n):
    m = 1 << n.bit_length() // 8
    for c in range(1, 99):
        f = lambda x: (x * x + c) % n
        y, r, q, g = 2, 1, 1, 1
        while g == 1:
            x = y
            for i in range(r):
                y = f(y)
            k = 0
            while k < r and g == 1:
                ys = y
                for i in range(min(m, r - k)):
                    y = f(y)
                    q = q * abs(x - y) % n
                g = gcd(q, n)
                k += m
            r <<= 1
        if g == n:
            g = 1
            while g == 1:
                ys = f(ys)
                g = gcd(abs(x - ys), n)
        if g < n:
            if isPrimeMR(g): return g
            elif isPrimeMR(n // g): return n // g
            return findFactorRho(g)
def primeFactor(n):
    i = 2
    ret = {}
    rhoFlg = 0
    while i*i <= n:
        k = 0
        while n % i == 0:
            n //= i
            k += 1
        if k: ret[i] = k
        i += 1 + i % 2
        if i == 101 and n >= 2 ** 20:
            while n > 1:
                if isPrimeMR(n):
                    ret[n], n = 1, 1
                else:
                    rhoFlg = 1
                    j = findFactorRho(n)
                    k = 0
                    while n % j == 0:
                        n //= j
                        k += 1
                    ret[j] = k

    if n > 1: ret[n] = 1
    if rhoFlg: ret = {x: ret[x] for x in sorted(ret)}
    return ret

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

    used = set()
    for a in A:
        for p in primeFactor(a):
            if p in used:
                print("setwise coprime")
                return
            used.add(p)

    print("pairwise coprime")
resolve()

Submission status: Accepted

Solution code:
from functools import reduce
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)

def solve():
    maxA = 10**6

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

    def getMinPFs(n):
        isPrimes = [False]*2 + [True]*(n-1)
        minPFs = [1] + list(range(1, n+1))
        for d in range(2, int(n**0.5)+1):
            if isPrimes[d]:
                minPFs[d] = d
                for x in range(d*d, n+1, d):
                    isPrimes[x] = False
                    if minPFs[x] == x:
                        minPFs[x] = d
        return minPFs

    def getPrimeFactors(x, minPFs):
        anss = set()
        while minPFs[x] > 1:
            anss.add(minPFs[x])
            x //= minPFs[x]
        return anss

    minPFs = getMinPFs(maxA)

    useds = [0] * (maxA+1)
    for A in As:
        PFs = getPrimeFactors(A, minPFs)
        for PF in PFs:
            if useds[PF]:
                break
            useds[PF] = 1
        else:
            continue
        break
    else:
        print('pairwise coprime')
        return

    def gcd(a, b):
        while b:
            a, b = b, a%b
        return a

    g = reduce(gcd, As)

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


solve()

Submission status: Accepted

Solution code:
import sys, math

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 == [] and n != 1:
        arr.append([n, 1])

    return arr

N = int(input())
A = list(map(int, sys.stdin.readline().rsplit()))

ok = True
S = set()
for a in A:
    arr = factorization(a)
    # print(arr)
    for b, _ in arr:
        if b in S:
            ok = False
            break
        else:
            S.add(b)
    if ok is False:
        break
if ok:
    print("pairwise coprime")
else:
    tmp = A[0]
    for a in A[1:]:
        tmp = math.gcd(a, tmp)
    if tmp != 1:
        print("not coprime")
    else:
        print("setwise coprime")

Submission status: Accepted

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

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)

max_a=max(alist)  
dlist=[i for i in range(max_a+1)]
for i in range(2,int(max_a**0.5)+1):
  if dlist[i]<i:
    continue
  else:
    for j in range(i**2,max_a+1,i):
      dlist[j]=i  
#print(dlist)

fact_set=set()
for i in range(N):
  ai=alist[i]
  facts=set()
  while ai>1:
    facts.add(dlist[ai])
    ai//=dlist[ai]    
  #print(facts)
  
  for f in facts:
    if f in fact_set:
      print("setwise coprime")
      sys.exit(0)
    else:
      fact_set.add(f)
else:
  print("pairwise coprime")

Submission status: Accepted

Solution code:
N = int(input())
M = 10**6 + 1

counts = [0 for _ in range(M)]
for a in map(int, input().split()):
  counts[a] += 1

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

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

print(answer)

Submission status: Accepted

Solution code:
N = int(input())
M = 10**6 + 1

counts = [0 for _ in range(M)]
for a in list(map(int, input().split())):
  counts[a] += 1

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

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

print(answer)

Submission status: Accepted

Solution code:
import os
import heapq
import sys,threading
import math
import operator
from collections import defaultdict,deque
from io import BytesIO, IOBase
import math as mt
sys.setrecursionlimit(10 ** 5)
threading.stack_size(2**27)


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


"""def pw(a,b):
    result=1
    while(b>0):
        if(b%2==1): result*=a
        a*=a
        b//=2
    return result"""


def inpt():
    return [int(k) for k in input().split()]

def main():
    MAXN=1000001
    prime=[0]*MAXN
    prime[1] = 1
    for i in range(2, MAXN):
        prime[i] = i

    for i in range(4, MAXN, 2):
        prime[i] = 2

    for i in range(3, mt.ceil(mt.sqrt(MAXN))):
        if (prime[i] == i):
            for j in range(i * i, MAXN, i):
                if (prime[j] == j):
                    prime[j] = i
    n=int(input())
    ar=inpt()
    d=defaultdict(int)
    ok=True
    for i in range(n):
        x=ar[i]
        while(x!=1):
            tp=prime[x]
            x=x//prime[x]
            if(tp in d and d[tp]!=(ar[i],i)):
                ok=False
                break
            d[tp]=(ar[i],i)

    if(ok):
        print('pairwise coprime')
    else:
        gcd=ar[0]
        for i in range(1,n):
            gcd=mt.gcd(gcd,ar[i])

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




BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

if __name__ == "__main__":
    #main()
    threading.Thread(target=main).start()

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
M = 10**6 + 1

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

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

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

print(answer)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
M = 10**6 + 1

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

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

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

print(answer)

Submission status: Accepted

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

g = 0
for a in A:
    g = gcd(g,a)
if g > 1:
    print('not coprime')
    exit()

sa = set()
for a in A:
    if a==1: continue
    if a in sa:
        print('setwise coprime')
        exit()
    sa.add(a)

MAXN = 10**6+10
sieve = [0,0] + [1]*MAXN
p = 2
small_primes = []
while p*p <= MAXN:
    if sieve[p]:
        small_primes.append(p)
        for q in range(2*p,MAXN+1,p):
            sieve[q] = 0
    p += 1

st = set()
for a in A:
    for p in small_primes:
        found = False
        while a%p==0:
            a //= p
            found = True
        if found:
            if p in st:
                print('setwise coprime')
                exit()
            st.add(p)
        if a==1: break
    else:
        if a in st:
            print('setwise coprime')
            exit()
        st.add(a)

print('pairwise coprime')

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7) #再帰関数の上限,10**5以上の場合python
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque, defaultdict
#deque(l), pop(), append(x), popleft(), appendleft(x)
#q.rotate(n)で → にn回ローテート
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate,combinations,permutations,product#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
from functools import reduce,lru_cache#pypyでもうごく
#@lru_cache(maxsize = None)#maxsizeは保存するデータ数の最大値、2**nが最も高効率
from decimal import Decimal
from argparse import ArgumentParser

args=ArgumentParser()
args.add_argument('-loc', '--local', type=bool,default=False)
LOCAL=args.parse_args().local

def input(): 
    x=sys.stdin.readline(); 
    if x[-1]=="\n": 
        return x.rstrip() 
    return x
    
def printe(*x):_=print("## ",*x,file=sys.stderr) if LOCAL else 0
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def binr(x): return bin(x)[2:]
def bitcount(x): #xは64bit整数
    x= x - ((x >> 1) & 0x5555555555555555)
    x= (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x= (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f 
    x+= (x >> 8); x+= (x >> 16); x+= (x >> 32) 
    return x & 0x7f

def main():
    mod = 1000000007
    #w.sort(key=itemgetter(1),reverse=True)  #二個目の要素で降順並び替え

    N = int(input())
    #N, K = map(int, input().split())
    A = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列
    tot=0
    def primes(n):
        a = set()
        while n % 2 == 0:
            a.add(2)
            n //= 2
        f = 3
        while f * f <= n:
            if n % f == 0:
                a.add(f)
                n //= f
            else:
                f += 2
        if n != 1:
            a.add(n)
        return a

    for a in A:
        tot=math.gcd(tot,a)
    if tot!=1:
        print("not coprime")
        return
    # tN=N
    # for a in A:
    #     if a==1:
    #         tN-=1

    # if tN>78498:
    #     print("setwise coprime")
    #     return 

    cur=set()
    for a in A:
        s=primes(a)
        if len(s&cur)!=0:
            print("setwise coprime")
            return 
        cur|=s

    print("pairwise coprime")


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
#A = [888881 for i in range(10**6)]
M = max(A)


#高速素因数分解
#前処理：その数にある最小の素因数→エラトステネスの篩で最初におとすもの
P = [1 for i in range(M+1)]
for i in range(2, M+1):
    if P[i] == 1:
        for j in range(i, M+1, i):
            if P[j] == 1:
                P[j] = i
dic = {}
for a in A:
  t_dic = {}
  x = a
  while x > 1:
    if P[x] in t_dic:
      t_dic[ P[x] ] += 1
    else:
      t_dic[ P[x] ] = 1    
    x //= P[x]
  for k in t_dic.keys():
    if k in dic:
      dic[k] += 1
    else:
      dic[k] = 1
#print(dic)
c = 0
for v in dic.values():
  c = max(c, v)

if c == len(A):
  print("not coprime")
elif c < 2:
  print("pairwise coprime")
else:
  print("setwise coprime")

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
M = max(A) + 1

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

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

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

print(answer)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys
from math import gcd
from collections import Counter
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

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

dup = False
dup_key = None
counter = Counter(A)
for key, val in counter.items():
    if val > 1:
        dup = True
        if dup_key is None:
            dup_key = key
        else:
            dup_key = max(dup_key, key)


def max_gcd_pair(S):
    # Assumption 1: S is the list of numbers
    # Assumption 2: There are no duplicates in S
    s = set(S)
    m = max(S)
    res = 1
    i = m
    while i > 0:
        a = i
        cnt = 0
        while a <= m: # a maxed at max of the list
            if a in s:
                cnt += 1
            a += i
        if cnt >= 2:  # we have found the result
            res = i
            break
        i = i - 1
    return res


pair = max_gcd_pair(A)
if dup:
    pair *= dup_key

if pair == 1:
    print('pairwise coprime')
    sys.exit()


setw = A[0]
for j in range(N):
    setw = gcd(setw, A[j])
if setw == 1:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Accepted

Solution code:
import math
import collections
def main():

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

    d = dict()
    def prime_factor(n):
        if n % 2 == 0: d[2] = d.get(2, 0) + 1
        while n % 2 == 0:
            n //= 2

        i = 3
        while i * i <= n:
            if n % i == 0:
                d[i] = d.get(i, 0) + 1
            while n % i == 0:
                n //= i
            i += 2
        if n > 1:
            d[n] = d.get(n, 0) + 1
        return

    ispair = True
    isset = True

    d = dict()
    for v in A: prime_factor(v)
    # print(d)

    if any(d[p] > 1 for p in d):
        ispair = False
    if any(d[p] == N for p in d):
        isset = False

    if ispair:
        return "pairwise coprime"
    if isset:
        return "setwise coprime"

    return "not coprime"

if __name__ == '__main__':
    print(main())

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
M = 10**6 + 1

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

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

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

print(answer)

Submission status: 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, cnt])

    if temp!=1:
        arr.append([temp, 1])

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

    return arr
    
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a 
def multiple_gcd(a):
    ans = a[0]
    for i in range(1, len(a)):
        ans = gcd(ans, a[i])
    return ans

def pairwise_coprime_gcd():
    for i in range(N-1):
        for j in range(i+1, N):
            if gcd(A[i], A[j]) != 1:
                return 0
    return 1
def pairwise_coprime(A):
    prime = set()
    for i in range(N):
        fact = factorization(A[i])
        for x in fact:
            if x[0] in prime:
                return 0
            if x[0] != 1:
                prime.add(x[0])
    return 1

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

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

Submission status: Accepted

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

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

if g!=1:
    print('not coprime')
    exit()

f = True
l = set()
for i in a:
    for j in range(2,int(i**0.5)+1):
        if i%j==0:
            if i in l:
                f = False
                break
            l.add(i)
        while i%j==0:
            i = i//j
        if i<2:
            break
    if i>1:
        if i in l:
            f = False
            break
        l.add(i)
        
if f:
    print('pairwise coprime')
else:
    print('setwise coprime')

Submission status: Accepted

Solution code:
from math import gcd
from functools import reduce
N = int(input())
*A, = map(int, input().split())

MAX_N = max(A)+5
primes = list(range(MAX_N+1))
for i in range(2, int(MAX_N**0.5)+1):
    if primes[i] < i:
        continue
    for j in range(2*i, MAX_N+1, i):
        primes[j] = i


def check():
    S = set()
    for a in A:
        T = set()
        while True:
            p = primes[a]
            if p != 1 and p in S:
                return False
            T.add(p)
            if p == a:
                break
            a //= p
        S |= T
    return True


if check() or all(a == 1 for a in A):
    print('pairwise coprime')
elif reduce(gcd, A) == 1:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Accepted

Solution code:
from math import gcd
from functools import reduce

def make_prime_table(n):
    sieve = list(range(n + 1))
    sieve[0] = -1
    sieve[1] = -1
    for i in range(4, n + 1, 2):
        sieve[i] = 2
    for i in range(3, int(n ** 0.5) + 1, 2):
        if sieve[i] != i:
            continue
        for j in range(i * i, n + 1, i * 2):
            if sieve[j] == j:
                sieve[j] = i
    return sieve


def prime_factorize(n):#1を除く(素因数,指数)のリスト
    result = []
    while n != 1:
        p = prime_table[n]
        e = 0
        while n % p == 0:
            n //= p
            e += 1
        result.append((p, e)) 
    return result


def f():
    s = set()
    for i in range(N):
        t = prime_factorize(A[i])
        for p, _ in t:
            if p in s:
                return False
            s.add(p)
    return True


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

prime_table = make_prime_table(10 ** 6)
if f():
    print('pairwise coprime')
elif reduce(gcd, A) == 1:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Accepted

Solution code:
from math import gcd


def eratosthenes(n):
    prime = []
    data = [i for i in range(2, n + 1)]
    while True:
        p = data[0]
        if n <= p ** 2:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]
    return data


def factorize(N):  # 素因数分解
    prime = set()
    for p in prime_list:
        if p * p > N:
            break
        while N % p == 0:
            N //= p
            prime.add(p)
    if N > 1:
        prime.add(N)
    return prime


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

ans = 0
for ai in a:
    ans = gcd(ans, ai)
if ans != 1:
    print('not coprime')
    exit()

prime_list = eratosthenes(10 ** 6)
num = set()
for ai in a:
    prime = factorize(ai)
    if len(prime & num) > 0:
        print('setwise coprime')
        break
    num |= prime
else:
    print('pairwise coprime')

Submission status: Accepted

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

PRIME_LENGTH = (10**6 + 1)

prime_list = [[] for _ in range(PRIME_LENGTH)]

for i in range(2, PRIME_LENGTH):
    if not prime_list[i]:
        idx = i
        while (idx < PRIME_LENGTH):
            prime_list[idx].append(i)
            idx += i

vote = [0] * (PRIME_LENGTH)

for a in A:
    for v in prime_list[a]:
        vote[v] += 1

if max(vote) == len(A):
    print("not coprime")
elif sum(map(lambda x: x > 1, vote)) > 0:
    print("setwise coprime")
else:
    print("pairwise coprime")

Submission status: Accepted

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


def gcd(x, y):
    while y != 0:
        x, y = y, x % y
    return x


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==[]:  # n=1のとき、[1,1]を返す
    #     arr.append([n, 1])

    return arr


# factorization(24)
## [[2, 3], [3, 1]]
##  24 = 2^3 * 3^1

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

# print(gcdall)
if gcdall > 1:
    print("not coprime")
    exit()

MAX = 10 ** 6 + 1
num = [False] * MAX
A = sorted(A)[::-1]
primeset = set()
for a in A:
    if a == 1:
        continue
    if num[a]:
        print("setwise coprime")
        exit()
    fact = factorization(a)
    for p, nn in fact:
        if p == 1:
            continue
        if p in primeset:
            continue
        primeset.add(p)
        for j in range(p, MAX, p):
            num[j] = True

print("pairwise coprime")