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 math

N = 1000001
 
spf = [*range(N)]
i = 2
while i * i < N:
  if spf[i] == i:
    for j in range(i * i, N, i):
      if spf[j] == j:
        spf[j] = i
  i += 1
  
r = 'pairwise'

input()
d = None
u = set()
for x in map(int, input().split()):
  d = math.gcd(d or x, x)
  s = set()
  while x > 1:
    p = spf[x]
    if p in u:
      r = 'setwise'
    s.add(p)
    x //= p
  u |= s
print((r, 'not')[d > 1], 'coprime')

Submission status: Accepted

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

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

    MAXA = 10**6
    B = [0] * (MAXA+1)
    for a in A:
        if a==1: continue
        if B[a]:
            print('setwise coprime')
            exit()
        B[a] = 1

    for n in range(2,MAXA+1):
        c = 0
        for m in range(n,MAXA+1,n):
            c += B[m]
            if c > 1:
                print('setwise coprime')
                exit()

    print('pairwise coprime')
solve()

Submission status: Accepted

Solution code:
import numpy as np


def main():
    int(input())
    a = np.array([int(i) for i in input().split()])
    m = a.max() + 1
    p = np.zeros(m, dtype=int)
    for i in range(2, m):
        if p[i] == 0:
            p[i::i] = i
    factors = set()
    for ai in a[a > 1]:
        f = set()
        while ai > p[ai]:
            f.add(p[ai])
            ai //= p[ai]
        f.add(ai)
        if factors & f:
            break
        factors |= f
    else:
        print("pairwise coprime")
        return
    if np.gcd.reduce(a) == 1:
        print("setwise coprime")
    else:
        print("not coprime")


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math


def divisorGenerator(n):

    large_divisors = []
    for i in range(1, int(math.sqrt(n) + 1)):
        if n % i == 0:
            yield i
            if i*i != n:
                large_divisors.append(n // i)
    for divisor in reversed(large_divisors):
        yield divisor

if __name__ == '__main__':

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

    gcd_ = math.gcd(A[0], A[1])
    for i in range(2, len(A)):
        gcd_ = math.gcd(gcd_, A[i])

    set_wise = False
    if gcd_ == 1:
        set_wise = True
    if not(set_wise):
        print("not coprime")
    else:
        pairwise = True
        divs = dict()
        for i in A:
            res = list(divisorGenerator(i))
            for el in res:
                if el != 1:
                    if not(el in divs):
                        divs[el] = 0
                    divs[el] += 1
                    if divs[el] > 1:
                        print("setwise coprime")
                        exit()
        print("pairwise coprime")
        # for value in divs.values():
        #     if value > 1:
        #         pairwise = False
        #         break
        # if pairwise:
        #     print("pairwise coprime")
        # else:
        #
        #

Submission status: Accepted

Solution code:
from math import gcd


def main():
    n = int(input())
    a = [int(i) for i in input().split()]
    m = max(a)
    p = [0] * (m + 1)
    for i in range(2, m + 1):
        if p[i] == 0:
            for j in range(i, m + 1, i):
                p[j] = i
    factors = set()
    for ai in a:
        if ai == 1:
            continue
        f = set()
        while ai > p[ai]:
            f.add(p[ai])
            ai //= p[ai]
        f.add(ai)
        if factors & f:
            break
        factors |= f
    else:
        print("pairwise coprime")
        return
    g = a[0]
    for ai in a[1:]:
        g = gcd(ai, g)
        if g == 1:
            print("setwise coprime")
            return
    print("not coprime")


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from math import gcd

def sieve(n):
    res = [i for i in range(n+1)]
    for i in range(2, int(n**0.5) + 1):
        if res[i] < i:
            continue
        for j in range(i*i, n + 1, i):
            if res[j] == j:
                res[j] = i
    return res

def factor(n, min_factor):
    res = []
    while n > 1:
        res.append(min_factor[n])
        n //= min_factor[n]
    return res

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

flag = [0] * (10 ** 6 + 1)

D = sieve(10 ** 6)

flag1 = 0
flag2 = 1

GCD = A[0]

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

if GCD == 1:
    flag1 = 1

for i in range(N):
    L = factor(A[i], D)
    L = set(L)
    for j in L:
        if flag[j]:
            flag2 = 0
            break
        flag[j] = 1
    if not flag2:
        break

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

Submission status: Accepted

Solution code:

from math import gcd
def resolve():
    N = int(input())
    A = list(map(int, input().split()))
    max_A = max(A) + 10

    CNT = [0] * max_A
    for a in A:
        CNT[a] += 1

    bl = True
    for i in range(2, max_A):
        cnt = 0
        for j in range(i, max_A, i):
            cnt += CNT[j]
        if cnt > 1:
            bl = False
    if bl:
        print("pairwise coprime")
        return

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

    print("not coprime")


if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
from collections import defaultdict
max = 10 ** 6
sieve = [None] * (max + 1)
for i in range(2, max + 1):
    if sieve[i] == None: # i is prime
        for ki in range(i, max + 1, i):
            sieve[ki] = i
def factors(n):
    while True:
        if sieve[n] is None:
            break
        yield sieve[n]
        n //= sieve[n]
used = defaultdict(lambda:0)

n = int(input())
a = map(int, input().split())
for ai in a:
    for factor in set(factors(ai)):
        used[factor] += 1
pairwise = True
setwise = True
for prime in used:
    if used[prime] > 1:
        pairwise = False
    if used[prime] == n:
        setwise = False
if pairwise:
    print("pairwise coprime")
elif setwise:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Accepted

Solution code:
from math import gcd
def preprocess(n):
    """
    n以下の自然数の高速素因数分解の前処理

    Parameters
    ----------
    n: int
        自然数

    Returns
    -------
    MinFactor:list
      高速素因数分解用のMinFactorテーブル
    """
    f = []
    is_prime = [True]*(n+1)
    is_prime[0] = False
    is_prime[1] = False
    # MinFactor[x]:xに含まれる最小の素因子
    MinFactor = [-1]*(n+1)
    MinFactor[0] = 0
    MinFactor[1] = 1

    for i in range(2, n+1):
        if is_prime[i]:
            MinFactor[i] = i
            f.append(i)
            for j in range(i*2, n+1, i):
                is_prime[j] = False
                if MinFactor[j] == -1:
                    MinFactor[j] = i
    """
    return値
     1.素数か否かの判定結果:is_prime
     2.素数のリスト:f
     3.高速素因数分解用のMinFactorテーブル
    """
    return MinFactor

def prime_factorize(n,MinFactor):
    # res = []
    while n != 1:
        prime = MinFactor[n]
        # exp = 0
        while MinFactor[n] == prime:
            # exp += 1
            n //= prime
        cnt[prime] += 1
        # res.append((prime,exp))
    # return res

n = int(input())
a = list(map(int, input().split()))
a_max = max(a)
g = a[0]
for aa in a:
    g = gcd(g,aa)

mf = preprocess(a_max)
cnt = [0]*(a_max+1)
for aa in a:
    prime_factorize(aa,mf)

if g != 1:
    print("not coprime")
elif max(cnt) <= 1:
    print("pairwise coprime")
else:
    print("setwise coprime")

Submission status: Accepted

Solution code:
from functools import reduce

n = int(input())
a = list(map(int, input().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 prime_factorize(n):
    res = []
    if n == 1:
        return res
    while n > 1:
        res.append(d[n])
        n //= d[n]
    return res

def is_pairwise_coprime():
    exists = [0] * (m + 1)
    for ai in a:
        for p in set(prime_factorize(ai)):
            if exists[p]:
                return False
            exists[p] = 1
    return True

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

def is_setwise_coprime():
    return reduce(gcd, a) == 1


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

Submission status: Accepted

Solution code:
from math import gcd


class Eratosthenes(): # エラトステネスの篩
    def __init__(self, N): # 素数リスト生成 O(n*log(log n))
        self.fact = [i for i in range(N + 1)]
        for i in range(2, int(N**0.5) + 1):
            if self.fact[i] < i:
                continue
            for j in range(i * 2, N + 1, i):
                self.fact[j] = i


    def factor(self, NUM): # 高速素因数分解 O(log num)
        PRIME = set()
        while NUM > 1:
            PRIME.add(self.fact[NUM])
            NUM //= self.fact[NUM]
        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()

era = Eratosthenes(max(a))
num = set()
for ai in a:
    prime = era.factor(ai)
    if len(prime & num) > 0:
        print('setwise coprime')
        break
    num |= prime
else:
    print('pairwise coprime')