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 sys
input = sys.stdin.readline

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

# from Kiri8128
# https://qiita.com/Kiri8128/items/eca965fe86ea5f4cbb98#%E7%B4%A0%E5%9B%A0%E6%95%B0%E5%88%86%E8%A7%A3%E3%82%92-on14-%E3%81%A7%E3%81%99%E3%82%8B

def gcd(a, b):
    while b: a, b = b, a % b
    return a
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


GCD=A[0]
for a in A:
    GCD=gcd(GCD,a)

if GCD!=1:
    print("not coprime")
    sys.exit()

SET=set()
for a in A:
    S=set(primeFactor(a))
    #print(S,SET)

    if SET & S !=set():
        print("setwise coprime")
        sys.exit()
    SET|=S

print("pairwise coprime")

Submission status: Accepted

Solution code:
from math import gcd

n = int(input())


def p(x):
    a = []
    i = 2
    while True:
        if x % i == 0:
            j = 0
            while x % i == 0:
                x //= i
                j += 1
            a.append((i, j))
        if i * i > x:
            break
        i += 1
    if x != 1:
        a.append((x, 1))
    return a


pp = set()
a = [int(i) for i in input().split()]

j = 0
for i in a:
    j = gcd(j, i)
ok1 = j == 1

ok2 = True
for i in a:
    for (j, _) in p(i):
        if j in pp:
            ok2 = False
        else:
            pp.add(j)
    if not ok2:
        break
if ok2:
    print("pairwise coprime")
else:
    if ok1:
        print("setwise coprime")
    else:
        print("not coprime")

Submission status: Accepted

Solution code:
import collections

def cin():  return list(map(int,input().split()))

N = cin()[0]
A = cin()

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

def gcd(l):
    ans = l[0]
    for i in l:  ans = gcd_(ans, i)
    return ans

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 a

flg = 0

s = [0 for _ in range(10 ** 6 + 5)]
for i in range(N):
    res = collections.Counter(prime_factorize(A[i])) # Counter({2: 4, 3: 1})
    keys = list(res.keys()) # [2, 3]
    length = len(keys)
    
    for i in range(length):
        num = keys[i] # 因数
        if s[num] == 1:
            flg = 1
            break
        s[num] += 1
        
if flg == 0:
    print("pairwise coprime")
else:
    if gcd(A) == 1:  print("setwise coprime")
    else:  print("not coprime")

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N = int(input())
As = list(mapint())
As.sort()

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 a

pairwise = True
s = set()
maxi = As[-1]
for i in range(N):
    a = As[i]
    if a in s:
        pairwise = False
        break
    if a==1:
        continue
    primes = list(set(prime_factorize(a)))
    for p in primes:
        cnt = 1
        while cnt*p<=maxi:
            s.add(cnt*p)
            cnt += 1
else:
    print('pairwise coprime')
    exit()

from math import gcd
g = 0
for a in As:
    g = gcd(g, a)
if g==1:
    print('setwise coprime')
    exit()
else:
    print('not coprime')

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
#mod = 998244353
INF = 10**18
eps = 10**-7


def gcd(a,b):
    while b:
        a,b = b,a%b
    return a


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

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

n = int(readline())
a = list(map(int,readline().split()))
a.sort()
check = [True]*(10**6+5)
p1 = True
for ai in a:
    if not p1:
        break
    dlist = fctr1(ai)
    for d,c in dlist:
        if check[d]:
            check[d] = False
        else:
            p1 = False
            break

if p1:
    print("pairwise coprime")
else:
    p2 = gcdlist(a)
    if p2 == 1:
        print("setwise coprime")
    else:
        print("not coprime")

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.buffer.readline
n = int(input())
A = list(map(int, input().split()))


# from kiriさん
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a


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


scflag = 0
g = A[0]
nums = set()
for i in range(n):
    g = gcd(g, A[i])
    temp = primeFactor(A[i])
    for a in temp.keys():
        # print(a)
        if a == 1:
            continue
        if a in nums:
            scflag = 1
        else:
            nums.add(a)
if g != 1:
    print("not coprime")
elif scflag:
    print("setwise coprime")
else:
    print("pairwise coprime")

Submission status: Accepted

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

U = 10**6+1
is_prime = [1]*U
is_prime[0] = 0
is_prime[1] = 0
for p in range(2, int(U**.5)+1):
    if is_prime[p]:
        for q in range(2*p, U, p):
            is_prime[q] = 0


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


min_factor = sieve(U)


def prime_factor(n):
    res = defaultdict(int)
    while 1 < n:
        res[min_factor[n]] += 1
        n //= min_factor[n]
    return res


for a in A:
    for k, v in prime_factor(a).items():
        if 1 <= is_prime[k]:
            is_prime[k] = 0
            continue
        ans = 1
        break
    else:
        continue
    break

if ans == 0:
    print('pairwise coprime')
else:
    if reduce(gcd, A) == 1:
        print('setwise coprime')
    else:
        print('not coprime')

Submission status: Accepted

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

primes = []
prime_idx = {}
furui = [-1]*(10**6+10)
furui[0] = 0
furui[1] = 1
for i in range(2,10**6 + 10):
    if furui[i] == -1:
        prime_idx[i] = len(primes)
        primes.append(i)
        x = i
        while x < 10**6 + 10:
            furui[x] = i
            x += i

appered = [0]*len(primes)
for a in A:
    x = a
    has = set()
    while x>1:
        has.add(prime_idx[furui[x]])
        x //= furui[x]
    for prime in has:
        appered[prime] += 1
flag = 0
for ap in appered:
    if ap > 1:
        flag = max(flag, 1)
    if ap == n:
        flag = max(flag, 2)
if flag == 2:
    print("not coprime")
elif flag == 1:
    print("setwise coprime")
else:
    print("pairwise coprime")

Submission status: Accepted

Solution code:
def gcd(x, y):
    while y:
        x, y = y, x % y
    return x

def sieve(n):
    res = [True for _ in range(n + 1)]
    res[0] = False
    res[1] = False
    i = 2
    while i * i <= n:
        if res[i]:
            for j in range(i * 2, n + 1, i):
                res[j] = False
        i += 1
    return res

def factorize(n):
    if n == 1: return []
    res = []
    x, y = n, 2
    while y * y <= x:
        while x % y == 0:
            res.append(y)
            x //= y
        y += 1
    if x > 1:
        res.append(x)
    return res

from collections import Counter, defaultdict

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

S = sieve(10**6 + 1)

flag = True

for i in range(N):
    if S[A[i]]:
        S[A[i]] = 0
    else:
        F = set(factorize(A[i]))
        for f in F:
            if S[f]:
                S[f] = 0
            else:
                flag = False
                break
        else:
            continue
        break

if flag:
    print('pairwise coprime')

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

Submission status: Accepted

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    if len(x) == 0:
        return []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

def pow_k(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans

"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""

import math
from functools import reduce
def gcd(*numbers):
    return reduce(math.gcd, numbers)

def gcd_list(numbers):
    return reduce(math.gcd, numbers)
def lcm_base(x, y):
    return (x * y) // math.gcd(x, y)

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)



def make_primes(n): #nまでの素数列挙
    ass = []
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    for i in range(len(is_prime)):
        if is_prime[i]:
            ass.append(i)
    return ass  


def prime_decomposition(n): #素因数分解
  i = 2
  table = []
  while i * i <= n:
    while n % i == 0:
      n /= i
      table.append(i)
    i += 1
  if n > 1:
    table.append(int(n))
  return table

def make_divisors(n): #約数列挙
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

data = make_primes(10**6+1)

ppp = cl.defaultdict(int)

for i in range(len(data)):
    ppp[data[i]] = 1
n = onem()

a = l()

data = gcd_list(a)

if data != 1:
    print("not coprime")

else:
    a.sort()
    for i in range(n):
        po = prime_decomposition(a[i])
        po = s(po)
        fl = 0
        for j in range(len(po)):
            if po[j][0] == 1:
                continue
            if ppp[po[j][0]] == 1:
                ppp[po[j][0]] = 2
            else:
                fl = 1
        if fl:
            print("setwise coprime")
            break
    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:
  p = t
  cnt = 0
  while p<=Amax:
    cnt += lis[p]
    p += 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 math as mt 
  
MAXN = 1000001
  
# stores smallest prime factor for 
# every number 
spf = [0 for i in range(MAXN)] 
  
# Calculating SPF (Smallest Prime Factor)  
# for every number till MAXN. 
# Time Complexity : O(nloglogn) 
def sieve(): 
    spf[1] = 1
    for i in range(2, MAXN): 
          
        # marking smallest prime factor  
        # for every number to be itself. 
        spf[i] = i 
  
    # separately marking spf for  
    # every even number as 2 
    for i in range(4, MAXN, 2): 
        spf[i] = 2
  
    for i in range(3, int(mt.ceil(mt.sqrt(MAXN)))): 
          
        # checking if i is prime 
        if (spf[i] == i): 
              
            # marking SPF for all numbers 
            # divisible by i 
            for j in range(i * i, MAXN, i):  
                  
                # marking spf[j] if it is  
                # not previously marked 
                if (spf[j] == j): 
                    spf[j] = i 
  
# A O(log n) function returning prime  
# factorization by dividing by smallest  
# prime factor at every step 
def getFactorization(x): 
    d1={}
    while (x != 1): 
        d1[spf[x]]=0
        x = x // spf[x] 
  
    return d1.keys()
def gcd(a,b):
    while b:
        a,b=b,a%b
    return a
# Driver code 
  
# precalculating Smallest Prime Factor 
sieve()
n=int(input())
d={}
flag=1;val=-1
a=[int(i) for i in raw_input().split()]
for i in range(n):
    x=a[i]
    if val==-1:
        val=x
    val=gcd(val,x)
    ret=getFactorization(x)
    for j in ret:
        d[j]=d.get(j,0)+1
for i in d.keys():
    if i!=1 and d[i]>1:
        flag=0
if val!=1:
    print("not coprime")
elif flag:
    print("pairwise coprime")
else:
    print("setwise coprime")

Submission status: Accepted

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


def union_gcd(lists):
    if len(lists) == 1:
        return lists[0]
    elif len(lists) > 1:
        num = lists[0]
        for i in range(1, len(lists)):
            num = math.gcd(num, lists[i])
        return num


def prime_to(n):
    prime = {i for i in range(2, n)}
    for i in range(2, n):
        if i in prime:
            for j in range(i*2, n, i):
                if j in prime:
                    prime.remove(j)
    return prime


is_pair_wise = True
is_all_gcd_1 = False

if union_gcd(A) == 1:
    is_all_gcd_1 = True

Num = [0 for i in range(10**6+1)]
for x in A:
    Num[x] += 1

seen = [False for i in range(10**6+1)]
A.sort()
primes = prime_to(10**6)
for num in primes:
    if seen[num] == False:
        seen[num] = True
        cnt = 0
        for i in range(1, 10**6+1):
            if num*i > 10**6:
                break
            else:
                cnt += Num[num*i]
        if cnt > 1:
            is_pair_wise = False
            break
if is_pair_wise:
    print("pairwise coprime")
else:
    if is_all_gcd_1:
        print("setwise coprime")
    else:
        print("not coprime")

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import collections
import sys
input=sys.stdin.readline

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

def judge(n,arr):
    MAX=10**6
    table=[i for i in range(MAX+1)]
    for i in range(2,MAX+1):
        if table[i]<i:
            continue
        for j in range(i,MAX+1,i):
            table[j]=i
    cnt=collections.defaultdict(int)
    for val in arr:
        s=set()
        while val!=1:
            prime=table[val]
            s.add(prime)
            val//=prime
        for tmp in s:
            cnt[tmp]+=1
    for val in cnt.values():
        if val>=2:
            return False
    return True
    
n=int(input())
arr=list(map(int,input().split()))
tmp=arr[0]
for val in arr:
    tmp=gcd(tmp,val)
if tmp==1:
    is_setwise=True
else:
    is_setwise=False
is_pairwise=judge(n,arr)
if is_pairwise==True:
    print('pairwise coprime')
elif is_setwise==True:
    print('setwise coprime')
else:
    print('not coprime')