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:
def main():
    from math import gcd
    from functools import reduce, lru_cache

    n, *a, = map(int, open(0).read().split())
    m = max(a)

    d = [0] * (m + 1)
    d[1] = 1
    for i in range(2, m + 1):
        for j in range(i, m + 1, i):
            if d[j] == 0:
                d[j] = i

    @lru_cache()
    def primes(x):
        ps = set()
        while x != 1:
            p = d[x]
            ps.add(p)
            x = x // d[x]
        return ps

    b = set()
    f = 0
    g = a[0]
    for i in range(n):
        x = a[i]
        ps = primes(x)
        g = gcd(g, x)
        if b & ps:
            f = 1
            break
        b |= ps
    if f > 0 and gcd(g, reduce(gcd, a[i:])) != 1:
        f = 2

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


if __name__ == '__main__':
    main()

Submission status: Accepted

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

A=max(a)

def min_factor(k):
    d=[]
    for i in range(k+1):
        d.append(i)

    i=2
    while i*i<=k:
        if d[i]==i:
            j=i*i
            while j<=k:
                if d[j]==j:
                    d[j]=i
                j+=i
        i+=1
    
    return d

def prime_factor_set(p):
    s=set()
    while p!=1:
        s.add(d[p])
        p//=d[p]  
    
    return s


d=min_factor(A)
cur=set()
flg=True
for i in range(n):
    tmp = prime_factor_set(a[i])
    if len(cur&tmp)>=1:
        flg=False
        break
    cur |= tmp

import numpy as np

g= np.gcd.reduce(a)

if flg:
    ans='pairwise coprime'
elif not flg and g==1:
    ans='setwise coprime'
else:
    ans='not coprime'

print(ans)

Submission status: Accepted

Solution code:
def main():
    from math import gcd
    from functools import reduce
    n, *a, = map(int, open(0).read().split())
    m = max(a)

    d = [0] * (m + 1)
    d[1] = 1
    for i in range(2, m + 1):
        for j in range(i, m + 1, i):
            if d[j] == 0:
                d[j] = i

    def primes(x):
        ps = set()
        while x != 1:
            p = d[x]
            ps.add(p)
            x = x // d[x]
        return ps

    b = set()
    f = 0
    for i in a:
        ps = primes(i)
        if b & ps:
            f = 1
            break
        b |= ps
    if f > 0 and reduce(gcd, a) != 1:
        f = 2

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import math


N_MAX = 200000 + 5
INF = 10**9 + 7
sys.setrecursionlimit(N_MAX)
MOD = 10**9 + 7


def eatosthenes(N):
    prime = []
    D = [1] * (N + 1)

    for i in range(2, N + 1):
        if D[i] != 1:
            continue
        for j in range(N // i + 1):
            if D[i * j] == 1:
                D[i * j] = i
        prime.append(i)

    return prime


def main():
    N = int(sys.stdin.readline().rstrip())
    A = [int(x) for x in sys.stdin.readline().rstrip().split()]

    maxA = max(A)
    primelist = eatosthenes(maxA)

    # 1 <= a <= maxA までの、要素の登場回数
    C = [0] * (maxA + 1)
    for a in A:
        C[a] += 1

    pc = True

    # p の倍数である個数をカウントする
    for p in primelist:
        cnt = 0
        for k in range(maxA // p + 1):
            cnt += C[k * p]

        # k*p となるような要素が2個以上あったら、pairwise coprime ではない
        if cnt > 1:
            pc = False

    if pc:
        print("pairwise coprime")
        return

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

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

    print("not coprime")


main()

Submission status: Accepted

Solution code:
import numpy as np
import numba
from numba import njit, b1, i4, i8, f8

@njit((i8,i8[:]), cache=True)
def main(N,A):
  Amax = A.max()
  lis = np.zeros(Amax+1, np.int64)
  table = np.full(Amax+1,Amax+1,np.int64)
  for i in range(2, Amax+1):
    table[i::i] = np.minimum(table[i::i],i)
  for i in range(N):
    p = A[i]
    while p>1:
      q = table[p]
      lis[q]+=1
      while p%q==0:
        p //= q
  setwise = False
  for i in range(Amax+1):
    if lis[i]==N:
      return 'not'
    if 2<=lis[i]<N:
      setwise=True
  if setwise==True:
    return 'setwise'
  return 'pairwise'

N = int(input())
A = np.array(list(map(int, input().split())))
print(main(N,A)+' coprime')

Submission status: Accepted

Solution code:
from sys import stdin, setrecursionlimit
from collections import Counter, deque, defaultdict
from math import floor, ceil, gcd
from bisect import bisect_left
import random
from itertools import combinations, accumulate
setrecursionlimit(100000)

INF = int(1e10)
MOD = int(1e9 + 7)

class PrimeTool(object):
    def __init__(self, n):
        self.n = n
        self.primes = []
        self.sieves = []

    def generate_primes(self):
        if len(self.primes) == 0 and len(self.sieves) == 0:
            is_prime = [True] * (self.n + 1)
            is_prime[0] = is_prime[1] = False
            self.sieves = [k for k in range(self.n + 1)]
            self.sieves[0] = 1
            for p in range(2, self.n + 1):
                if is_prime[p]:
                    self.primes.append(p)
                    for i in range(p, self.n + 1, p):
                        is_prime[i] = False
                        self.sieves[i] = p
            return self.primes

    def factorization(self, n):
        arr = []
        temp = n
        for i in range(2, int(-(-n**0.5//1))+1):
            if temp % i == 0:
                c = 0
                while temp % i==0:
                    c += 1
                    temp //= i
                arr.append((i, c))
        if temp != 1:
            arr.append((temp, 1))
        return arr

    def fast_factorization(self, num):
        # 1度計算だけ
        self.generate_primes()

        # 試し割りなしのfact
        arr = []
        temp = num
        while temp != 1:
            i = self.sieves[temp]
            c = 0
            while temp % i==0:
                c += 1
                temp //= i
            arr.append((i, c))
        if temp != 1:
            arr.append((temp, 1))
        return arr

def solve(N, A):
    tool = PrimeTool(max(A) + 1)
    primes = tool.generate_primes()
    ct = Counter()

    pair_wise = True
    for i, Ai in enumerate(A):
        arr = tool.fast_factorization(Ai)
        for p, _ in arr:
            ct[p] += 1
            if ct[p] > 1:
                pair_wise = False
                break
        if not pair_wise:
            break

    # 共通gcd
    prod = A[0]
    for k in range(1, N):
        prod = gcd(prod, A[k])
    
    if pair_wise:
        print("pairwise coprime")
    elif prod == 1:
        print("setwise coprime")
    else:
        print("not coprime")

def main():
    from builtins import int, map
    N = int(input())
    A = list(map(int, input().split()))
    solve(N, A)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
class Prime():
    def __init__(self, n):
        self.p = []
        self.d = [0] * n

        for i in range(2, n):
            if self.d[i] == 0:
                self.p.append(i)
                for j in range(i, n, i):
                    if self.d[j] == 0:
                        self.d[j] = i

        self.ind = [-1] * n
        for i in range(len(self.p)):
            self.ind[self.p[i]] = i

    def prime_factorization_index(self, x):
        l = []
        while x != 1:
            if l == [] or l[-1] != self.ind[self.d[x]]:
                l.append(self.ind[self.d[x]])
            x //= self.d[x]
        return l

    def num_prime(self):
        return len(self.p)

def main():

    from math import gcd
 
    n = int(input())
    a = list(map(int, input().split()))
 
    g = a[0]
    for i in range(1, n):
        g = gcd(g, a[i])
        if g == 1:
            break
    else:
        print('not coprime')
        exit()

    p = Prime(10**6 + 1)

    tf = [False] * p.num_prime()

    for i in range(1, n):
        l = p.prime_factorization_index(a[i])
        for i in l:
            if tf[i]:
                print('setwise coprime')
                exit()
            else:
                tf[i] = True

    print('pairwise coprime')

main()

Submission status: Accepted

Solution code:
import sys
import math


N_MAX = 200000 + 5
INF = 10**9 + 7
sys.setrecursionlimit(N_MAX)
MOD = 10**9 + 7


def main():
    N = int(sys.stdin.readline().rstrip())
    A = [int(x) for x in sys.stdin.readline().rstrip().split()]

    maxA = max(A)

    # 1 <= a <= maxA までの、要素の登場回数
    C = [0] * (maxA + 1)
    for a in A:
        C[a] += 1

    pc = True

    # p の倍数である個数をカウントする
    for p in range(2, maxA + 1):
        cnt = 0
        for k in range(maxA // p + 1):
            cnt += C[k * p]

        # k*p となるような要素が2個以上あったら、pairwise coprime ではない
        if cnt > 1:
            pc = False

    if pc:
        print("pairwise coprime")
        return

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

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

    print("not coprime")


main()

Submission status: Accepted

Solution code:
class Prime():
    def __init__(self, n):
        self.p = []
        self.d = [0] * n

        for i in range(2, n):
            if self.d[i] == 0:
                self.p.append(i)
                for j in range(i, n, i):
                    if self.d[j] == 0:
                        self.d[j] = i

        self.ind = [-1] * n
        for i in range(len(self.p)):
            self.ind[self.p[i]] = i

    def prime_factorization_index(self, x):
        l = []
        while x != 1:
            if l == [] or l[-1] != self.ind[self.d[x]]:
                l.append(self.ind[self.d[x]])
            x //= self.d[x]
        return l

    def num_prime(self):
        return len(self.p)

from math import gcd
 
n = int(input())
a = list(map(int, input().split()))
 
g = a[0]
for i in range(1, n):
    g = gcd(g, a[i])
    if g == 1:
        break
else:
    print('not coprime')
    exit()

p = Prime(10**6 + 1)

tf = [False] * p.num_prime()

for i in range(1, n):
    l = p.prime_factorization_index(a[i])
    for i in l:
        if tf[i]:
            print('setwise coprime')
            exit()
        else:
            tf[i] = True

print('pairwise coprime')

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1 << 25)
readline = sys.stdin.buffer.readline
read = sys.stdin.readline  # 文字列読み込む時はこっち
ra = range
enu = enumerate


def exit(*argv, **kwarg):
    print(*argv, **kwarg)
    sys.exit()


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))
# 受け渡されたすべての要素からsubだけ引く.リストを*をつけて展開しておくこと


def a_int(): return int(readline())


def ints(): return list(map(int, readline().split()))


def _make_prime_numbers(N: int):
    # N以下の素数を列挙 -> set
    # まずエラトステネスの篩を作成
    is_prime = [True] * (N + 1)
    is_prime[0] = False  # 0と1は素数ではない
    is_prime[1] = False
    for i in range(2, int(N ** 0.5) + 1):
        if is_prime[i]:
            for j in range(i * 2, N + 1, i):  # iの倍数は素数でない
                is_prime[j] = False

    primes = []
    for i, flg in enumerate(is_prime):
        if flg:
            primes.append(i)

    return primes


primes = _make_prime_numbers(10**6)


from bisect import bisect_left


def fast_factorization(N: int):
    # -> List[Tuple[int,int]] (素数,冪数)を格納
    # 素数配列primesを使ってO(log N)で因数分解
    if N == 1:
        return []  # 1は素数ではない
    # 素因数分解
    arr = []
    temp = N
    for p in primes[:bisect_left(primes, N**(1 / 2)) + 1]:
        if temp % p == 0:
            cnt = 0
            while temp % p == 0:
                cnt += 1
                temp //= p
            arr.append((p, cnt))
            if temp == 1:  # 早期終了
                break

    if temp != 1:  # √Nより大きい素因数はたかだか1個ある
        arr.append((temp, 1))
    if arr == []:  # 自身が素数だった場合
        arr.append((temp, 1))

    return arr


MOD = 10**9 + 7
INF = 2**31  # 2147483648 > 10**9
# default import
from collections import defaultdict, Counter, deque
from math import gcd


N = a_int()
A = ints()

# setかはすぐわかる
# setでなければ not coprime
# pairは互いに素かをみればいいのか
# つまり因数分解して足してったときにすべての素数のべき数が1以下であれば良い

g_set = 0
cnt = defaultdict(lambda: 0)
flg = 1  # pairwiseであるフラグ
for a in A:
    g_set = gcd(g_set, a)
    if flg:
        for p, n in fast_factorization(a):
            if cnt[p] != 0:
                flg = 0
            cnt[p] += n


# print(cnt)
# for v in cnt.values():
#     if v > 1:
#         flg = 0
#         break

if g_set > 1:
    print('not coprime')
elif flg:
    print('pairwise coprime')
else:
    print('setwise coprime')

Submission status: Accepted

Solution code:
nn=int(input())
aa=list(map(int,input().split()))
a=[x for x in aa if x!=1]
n=len(a)
if n<=1:
  print('pairwise coprime')
  exit()

# 素因数分解
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
tmp=[i for i,j in factorization(min(a))]
not_flg=False
for t in tmp:
  flg=True
  for x in a:
    if x%t==0:
      pass
    else:
      flg=False
      break
  if flg:
    not_flg=flg
    break
if not_flg:
  if n==nn:
    print('not coprime')
  else:
    print('setwise coprime')
  exit()
#if n>78499:
if n>99999:
  print('setwise coprime')
  exit()
ary=set(())
for x in a:
  tmp={i for i,j in factorization(x)}
  for t in tmp:
    if t in ary:
      print('setwise coprime')
      exit()
    else:
      ary.add(t)
print('pairwise coprime')

Submission status: Accepted

Solution code:
from math import gcd
from functools import reduce


def main():
    input()  # N
    array = [int(x) for x in input().split()]
    MAX_A = 10 ** 6 + 1
    histogram = [0] * MAX_A
    for x in array:
        histogram[int(x)] += 1

    for divider in range(2, MAX_A):
        count = sum(histogram[divider::divider])
        if count > 1:
            break
    else:
        return 'pairwise coprime'

    gcd_total = reduce(gcd, array)
    if gcd_total == 1:
        return 'setwise coprime'
    else:
        return 'not coprime'


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

Submission status: Accepted

Solution code:
def resolve():
    import sys
    from fractions import gcd
    input = sys.stdin.readline
    n=int(input())
    a=list(map(int,input().split()))
    m=10**6+5
    chk=[0]*m
    for i in a:
      chk[i]+=1
    pw=1
    for i in range(2,m):
      cnt=0
      for j in range(i,m,i):
        cnt+=chk[j]
      if cnt>1:
        pw=0
        break
    g=a[0]
    for i in a[1:]:
      g=gcd(g,i)
    if pw==1:
      print('pairwise coprime')
    elif g==1:
      print('setwise coprime')
    else:
      print('not coprime')

if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
from math import gcd


def main():
    input()  # N
    array = [int(x) for x in input().split()]
    MAX_A = 10 ** 6 + 1
    histogram = [0] * MAX_A
    for x in array:
        histogram[int(x)] += 1
    for divider in range(2, MAX_A):
        count = 0
        for counted in histogram[divider::divider]:
            count += counted
        if count > 1:
            break
    else:
        return 'pairwise coprime'
    gcd_now = 0
    for x in array:
        gcd_now = gcd(x, gcd_now)
    if gcd_now == 1:
        return 'setwise coprime'
    else:
        return 'not coprime'


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

Submission status: Accepted

Solution code:
from math import gcd


def main():
    input()  # N
    array = [int(x) for x in input().split()]
    MAX_A = 10 ** 6 + 2
    histgram = [0] * MAX_A
    for x in array:
        histgram[int(x)] += 1
    pairwise = True
    for divider in range(2, MAX_A):
        count = 0
        for counted in histgram[divider::divider]:
            count += counted
        if count > 1:
            pairwise = False
    if pairwise:
        return 'pairwise coprime'
    gcd_now = 0
    for x in array:
        gcd_now = gcd(x, gcd_now)
    if gcd_now == 1:
        return 'setwise coprime'
    else:
        return 'not coprime'


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

Submission status: Accepted

Solution code:
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 table

N = int(input())
A = list(map(int, input().split()))
Amax = max(A)
lis = [0]*(Amax+1)
for i in range(N):
  lis[A[i]] += 1
table = sieve(Amax)
setwise = False
for t in table:
  cnt = sum(lis[t::t])
  if cnt==N:
    print('not coprime')
    break
  if 2<=cnt<N:
    setwise=True
else:
  if setwise==True:
    print('setwise coprime')
  else:
    print('pairwise coprime')

Submission status: Accepted

Solution code:
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 table

N = int(input())
A = list(map(int, input().split()))
Amax = max(A)
lis = [0]*(Amax+1)
for i in range(N):
  lis[A[i]] += 1
table = sieve(Amax)
setwise = False
for t in table:
  cnt = sum(lis[t:Amax+1:t])
  if cnt==N:
    print('not coprime')
    break
  if 2<=cnt<N:
    setwise=True
else:
  if setwise==True:
    print('setwise coprime')
  else:
    print('pairwise coprime')

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline

import math

primes = set()


def prime_factorization(n):
    global primes
    primess = set()
    i = 2
    factors = []
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
            if i not in primess and i in primes:
                print("setwise coprime")
                exit()
            primes.add(i)
            primess.add(i)
    if n > 1:
        if n not in primess and n in primes:
            print("setwise coprime")
            exit()
        primess.add(n)
        primes.add(n)


def main():
    N = int(input())
    A = [int(x) for x in input().split()]

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

    if a != 1:
        print("not coprime")
        return

    for i in range(N):
        prime_factorization(A[i])

    print("pairwise coprime")


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math
NOTCOM = "not coprime"
SETWISE = "setwise coprime"
PAIRWISE = "pairwise coprime"
MAX_A = 10 ** 6 + 5

def main():
    N = int(input())
    A = list(map(int, input().split()))
    c = [0] * MAX_A
    for a in A:
        c[a] += 1
    pairwse = True
    for i in range(2, MAX_A):
        cnt = 0
        for j in range(i, MAX_A, i):
            cnt += c[j]
        if cnt > 1: pairwse = False
    if pairwse:
        return PAIRWISE
    
    allgcd = A[0]
    for a in A:
        allgcd = math.gcd(allgcd, a)
    if allgcd == 1: return SETWISE
    return NOTCOM

print(main())

Submission status: Accepted

Solution code:
import numpy as np
import numba
from numba import njit, b1, i4, i8, f8

@njit((i8, i8[:]), cache=True)
def main(N,A):
  Amax = np.max(A)
  lis = np.zeros(Amax+1, np.int64)
  for i in range(N):
    lis[A[i]] += 1
  setwise = False
  for t in range(2,Amax+1):
    cnt = np.sum(lis[t:Amax+1:t])
    if cnt==N:
      return 'not'
    if 2<=cnt<N:
      setwise=True
  if setwise==True:
    return 'setwise'
  return 'pairwise'

N = int(input())
A = np.array(list(map(int, input().split())))
print(main(N,A)+' coprime')

Submission status: Accepted

Solution code:
def resolve():
    import sys
    input = sys.stdin.readline
    n=int(input())
    a=sorted(list(map(int,input().split())))
    ma=a[-1]
    pn=[i for i in range(ma+1)]
    for i in range(2,ma//2+1):
      j=2
      while j*i<=ma:
        pn[j*i]=min(pn[j*i],i)
        j+=1
    chk=[0]*(ma+1)
    for i in a:
      if i==1:
        continue
      x=pn[i]
      chk[x]+=1
      while x!=i:
        while i%x==0:
          i//=x
        x=pn[i]
        chk[x]+=1
    ans=2
    for i in chk[2:]:
      if i==n:
        ans=0
        break
      if i>=2:
        ans=1
    if ans==2:
      print('pairwise coprime')
    elif ans==1:
      print('setwise coprime')
    else:
      print('not coprime')

if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
from heapq import heapify, heappop, heappush
import math
import random
import string
from copy import deepcopy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

N = getN()
A = getList()

pair = True
semi = True
# not divisible
# 全部互いに素かどうか
judge = [0] * (10 ** 6 + 1)

now = A[0]
for i in A[1:]:
    now = math.gcd(now, i)
if now > 1:
    semi = False

for i in A:
    judge[i] += 1

for i in range(2, 10 ** 6 + 1):
    cnt = 0
    for j in range(i, 10 ** 6 + 1, i):
        cnt += judge[j]
    if cnt > 1:
        pair = False
        break

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

Submission status: Accepted

Solution code:
def prime(p):
    memo = set()
    for i in range(2,(int(p**0.5)+1)):
        while p%i==0:
            p //= i
            memo.add(i)
    if p != 1:
        memo.add(p)
    return memo

from math import gcd

N = int(input())

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

tmp_gcd = A[0]

#最大公約数が２以上かを判定
for i in range(1,N):
    tmp_gcd = gcd(tmp_gcd, A[i])

if 1 < tmp_gcd:
    print('not coprime')
    exit()

#素因数に被りがあるか判定
servive_prime = set()
for a in A:
    now_prime = prime(a)
    ls,ln = len(servive_prime), len(now_prime)
    servive_prime.update(now_prime)
    if len(servive_prime) < ls + ln:
        print('setwise coprime')
        exit()
#素因数被りがない場合
print('pairwise coprime')

Submission status: Accepted

Solution code:
def prime(p):
    memo = set()
    for i in range(2,(int(p**0.5)+1)):
        while p%i==0:
            p //= i
            memo.add(i)
    if p != 1:
        memo.add(p)
    return memo

from math import gcd

N = int(input())

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

tmp_gcd = A[0]

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

if 1 < tmp_gcd:
    print('not coprime')
    exit()

servive_prime = set()
for a in A:
    now_prime = prime(a)
    ls,ln = len(servive_prime), len(now_prime)
    servive_prime.update(now_prime)
    if len(servive_prime) < ls + ln:
        print('setwise coprime')
        exit()
print('pairwise coprime')

Submission status: Accepted

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

MAX = max(A)

# remap
AR = [0] * (MAX+1)
V = [False] * (MAX+1)
for i in range(N): AR[A[i]] += 1
pairwise, setwise = True, True

# sieve
for i in range(2, MAX+1):
    if V[i]: continue
    cnt, j = 0, i
    while j < MAX+1:
        cnt += AR[j]
        V[j] = True
        j += i
    if cnt > 1: pairwise = False
    if cnt == len(A): setwise = False

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

Submission status: Accepted

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

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

from functools import reduce

import math

alls = reduce(math.gcd, A)

if alls != 1:
  print("not coprime")
  exit(0)
  
# 素因数のペアが存在するかを探す
facts = [False] * (10 ** 6 + 1)

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

for a in A:
  cur = factorization(a)
  for f in cur:
    if f[0] != 1 and facts[f[0]]:
      print("setwise coprime")
      exit(0)
    else:
      facts[f[0]] = True
else:
  print("pairwise coprime")

Submission status: Accepted

Solution code:
M=10**6+1
f=lambda p: exit(print(['pairwise','setwise','not'][p]+' coprime'))
n,*l=map(int,open(0).read().split())
from math import *
g,C=0,[0]*M
for x in l:
  g=gcd(g,x)
  C[x]=1
if g>1: f(2)
if any(sum(C[i::i])>1 for i in range(2,M)): f(1)
f(0)

Submission status: Accepted

Solution code:
import sys
#ユークリッドの互除法
def gcd(x, y):
    if x % y == 0:
        return y
    else:
        return gcd(y, x % y)
#入力
N = int(input())
A = list(map(int, input().split()))
#カウントしていく
count= [0] * (1000001)
setwise_gcd = A[0]
for i in range(0,N):
    count[A[i]]+= 1
    setwise_gcd = gcd(setwise_gcd, A[i])

#全体のgcdが1でないならnot coprime
if setwise_gcd != 1:
    print("not coprime")
    sys.exit(0)
#A[x] % i == 0 && A[y] % i == 0 となるx, y が存在しないならpairwise coprime
for i in range(2,1000001):
    divided_count = count[i]
    now_number = 2 * i
    while(now_number<1000001):
        divided_count+= count[now_number]
        now_number+= i
    if(divided_count >= 2):
        print("setwise coprime")
        exit(0)
print("pairwise coprime")

Submission status: Accepted

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

read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7


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

    pairwise = True
    used = [False] * (max(A) + 1)
    
    # 同じ素因数を含むA[i]が存在するか判定
    for a in A:
        for i in range(2, int(a ** 0.5) + 1):
            if a % i == 0:
                if used[i]:
                    pairwise = False
                else:
                    used[i] = True
                    while a % i == 0:
                        a //= i
        if a != 1:
            if used[a]:
                pairwise = False
                break
            else:
                used[a] = True

    # setwiseか判定
    g = reduce(gcd, A)

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


if __name__ == '__main__':
    main()

Submission status: Accepted

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

read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7


def main():
    N = int(readline())
    A = list(map(int, readline().split()))
    used = [False] * (max(A) + 1)
    pairwise = True
    for a in A:
        for i in range(2, int(a ** 0.5) + 1):
            if a % i == 0:
                if used[i]:
                    pairwise = False
                else:
                    used[i] = True
                    while a % i == 0:
                        a //= i
        if a != 1:
            if used[a]:
                pairwise = False
                break
            else:
                used[a] = True


    g = reduce(gcd, A)

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from math import gcd

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

def isSetwise(A):
    ret = A[0]
    for a in A:
        ret = gcd(ret, a)
    return ret == 1
from collections import Counter

def createPrimeList(N):
    isPrime = [True] * (N + 1)
    isPrime[0] = False
    isPrime[1] = False
    smallestPrime = [1] * (N + 1)
    for i in range(2, N + 1):
        if not isPrime[i]:
            continue
        for p in range(i * 2, N, i):
            if isPrime[p]:
                smallestPrime[p] = i
            isPrime[p] = False
    return smallestPrime

from collections import Counter
smallestPrime = createPrimeList(max(A) + 10)
def primeFactorization(N):
    ret = Counter()
    while N > 1:
        p = smallestPrime[N]
        if p == 1:
            ret[N] += 1
            break
        ret[p] += 1
        N //= p
    return ret

def isPairwise(A):
    P = Counter()
    for a in A:
        for p in primeFactorization(a):
            if P[p] >= 1:
                return False
            P[p] += 1
    return True

if not isSetwise(A):
    print('not coprime')
    exit()

if isPairwise(A):
    print('pairwise coprime')
else:
    print('setwise coprime')

Submission status: Accepted

Solution code:
import numpy as np
from numba import njit

n = int(input())
a = list(map(int, input().split()))
MAX = 10 ** 6

nums = np.zeros(MAX + 1, np.int64)
for e in a:
    nums[e] += 1


@njit
def solve(nums):
    mx = 0
    for i in range(2, MAX + 1):
        cnt = nums[i::i].sum()
        mx = max(mx, cnt)

    return mx


mx = solve(nums)

if nums[1] == n:
    ans = "pairwise"
elif mx == n:
    ans = "not"
elif mx == 1:
    ans = "pairwise"
else:
    ans = "setwise"

ans += " coprime"

print(ans)