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: Wrong Answer

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 f == 0:
            if b & ps:
                f = 1
                break
    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: Wrong Answer

Solution code:
# 自然数m以下の素数を返す（SETでRETURN）
import math
def prime_numbers(m):
    # 素数を保持するset
    primes = []

    # 2以上m以下の素数を数え上げる
    n = 2
    while n <= m:
        # 自身より小さい全ての素数で割り切れなければ、素数とみなせる
        if all(n % i != 0 for i in primes):
            primes.append(n)
        n += 1
    return primes

#素因数分解（10**6まで）
def soinsu_bunkai(m):
    pf=set()

    for i in pri_num:
        while m%i==0:
            pf.add(i)
            m//=i
    if m>1:
        pf.add(1)
    return pf


# 初期入力
import sys
from collections import Counter
input = sys.stdin.readline  #文字列では使わない
N = int(input())
A = list(map(int, input().split()))

# 10**6までの素因数分解するために、「10**6のルート」までの素数を列挙
pri =10**6 +10
sq_pri =int(math.sqrt(pri))
pri_num =prime_numbers(sq_pri +10)

#素因数分解しながら判定の下準備
pair_w =set()
set_w =set()
not_judg =[]
intersect =set()
prim_list_dic =dict()
for a in A:
    aa =soinsu_bunkai(a)
    if intersect & aa:
        pair_w.add(0)
    else:
        pair_w.add(1)
    not_judg.extend(list(aa))
    intersect |=aa
    prim_list_dic[a] =aa

#判定
ans ="setwise coprime"
c =Counter(not_judg)
#pairwise coprimeの判定
if 1 in pair_w and 0 not in pair_w:
    ans ="pairwise coprime"

#not coprimeの判定
elif N in c.values():
    ans ="not coprime"

print(ans)

Submission status: Wrong Answer

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


def divisor(n):
    l = []
    i = 1
    while True:
        if n % i == 0:
            l.append(i)
            if i * i != n:
                l.append(n / i)
        if i * i >= n:
            break
        i += 1
    return sorted(l)


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

gcd_of_all = gcd(a[0], a[1])
for i in range(2, n):
    gcd_of_all = gcd(gcd_of_all, a[i])

if gcd_of_all != 1:
    print("not coprime")
    exit()

s = set()

for i in range(n):
    l = divisor(a[i])
    for j in range(len(l)):
        if l[j] == 1:
            continue
        if l[j] in s:
            print("setwise coprime")
            exit()
        else:
            s.add(l[j])

print("pairwise coprime")
exit()

Submission status: Wrong Answer

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(N):
    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: Wrong Answer

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):
        arr = []
        temp = self.n
        for i in range(2, int(-(-self.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))
        if len(arr) == 0:
            arr.append((self.n, 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))
        if len(arr) == 0:
            arr.append((num, 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):
        for p, _ in tool.fast_factorization(Ai):
            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()