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:
# coding: utf-8
from math import gcd

def getPrime(x):
    num_list=[i for i in range(2,x+1)]
    prime_list=[]
    D=[x+1 for i in range(x+1)]
    
    while num_list[0]<x**(1/2):
        p=num_list.pop(0)
        prime_list.append(p)
        for i in range(len(num_list)):
            if num_list[i]%p==0:
                if D[num_list[i]]>p:
                    D[num_list[i]]=p
        num_list = [e for e in num_list if e % p != 0]
    
    prime_list = prime_list + num_list
    for i in range(len(prime_list)):
        D[prime_list[i]] = prime_list[i]
    D[0]=1
    D[1]=1
    return D

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

if max(A) == 1:
    print("pairwise coprime")
    exit()

D = getPrime(max(A))

pc_flg = True

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

prime_flg=[False for i in range(10**6+1)]

for i in range(N):
    num = A[i]
    primes = []
    while True:
        p = D[num]
        num = num//p
        primes.append(p)
        if num == 1:
            break
    for j in set(primes):
        if not(prime_flg[j]):
            prime_flg[j] = True
        else:
            if j != 1:
                pc_flg = False


if pc_flg:
    print("pairwise coprime")
elif x==1:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
if a == [1]*n:
    print("pairwise coprime")
    quit()
m = max(a)
l = [-1]*(m+3)
for i in range(2,m+1):
    if l[i] != -1:
        continue
    l[i] = i
    j = 2
    while i*j <= m:
        if l[i*j] == -1:
            l[i*j] = i
        j += 1
def fastfact(i,lst):
    if l[i] == -1:
        return lst
    while i > 1:
        lst.append(l[i])
        i //= l[i]
    return lst
check = [0]*(m+1)
for i in range(n):
    if a[i] == 1:
        continue
    s = set(fastfact(a[i],[]))
    for j in s:
        check[j] += 1
M = max(check)
if M == 1:
    print("pairwise coprime")
elif M == n:
    print("not coprime")
else:
    print("setwise coprime")

Submission status: Accepted

Solution code:
from math import gcd 
 
n = int(input())
maxA = 10**6+1
A = list(map(int, input().split()))
c = [0]*maxA
for a in A:
    c[a] += 1

for i in range(2, maxA):
    cnt = 0
    for j in range(i, maxA, i):
        cnt += c[j]
    if cnt >= 2:
        break
else:
    print('pairwise coprime')
    exit()

g = A[0]
for a in A[1:]:
    g = gcd(g, a)
if g == 1:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Accepted

Solution code:
from math import gcd 
 
n = int(input())
maxA = 10**6+5
A = list(map(int, input().split()))
c = [0]*maxA
for a in A:
    c[a] += 1

for i in range(2, maxA):
    cnt = 0
    for j in range(i, maxA, i):
        cnt += c[j]
    if cnt >= 2:
        break
else:
    print('pairwise coprime')
    exit()

g = A[0]
for a in A[1:]:
    g = gcd(g, a)
if g == 1:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Accepted

Solution code:
c=[0]*6**8
for a in[*open(0)][1].split():c[int(a)]+=1
m=max(sum(c[i::i])for i in range(2,6**8))
print(m<sum(c)and'psaeitr'[m>1::2]+'wise'or'not','coprime')

Submission status: Accepted

Solution code:
c=[0]*6**8
n,a=open(0)
for a in a.split():c[int(a)]+=1
m=max(sum(c[i::i])for i in range(2,6**8))
print(('not','psaeitr'[m>1::2]+'wise')[m<int(n)],'coprime')

Submission status: Accepted

Solution code:
c=[m:=0]*6**8
n,a=open(0)
for a in a.split():c[int(a)]+=1
print(('not','psaeitr'[any([(m:=max(m,sum(c[i::i])))>1for i in range(2,6**8)])::2]+'wise')[m<int(n)],'coprime')

Submission status: Accepted

Solution code:
from math import gcd
from functools import reduce
from collections import Counter


class Osa_k:
    def __init__(self, maximum):
        self.table = [-1] * (maximum+1)
        for i in range(2, maximum+1):
            if self.table[i] != -1:
                continue
            self.table[i] = i
            for k in range(i*i, maximum+1, i):
                if self.table[k] == -1:
                    self.table[k] = i

    def factorize(self, n):
        res = Counter()
        b = n
        while 1:
            if self.table[b] == -1:
                break
            res[self.table[b]] += 1
            b //= self.table[b]
        if b != 1:
            res[b] += 1
        return res


N = int(input())
*A, = map(int, input().split())
def f():
    cnt = Counter()
    ins = Osa_k(max(A))
    for i in A:
        res = ins.factorize(i)
        for j in res.keys():
            cnt[j] += 1
            if cnt[j] >= 2:
                return False
    return True

cond1 = f()
cond2 = (reduce(gcd, A)==1)

if cond1:
    print("pairwise coprime")
elif cond2:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Accepted

Solution code:
from math import gcd
from functools import reduce
from collections import Counter


class Osa_k:
    def __init__(self, maximum):
        self.table = [-1] * (maximum+1)
        for i in range(2, maximum+1):
            if self.table[i] != -1:
                continue
            for j in range(2, int(i**0.5)+1):
                if i%j == 0:
                    self.table[i] = j
                    for k in range(2*i, maximum+1, i):
                        if self.table[k] != -1:
                            self.table[k] = j
                    break

    def factorize(self, n):
        res = Counter()
        b = n
        while 1:
            if self.table[b] == -1:
                break
            res[self.table[b]] += 1
            b //= self.table[b]
        res[b] += 1
        return res


N = int(input())
*A, = map(int, input().split())
def f():
    cnt = Counter()
    ins = Osa_k(max(A))
    for i in A:
        res = ins.factorize(i) if i!=1 else {}
        for j in res.keys():
            cnt[j] += 1
            if cnt[j] >= 2:
                return False
    return True

cond1 = f()
cond2 = (reduce(gcd, A)==1)

if cond1:
    print("pairwise coprime")
elif cond2:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Accepted

Solution code:
from math import gcd
from functools import reduce
from collections import Counter


class Osa_k:
    def __init__(self, maximum):
        self.table = [-1] * (maximum+1)
        for i in range(2, maximum+1):
            if self.table[i] != -1:
                continue
            for j in range(2, int(i**0.5)+1):
                if i%j == 0:
                    self.table[i] = j
                    for k in range(2*i, maximum+1, i):
                        if self.table[k] != -1:
                            self.table[k] = j
                    break

    def factorize(self, n):
        res = Counter()
        b = n
        while 1:
            if self.table[b] == -1:
                break
            res[self.table[b]] += 1
            b //= self.table[b]
        res[b] += 1
        return res


N = int(input())
*A, = map(int, input().split())
def f():
    cnt = Counter()
    ins = Osa_k(10**6)
    for i in A:
        res = ins.factorize(i) if i!=1 else {}
        for j in res.keys():
            cnt[j] += 1
            if cnt[j] >= 2:
                return False
    return True

cond1 = f()
cond2 = (reduce(gcd, A)==1)

if cond1:
    print("pairwise coprime")
elif cond2:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Accepted

Solution code:
from math import gcd
from functools import reduce
from collections import Counter


class Osa_k:
    def __init__(self, maximum):
        self.table = [-1] * (maximum+1)
        for i in range(2, maximum+1):
            for j in range(2, int(i**0.5)+1):
                if i%j == 0:
                    self.table[i] = j
                    break

    def factorize(self, n):
        res = Counter()
        b = n
        while 1:
            if self.table[b] == -1:
                break
            res[self.table[b]] += 1
            b //= self.table[b]
        res[b] += 1
        return res


N = int(input())
*A, = map(int, input().split())
def f():
    cnt = Counter()
    ins = Osa_k(10**6)
    for i in A:
        res = ins.factorize(i) if i!=1 else {}
        for j in res.keys():
            cnt[j] += 1
            if cnt[j] >= 2:
                return False
    return True

cond1 = f()
cond2 = (reduce(gcd, A)==1)

if cond1:
    print("pairwise coprime")
elif cond2:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Accepted

Solution code:
c=[0]*6**8
n,a=open(0)
for a in a.split():c[int(a)]+=1
print(('not','psaeitr'[any(c:=[max(0,sum(c[i::i])-1)for i in range(2,6**8)])::2]+'wise')[max(c)+1<int(n)],'coprime')

Submission status: Accepted

Solution code:
from math import gcd
from functools import reduce
from collections import Counter


class Osa_k:
    def __init__(self, maximum):
        self.table = [-1] * (maximum+1)
        for i in range(2, maximum+1):
            for j in range(2, int(i**0.5)+1):
                if i%j == 0:
                    self.table[i] = j
                    break

    def factorize(self, n):
        res = Counter()
        b = n
        while 1:
            if self.table[b] == -1:
                break
            res[self.table[b]] += 1
            b //= self.table[b]
        res[b] += 1
        return res


N = int(input())
*A, = map(int, input().split())
def f():
    cnt = Counter()
    ins = Osa_k(max(A))
    for i in A:
        res = ins.factorize(i) if i!=1 else {}
        for j in res.keys():
            cnt[j] += 1
            if cnt[j] >= 2:
                return False
    return True

cond1 = f()
cond2 = (reduce(gcd, A)==1)

if cond1:
    print("pairwise coprime")
elif cond2:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Accepted

Solution code:
m=6**8
c=[0]*m
n,a=open(0)
for a in a.split():c[int(a)]+=1
print(('not','psaeitr'[any(c:=[max(0,sum(c[i::i])-1)for i in range(2,m)])::2]+'wise')[max(c)+1<int(n)],'coprime')

Submission status: Accepted

Solution code:
import math
m=6**8
c=[g:=0]*m
for a in[*open(0)][1].split():g=math.gcd(g,a:=int(a));c[a]+=1
print(('not','psaeitr'[any(sum(c[i::i])>1for i in range(2,m))::2]+'wise')[g<2],'coprime')

Submission status: Accepted

Solution code:
n,*a=map(int,open(0).read().split())
m=6**8
c=[0]*m
p=[1,1]+c[:]
for i in range(m):
  if p[i]<1:
    for j in range(i,m,i):p[j]=i
for a in a:
  s={a}
  while a!=p[a]:
    s|={p[a]}
    a//=p[a]
    s|={a}
  for i in s:c[i]+=1
print(('not','psaeitr'[max(c[2:])>1::2]+'wise')[max(c[2:])<n],'coprime')

Submission status: Accepted

Solution code:
from functools import reduce
from math import gcd, sqrt,ceil


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

a_gcd = reduce(gcd,a)
if a_gcd != 1:
    print("not coprime")
    exit(0)
isset = a_gcd == 1
hurui = [i for i in range(m+1)]
for i in range(2,ceil(sqrt(m))+1):
    for j in range(2,ceil(sqrt(i))+1):
        if i==2:
            continue
        if i%j == 0:
            break
    else:
        for k in range(i+i,m,i):
            if hurui[k] != k:
                continue
            hurui[k] = i
    continue
s = set()
p_f = True
for ai in a:
    t = set()
    while(ai > 1):
        t.add(hurui[ai])
        ai //= hurui[ai]
    for ti in t:
        if ti in s:
            p_f = False
        else:
            s.add(ti)

if p_f:
    print("pairwise coprime")
elif isset:
    print("setwise coprime")

Submission status: Accepted

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

#素数
def primes(n):
    n, correction = n-n%6+6, 2-(n%6>1)
    sieve = [True] * (n//3)
    for i in range(1, int(n**0.5)//3+1):
        if sieve[i]:
            k = 3*i+1|1
            sieve[k*k//3::2*k] = [False] * ((n//6-k*k//6-1)//k+1)
            sieve[k*(k-2*(i&1)+4)//3::2*k] = [False] * ((n//6-k*(k-2*(i&1)+4)//6-1)//k+1)
    return [2, 3] + [3*i+1|1 for i in range(1, n//3-correction) if sieve[i]]

primes=primes(int(1000))
points=[0]*1000001

from math import gcd
pairprime_flag=True
allgcd=A[0]
allprime=set()

for a in A:
    allgcd=gcd(allgcd,a)
    if pairprime_flag:
        for i in primes:
            if a%i==0:
                if points[i]==1:
                    pairprime_flag=False
                points[i]=1
                while a%i==0:
                    a//=i
            if a==1:
                break
        if a!=1:
            if points[a]!=0:
                pairprime_flag=False
            else:
                points[a]=1

if pairprime_flag:
    print('pairwise coprime')
elif allgcd==1:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Accepted

Solution code:
import math

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

A_max = max(A)

D = [i for i in range(1+A_max)]

for i in range(2,1+int(A_max**(1/2))):
    if D[i] == i:
        for j in range(2,1+A_max//i):
            D[i*j] = i

prime = {}

for i in range(2,1+A_max):
    if D[i] == i:
        prime[i] = 0

for a in A:
    X = []
    aa = a
    while aa > 1:
        X.append(D[aa])
        aa //= D[aa]
    
    X = set(X)

    for x in X:
        prime[x] += 1

if all([v<=1 for v in prime.values()]):
    print('pairwise coprime')

else:
    g = A[0]
    for i in range(1,N):
        g = math.gcd(g,A[i])
    if g == 1:
        print('setwise coprime')
    else:
        print('not coprime')

Submission status: Accepted

Solution code:
import sys, math
from functools import lru_cache
import numpy as np
import heapq
from collections import defaultdict
sys.setrecursionlimit(10**9)
MOD = 10**9+7

def input():
    return sys.stdin.readline()[:-1]

def mi():
    return map(int, input().split())

def ii():
    return int(input())

def i2(n):
    tmp = [list(mi()) for i in range(n)]
    return [list(i) for i in zip(*tmp)]

def sieve(n):
    res = [i for i in range(n)]

    i = 2
    while i*i < n:
        if res[i] < i:
            i += 1
            continue
        j = i*i
        while j < n:
            if res[j] == j:
                res[j] = i
            j += i
        i += 1

    return res

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

    return res

def main():
    N = ii()
    A = np.array(list(mi()))

    m = max(A)
    s = sieve(m+1)
    d = defaultdict(bool)
    
    g = np.gcd.reduce(A)
    if g > 1:
        print('not coprime')
        return

    for a in A:
        f = factor(a, s)
        for v in f:
            if d[v]:
                print('setwise coprime')
                return
            d[v] = True

    print('pairwise coprime')



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from math import gcd
from functools import reduce
from collections import defaultdict
n=int(input())
a=list(map(int,input().split()))

if reduce(gcd,a)!=1:
  print("not coprime")
  exit()

def primes(x):
  ret=[]
  for i in range(1,int(x**0.5)+1):
    if x%i==0:
      ret.append(i)
      if x//i!=i:
        ret.append(x//i)
  ret.sort()
  return ret[1:]
      
s=set()
for q in a:
  p=primes(q)
  for j in p:
    if j in s:
      print("setwise coprime")
      exit()
    s.add(j)
print("pairwise coprime")

Submission status: Accepted

Solution code:
from math import gcd
from functools import reduce
from collections import defaultdict
n=int(input())
a=list(map(int,input().split()))

g=reduce(gcd,a)
if g!=1:
  print("not coprime")
  exit()

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
  
def primes(x):
  ret=[]
  for i in range(1,int(x**0.5)+1):
    if x%i==0:
      ret.append(i)
      if x//i!=i:
        ret.append(x//i)
  ret.sort()
  return ret[1:]
      
d=defaultdict(int)
for q in a:
  #p=primeFactor(q)
  p=primes(q)
  for j in p:
    if d[j]==1:
      print("setwise coprime")
      exit()
    d[j]+=1
print("pairwise coprime")

Submission status: Accepted

Solution code:
from math import gcd
from functools import reduce
from collections import defaultdict
n=int(input())
a=list(map(int,input().split()))

g=reduce(gcd,a)
if g!=1:
  print("not coprime")
  exit()

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
#d=defaultdict(int)
s=set()
for q in a:
  p=primeFactor(q)
  for j in p:
    if j in s:
      print("setwise coprime")
      exit()
    s.add(j)
print("pairwise coprime")

Submission status: Accepted

Solution code:
from math import gcd
from functools import reduce
from collections import defaultdict
n=int(input())
a=list(map(int,input().split()))

g=reduce(gcd,a)
if g!=1:
  print("not coprime")
  exit()

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
d=defaultdict(int)
s=set()
for q in a:
  p=primeFactor(q)
  for j in p:
    if d[j]==1:
      print("setwise coprime")
      exit()
    d[j]+=1
print("pairwise coprime")

Submission status: Accepted

Solution code:
from math import gcd
from functools import reduce
from collections import defaultdict
n=int(input())
a=list(map(int,input().split()))

g=reduce(gcd,a)
if g!=1:
  print("not coprime")
  exit()

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
d=defaultdict(int)
for q in a:
  p=primeFactor(q)
  for j in p:
    d[j]+=1

for _,di in d.items():
  if di>=2:
    print("setwise coprime")
    exit()
print("pairwise coprime")

Submission status: Accepted

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


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

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

    if not g == 1:
        print('not coprime')
        return


    limit = int(10 ** 3)
    F = [0] * (10 ** 6 + 1)
    M = [0] * (10 ** 6 + 1)
    for i in range(2, limit + 1):
        if F[i] > 0:
            continue
        v = 2 * i
        while v <= 10 ** 6:
            if F[v] == 0:
                F[v] = i
            v += i

    pc = True
    for v in A:
        S = set()
        x = v
        while True:
            if F[x] > 0:
                S.add(F[x])
                x //= F[x]
            else:
                S.add(x)
                break

        for s in S:
            if s == 1:
                continue
            if M[s] == 1:
                pc = False
                break
            M[s] += 1

        if not pc:
            break

    if pc:
        print('pairwise coprime')
    else:
        print('setwise coprime')


if __name__ == '__main__':
    main()

Submission status: Accepted

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

R = max(A)
prime_factor_counter = [0]*(R+1)

# D[x]にxを割り切れる最初の素数を格納
# 次に行う素因数分解で試し割りのムダを削減するための前準備
D = [0]*(R+1)
for i in range(2, R+1):
    if D[i]:
        continue
    n = i
    while n < R+1:
        if D[n] == 0:
            D[n] = i
        n += i

# 素因数分解し、素因子をカウント
# ex: 12 => 2と3のカウントを+1する
for a in A:
    tmp = a
    while tmp > 1:
        prime_factor = D[tmp]
        prime_factor_counter[prime_factor] += 1
        while tmp%prime_factor == 0:
            tmp //= prime_factor

# 回答出力
if max(prime_factor_counter) < 2:
    print('pairwise coprime')
elif max(prime_factor_counter) - A.count(1) < N:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Accepted

Solution code:
from collections import defaultdict

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

Ones = A.count(1)
R = max(A)
nums = [0]*(R+1)

# 素因数テーブルの作成
D = [0]*(R+1)
for i in range(2, R+1):
    if D[i]:
        continue
    n = i
    while n < R+1:
        if D[n] == 0:
            D[n] = i
        n += i

# 素因子をカウント
for a in A:
    tmp = a
    while tmp > 1:
        prime_factor = D[tmp]
        nums[prime_factor] += 1
        while tmp%prime_factor == 0:
            tmp //= prime_factor
y = max(nums)
if y < 2:
    print('pairwise coprime')
elif y-Ones < N:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Accepted

Solution code:
def li():
    return [int(x) for x in input().split()]

N = int(input())
A = li()

import math
from functools import reduce
from collections import defaultdict

# 最大公約数（リスト引数）
# 空のリストを渡さないよう注意
def GCD_list(numbers):
    return reduce(math.gcd, numbers)



# 数列全ての高速素因数分解
MAX = 10 ** 6
is_prime = [True] * (MAX + 1)
divs = [1] * (MAX + 1)
is_prime[0], is_prime[1] = False, False
i = 1
while i * i <= MAX:
    if not is_prime[i]:
        i += 1
        continue
    for j in range(2 * i, MAX + 1, i):
        is_prime[j] = False
        divs[j] = i
    i += 1

pairwise_coprime = True
all_primes = defaultdict(int)
for k in range(N):
    n = A[k]
    p = divs[n]
    primes = defaultdict(int)
    while p > 1:
        primes[p] += 1
        n = n // p
        p = divs[n]
    # 最後に残った数は1か素数にしかならない
    if n != 1:
        primes[n] += 1
    for key in primes:
        if all_primes[key] > 0 and primes[key] > 0:
            pairwise_coprime = False
            break
        all_primes[key] += primes[key]

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

Submission status: Accepted

Solution code:
import sys, math
input = sys.stdin.readline
n = int(input())
a = [int(x) for x in input().split()]

m = max(a)
primes = list(range(m+1))
primes[1] = 0
for i in range(2, m+1, 2): primes[i] = 2

for i in range(3, int(m ** 0.5)+1):
    for j in range(i, m+1, i):
        if primes[j] > i: primes[j] = i

b = [0] * (m + 1)
jdg_p = True
for aa in a:
    aset = set()
    while aa != 1:
        aset.add(primes[aa])
        aa //= primes[aa]
    for aaset in aset:
        b[aaset] += 1
        if b[aaset] >= 2:
            jdg_p = False
            break
        else:
            b[aaset] += 1
    if not jdg_p: break

x = a[0]
jdg_s = True
for aa in a[1:]:
    x = math.gcd(x, aa)
if x != 1: 
    jdg_s = False

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

Submission status: Accepted

Solution code:
import math
import _collections
n=int(input())
A=list(map(int,input().split()))
ans=A[0]
X=[0]*(max(A)+1)

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



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

if ans!=1:
    print('not coprime')
else:
    ans='pairwise coprime'
    for a in A:
        B=prime_factorize(a)
        for b in B:
            if X[b]!=0:
                ans='setwise coprime'
            else:
                X[b]+=1
    print(ans)

Submission status: Accepted

Solution code:
from math import gcd
def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return set(a)
  
n = int(input())
a = list(map(int, input().split()))
dic = {}
g = a[0]
flg = True
for i in range(n):
  g = gcd(g, a[i])
  if flg:
    tmp = prime_factorize(a[i])
    for j in tmp:
      if j in dic:
        flg = False
      else:
        dic[j]=1
        
if flg:
  print("pairwise coprime")
elif g == 1:
  print("setwise coprime")
else:
  print("not coprime")

Submission status: Accepted

Solution code:
from math import gcd
from functools import reduce
k=10**6+1
def judge(n,a):
  c=[0]*k
  for x in a:
    c[x]+=1 #対応する数の個数を記録
  t=any(sum(c[i::i])>1 for i in range(2,k)) #自身を約数に持つ数が2つ以上与えられたリストに存在するような数が一つでもあるかどうか
  t+=reduce(gcd,a)>1 #全体について1以外の公約数があれば1加える
  return ['pairwise','setwise','not'][t]+' coprime' #全体に公約数があればt=2,全体の公約数が1で公約数持つペアがあればt=1
n=int(input())
a=list(map(int,input().split()))
print(judge(n,a))