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 numpy as np
import sys
i4 = np.int32
i8 = np.int64
u4 = np.uint32

if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC
    from numba import njit
    from numba.types import int64, Array, uint32
    cc = CC('my_module')

    @cc.export('factorization', (uint32, ))
    @njit
    def factorization(N):
        p = np.zeros(N + 1, u4)
        n_max = int(np.sqrt(N)) + 1
        p[0] = 1
        p[1] = 1
        for i in range(2, n_max):
            if p[i] == 0:
                j = i
                while j <= N:
                    p[j] = i
                    j += i
        for i in range(n_max, N + 1):
            if p[i] == 0:
                p[i] = i
        return p

    @cc.export('solve', (Array(uint32, 1, 'C'),))
    def solve(A):
        a = np.sort(A)
        p_max = a[-1]
        p = factorization(p_max)
        primes_num = 0
        for i in range(p.shape[0]):
            if i == p[i]:
                primes_num += 1
        a_start = 0
        while a[a_start] == 1:
            a_start += 1
            if a_start == a.shape[0]:
                return 0
        a = a[a_start:]
        if len(a) > primes_num:
            return 1
        check = np.zeros(p_max + 1, u4)
        stack = np.empty(20, u4)
        p_stack = 0
        for d in a:
            while d > 1:
                x = p[d]
                for i in range(p_stack):
                    if stack[i] == x:
                        break
                else:
                    stack[p_stack] = x
                    p_stack += 1
                d //= x

            while p_stack > 0:
                p_stack -= 1
                check[stack[p_stack]] += 1

        if check.max() > 1:
            return 1
        else:
            return 0
    cc.compile()
    from my_module import solve, factorization
    exit()

from my_module import solve, factorization

def main(in_file):
    stdin = open(in_file)
    stdin.readline()
    A = np.fromstring(stdin.readline(), u4, sep=' ')
    ans = solve(A)
    if ans:
        g = np.gcd.reduce(A)
        if g > 1:
            ans = 2
        else:
            ans = 1
    p = ['pairwise coprime', 'setwise coprime', 'not coprime']
    print(p[ans])


if __name__ == '__main__':
    main('/dev/stdin')

Submission status: Accepted

Solution code:
import numpy as np
import sys
i4 = np.int32
i8 = np.int64
u4 = np.uint32

if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC
    from numba import njit
    from numba.types import int64, Array, uint32
    cc = CC('my_module')

    @njit
    def factorization(N):
        p = np.zeros(N + 1, u4)
        n_max = int(np.sqrt(N)) + 1
        p[0] = 1
        p[1] = 1
        for i in range(2, n_max):
            if p[i] == 0:
                j = i
                while j <= N:
                    p[j] = i
                    j += i
        for i in range(n_max, N + 1):
            if p[i] == 0:
                p[i] = i
        return p

    @cc.export('solve', (Array(uint32, 1, 'C'),))
    def solve(A):
        a = np.sort(A)
        p_max = a[-1]
        p = factorization(p_max)
        primes_num = 0
        for i in range(p.shape[0]):
            if i == p[i]:
                primes_num += 1
        a_start = 0
        while a[a_start] == 1:
            a_start += 1
            if a_start == a.shape[0]:
                return 0
        a = a[a_start:]
        if len(a) > primes_num:
            return 1
        check = np.zeros(p_max + 1, i8)
        stack = np.empty(20, i8)
        p_stack = 0
        for d in a:
            while d > 1:
                x = p[d]
                for i in range(p_stack):
                    if stack[i] == x:
                        break
                else:
                    stack[p_stack] = x
                    p_stack += 1
                d //= x

            while p_stack > 0:
                p_stack -= 1
                check[stack[p_stack]] += 1

        if check.max() > 1:
            return 1
        else:
            return 0
    cc.compile()
    exit()


def main(in_file):
    stdin = open(in_file)
    stdin.readline()
    A = np.fromstring(stdin.readline(), u4, sep=' ')
    ans = solve(A)
    if ans:
        g = np.gcd.reduce(A)
        if g > 1:
            ans = 2
        else:
            ans = 1
    p = ['pairwise coprime', 'setwise coprime', 'not coprime']
    print(p[ans])


if __name__ == '__main__':
    from my_module import solve
    main('/dev/stdin')

Submission status: Accepted

Solution code:
max_num = 10**6 + 1
prime = [i for i in range(max_num)]
r2_num = int(max_num**(1/2))+1
for i in range(2, r2_num):
  if prime[i] == i:
    for j in range(i**2, max_num, i):
      if prime[j] == j:
        prime[j] = i
def gcd(a, b): # a >= b
  if a%b == 0:
    return b
  else:
    return gcd(b, a%b)

flg_pairwise = True
flg_setwise = False

n = int(input().rstrip())
a_ls = list(map(int, input().rstrip().split(" ")))
gcd_a = 0
primes_a = []
count_prime = [0 for i in range(max_num)]
for a in a_ls:
  gcd_a = gcd(gcd_a, a)
  if gcd_a == 1:
    flg_setwise = True
  tmp_prime = 0
  while a > 1:
    p = prime[a]
    pp = prime[p]
    if p == 0 or pp == 0:
      flg_pairwise = False
      break
    if tmp_prime != p:
      prime[tmp_prime] = 0
      tmp_prime = p
    a = a//p
  if flg_pairwise:
    prime[tmp_prime] = 0
  if flg_setwise and not flg_pairwise:
    break
if flg_pairwise:
  print("pairwise coprime")
elif flg_setwise:
  print("setwise coprime")
else:
  print("not coprime")

Submission status: Accepted

Solution code:
from functools import reduce
from math import gcd

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

c=max(A)+1
D=[0]*c
div=[0]*c
P=[]

for i in range(2,c):
    if D[i]==0:
        P.append(i)
        D[i]=i
    for j in P:
        if i*j>=c  or j>D[i] :
           break
        D[i*j]=j
f=0
for i in A:
    if i==1:
        continue
    temp=i
    while temp!=1:
        if div[D[temp]]==1:
            f=1
            break
        div[D[temp]]+=1
        temp2=D[temp]
        while temp%temp2==0 and temp>=temp2:
            temp=temp//temp2
    if f==1:
        break
        


if max(div)<=1 and f==0:
    print('pairwise coprime')

elif reduce(gcd, A) == 1:
    print('setwise coprime')

else:
    print('not coprime')

Submission status: Accepted

Solution code:
from functools import reduce
from math import gcd

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

c=max(A)+1
D=[0]*c
div=[0]*c
P=[]

for i in range(2,c):
    if D[i]==0:
        P.append(i)
        D[i]=i
    for j in P:
        if i*j>=c  or j>D[i] :
           break
        D[i*j]=j
f=0
for i in A:
    if i==1:
        continue
    temp=i
    while temp!=1:
        if div[D[temp]]==1:
            f=1
            break
        div[D[temp]]+=1
        temp2=D[temp]
        while temp%temp2==0 and temp>=temp2:
            temp=temp//temp2
    if f==1:
        break
        
if f==0:
    print('pairwise coprime')

elif reduce(gcd, A) == 1:
    print('setwise coprime')

else:
    print('not coprime')

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
from collections import defaultdict
def main():
    n, *a = map(int, read().split())

    maxa = max(a) + 1  # aはint配列
    d = [i for i in range(maxa)]
    for p0 in range(2, maxa):
        if p0 == d[p0]:
            for p1 in range(p0 ** 2, maxa, p0):
                if d[p1] % p0 == 0:
                    d[p1] = p0

    def factorization(f):  # f > maxaだとエラー
        l = []
        t = f
        while True:
            if t == d[t]:
                l.append(d[t])
                break
            else:
                l.append(d[t])
                t = t // d[t]
        return l

    if all([i == 1 for i in a]):
        print('pairwise coprime')
        sys.exit()
    if len(set(a)) == 1:
        print('not coprime')
        sys.exit()
    d1 = defaultdict(int)
    for ae in a:
        t1 = set(factorization(ae))
        for t1e in t1:
            d1[t1e] += 1
    if 1 in a:
        d1[1] = 1
    d1v = tuple(d1.values())
    if all([i == 1 for i in d1v]):
        print('pairwise coprime')
    elif max(d1v) == n:
        print('not coprime')
    else:
        print('setwise coprime')

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import numpy as np
import sys
i4 = np.int32
i8 = np.int64

if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC
    from numba import njit
    from numba.types import int64, Array
    cc = CC('my_module')

    @njit
    def factorization(N):
        p = np.zeros(N + 1, i8)
        n_max = int(np.sqrt(N)) + 1
        p[0] = 1
        p[1] = 1
        for i in range(2, n_max):
            if p[i] == 0:
                j = i
                while j <= N:
                    p[j] = i
                    j += i
        for i in range(n_max, N + 1):
            if p[i] == 0:
                p[i] = i
        return p

    @cc.export('solve', (Array(int64, 1, 'C'),))
    def solve(A):
        a = np.sort(A)
        p_max = a[-1]
        p = factorization(p_max)
        primes_num = 0
        for i in range(p.shape[0]):
            if i == p[i]:
                primes_num += 1
        a_start = 0
        while a[a_start] == 1:
            a_start += 1
            if a_start == a.shape[0]:
                return 0
        a = a[a_start:]
        if len(a) > primes_num:
            return 1
        check = np.zeros(p_max + 1, i8)
        stack = np.empty(20, i8)
        p_stack = 0
        for d in a:
            while d > 1:
                x = p[d]
                for i in range(p_stack):
                    if stack[i] == x:
                        break
                else:
                    stack[p_stack] = x
                    p_stack += 1
                d //= x

            while p_stack > 0:
                p_stack -= 1
                check[stack[p_stack]] += 1

        if check.max() > 1:
            return 1
        else:
            return 0
    cc.compile()
    exit()


def main(in_file):
    stdin = open(in_file)
    stdin.readline()
    A = np.fromstring(stdin.readline(), i8, sep=' ')
    ans = solve(A)
    if ans:
        g = np.gcd.reduce(A)
        if g > 1:
            ans = 2
        else:
            ans = 1
    p = ['pairwise coprime', 'setwise coprime', 'not coprime']
    print(p[ans])


if __name__ == '__main__':
    from my_module import solve
    main('/dev/stdin')

Submission status: Accepted

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

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

#高速素因数分解

#エラストテネスのふるい
#sieveが0なら素数、0以外ならその値を割り切る素数
def create_sieve(n):
  sieve=[0]*(n+1)
  for i in range(2,n+1):
    if sieve[i]==0:
      for j in range(i*i,n+1,i):
        sieve[j]=i
  return sieve
#素因数分解
#dicではkey=素数、value=何乗か
def prime(n,sieve):
  dic={}
  while(1):
    if sieve[n]==0:
      dic[n]=dic.get(n,0)+1
      break
    else:
      p=sieve[n]
      dic[p]=dic.get(p,0)+1
      n=n//p
  return dic

def setwise(a):
  l=a[0]
  for i in range(len(a)):
    l=gcd(l,a[i])
  return l==1


if setwise(a):
  check=set()
  sieve=create_sieve(max(a))
  for num in a:
    if num!=1:
      dic=prime(num,sieve)
      for j in dic:
        if j in check:
          print("setwise coprime")
          exit()
        else:
          check.add(j)
  print("pairwise coprime")
  
else:
  print("not coprime")

Submission status: Accepted

Solution code:
import numpy as np
import sys
i4 = np.int32
i8 = np.int64

if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC
    from numba import njit
    from numba.types import int64, Array
    cc = CC('my_module')

    @njit
    def factorization(N):
        p = np.zeros(N + 1, i8)
        n_max = int(np.sqrt(N)) + 1
        p[0] = 1
        p[1] = 1
        for i in range(2, n_max):
            if p[i] == 0:
                j = i
                while j <= N:
                    p[j] = i
                    j += i
        for i in range(n_max, N + 1):
            if p[i] == 0:
                p[i] = i
        return p

    @cc.export('solve', (Array(int64, 1, 'C'),))
    def solve(A):
        a = np.sort(A)
        p_max = a[-1]
        p = factorization(p_max)
        primes_num = 0
        for i in range(p.shape[0]):
            if i == p[i]:
                primes_num += 1
        a_start = 0
        while a[a_start] == 1:
            a_start += 1
            if a_start == a.shape[0]:
                return 0
        a = a[a_start:]
        if len(a) > primes_num:
            return 1
        check = np.zeros(p_max + 1, i8)
        stack = np.empty(20, i8)
        p_stack = 0
        for d in a:
            while d > 1:
                x = p[d]
                for i in range(p_stack):
                    if stack[i] == x:
                        break
                else:
                    stack[p_stack] = x
                    p_stack += 1
                d //= x

            while p_stack > 0:
                p_stack -= 1
                check[stack[p_stack]] += 1

        if check.max() > 1:
            return 1
        else:
            return 0
    cc.compile()
    exit()


def main(in_file):
    stdin = open(in_file)
    stdin.readline()
    A = np.array([int(x) for x in stdin.readline().split()])
    ans = solve(A)
    if ans:
        g = np.gcd.reduce(A)
        if g > 1:
            ans = 2
        else:
            ans = 1
    p = ['pairwise coprime', 'setwise coprime', 'not coprime']
    print(p[ans])


if __name__ == '__main__':
    from my_module import solve
    main('/dev/stdin')

Submission status: Accepted

Solution code:
N = int(input())

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

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

freq = [0] * 1000005

for i in range(len(A)):
    freq[A[i]] += 1

pairwise = True

for i in range(2, 1000005):
    cnt = 0
    for j in range(i, 1000005, i):
        cnt += freq[j]
    # 2箇所以上に素因数が現れたら、pairwiseではない    
    if cnt > 1:
        pairwise = False

if pairwise:
    print("pairwise coprime")
    exit()

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

Submission status: Accepted

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

maxn =  1000005
prime = [0 for _ in range(maxn)]

for i in range(2, maxn):
    if prime[i] == 0:
        for j in range(i, maxn, i):
            prime[j] = i #最大質因數

st = set() #目前出現過的所有質因數，一開始為A[0]的所有質因數
a = A[0]
while prime[a]:
    st.add(prime[a])
    x = prime[a]
    while (a % x == 0):
        a //= x

pairwise = True
st2 = st #所有數共有的質因數，一開始為A[0]的所有質因數
for a in A[1:]:
    tmp = set()
    for j in st2:
        if a % j == 0:
            tmp.add(j)

    st2 = tmp
    if pairwise:
        while prime[a]:
            if prime[a] in st:
                pairwise = False
            st.add(prime[a])
            x = prime[a]
            while (a % x == 0):
                a //= x

if pairwise:
    print("pairwise coprime")
elif len(st2) == 0:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Accepted

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

maxV = (10 ** 6 + 1)

sieve = [i for i in range(maxV)]
p = 2

while p*p < maxV:
    if sieve[p] == p:
        for q in range(p*2, maxV, p):
            if sieve[q] == q:
                sieve[q] = p
    p += 1

from math import gcd

g = 0
primes = set()
for a in A:
    g = gcd(g, a)

    v = a


if g > 1:
    print('not coprime')
    exit()

for a in A:
    temp_prime = set()
    while a > 1:
        prime = sieve[a]
        temp_prime.add(prime)
        a = a // prime

    for t in temp_prime:
        if t in primes:
            print('setwise coprime')
            exit()
        primes.add(t)

print('pairwise coprime')