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:
n = int(input())
a = list(map(int,input().split()))
p = [0 for _ in range(10**6)]
pr = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997]
#print(pr)
at = 0
for x in a:
  d = int(x)
  for y in pr:
    if d % y == 0:
      if p[y] == 1:
        at = 1
      else:
        p[y] = 1
      while d % y == 0:
        d //= y
  if d != 1:
    if p[d] == 1:
      at = 1
    else:
      p[d] = 1
  if at == 1:
    break
  #print(p)
if at == 0:
  print('pairwise coprime')
  exit()
now = int(a[0])
for x in a:
  big,sml = x,now
  while sml:
    #print(big,sml)
    big,sml = sml,big%sml
  now = big
  if now == 1:
    print('setwise coprime')
    exit()
  #print(now)
print('not coprime')

Submission status: Accepted

Solution code:
import sys; input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**7)
from collections import defaultdict
con = 10 ** 9 + 7; INF = float("inf")

from math import gcd

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

num = 10 ** 6 + 1
L = [1 for i in range(num)]; L[0] = 0; L[1] = 0
plist = []
for i in range(num):
	if L[i] == 1:
		plist.append(i); c = 2
		while i * c <= num - 1:
			L[i * c] = 0; c += 1

#処理内容
def main():
	N = int(input())
	A = getlist()
	GCD = A[0]
	for i in range(N):
		GCD = gcd(GCD, A[i])

	if GCD != 1:
		print("not coprime")
		return

	B = []
	for i in A:
		if i != 1:
			B.append(i)

	B.sort()
	table = [0] * (10 ** 6 + 1)
	for i in B:
		table[i] += 1

	for i in plist:
		val = 0
		c = 1
		while i * c <= 10 ** 6:
			val += table[i * c]
			c += 1		

		if val >= 2:
			print("setwise coprime")
			return

	print("pairwise coprime")


if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
import math,sys,bisect,heapq
from collections import defaultdict,Counter,deque
from itertools import groupby,accumulate
#sys.setrecursionlimit(200000000)
int1 = lambda x: int(x) - 1
input = iter(sys.stdin.buffer.read().decode().splitlines()).__next__
ilele = lambda: map(int,input().split())
alele = lambda: list(map(int, input().split()))
ilelec = lambda: map(int1,input().split())
alelec = lambda: list(map(int1, input().split()))
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
MOD = 1000000000 + 7
def Y(c):  print(["NO","YES"][c])
def y(c):  print(["no","yes"][c])
def Yy(c):  print(["No","Yes"][c])
    
def primeFactors(n): 
	A =set()
	while n % 2 == 0: 
		A.add(2) 
		n = n // 2
	for i in range(3,int(math.sqrt(n))+1,2): 
		while n % i== 0: 
			A.add(i) 
			n = n // i 
	if n > 2: 
		A.add(n) 
	return list(A)


N= int(input())
A = alele()
mark = {}
f1 = 1
f2 = 0
x = None
for i in A:
    if f2 == 0:
        if x == None:
            x=i
        x = math.gcd(x,i)
        if x == 1:
            f2 =1
    if f1 == 1:
        c = primeFactors(i)
        for j in c:
            if mark.get(j,-1) !=-1:
                f1 = 0
                break
            mark[j] = 1
if f1 == 1:
    print("pairwise coprime")
elif f2 == 1:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Accepted

Solution code:
import sys
import numpy as np
from numba import njit,i8,void

@njit(i8(i8,i8),cache=True)
def gcd(x,y):
    while y:
        x,y = y , x % y 
    return x

@njit(i8(i8[:]),cache=True)
def get_gcd(a):
    gcd_all = a[0]
    for i in range(1,a.size):
        gcd_all = gcd(gcd_all,a[i])
    return gcd_all

@njit(i8(i8[:]),cache=True)
def judge_setwise(a):
    amax = a.max()
    aflag = np.zeros(amax,np.int64)
    aflag[a-1] = 1

    for i in range(2,amax+1):
        index = (np.arange(amax//i)+1)*i - 1
        count = aflag[index].sum()
        if count>=2:
            print("setwise coprime")
            return 0
    else:
        print("pairwise coprime")
        return 0

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


if get_gcd(a)>1:
    print("not coprime")
else:
    judge_setwise(a)

Submission status: Accepted

Solution code:
from math import gcd


def eratosthenes(n):
    prime = []
    data = [i + 1 for i in range(1, n)]
    while True:
        p = data[0]
        if n <= p ** 2:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]
    return data


def factorize(N):  # 素因数分解
    for p in prime_list:
        if p * p > N:
            break
        if N % p == 0 and (p in num):
            print('setwise coprime')
            exit()
        while N % p == 0:
            N //= p
            num.add(p)
    if N > 1:
        if N in num:
            print('setwise coprime')
            exit()
        num.add(N)


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()

prime_list = eratosthenes(10 ** 6)
num = set()
for ai in a:
    factorize(ai)
else:
    print('pairwise coprime')

Submission status: Accepted

Solution code:
from math import gcd
N = 1000001
sieve = [-1] * (N + 1)
sieve[0] = sieve[1] = 0
for i in range(N + 1):
    if sieve[i] != -1:
        continue
    else:
        index = i * i
        while True:
            if index > N:
                break
            sieve[index] = i
            index += i

isCounted = [0] * 1000001
isPairwiseCoprime = True
M = int(input())
A = list(map(int,input().split()))
for i in range(M):
    elem = A[i]
    if elem == 1:
        continue
    primeList = []
    while sieve[elem] != -1:
        primeList.append(sieve[elem])
        elem //= sieve[elem]
    primeList.append(elem)
    for elem1 in primeList:
        if isCounted[elem1] != 0:
            isPairwiseCoprime = False
            break
    if not isPairwiseCoprime:
        break
    for elem1 in primeList:
        isCounted[elem1] += 1
if isPairwiseCoprime:
    print("pairwise coprime")
else:
    curGcd = A[0]
    for elem in A:
        curGcd = gcd(elem,curGcd)
    if curGcd == 1:
        print("setwise coprime")
    else:
        print("not coprime")

Submission status: Accepted

Solution code:
from math import gcd
from collections import Counter, defaultdict, deque

(N,) = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]


ACounter = Counter(A)

# has i, j duplicate with gcd not 1
hasPair = any(v > 1 for k, v in ACounter.items() if k != 1)
if not hasPair:
    # check any i j pair has same prime factor
    seenCount = defaultdict(set)

    def sieve(n):
        ret = [-1] * n
        for i in range(2, n):
            if ret[i] == -1:
                for j in range(i, n, i):
                    # each cell is rewritten once for each of its unique prime factors so total cost is O(n loglog n)
                    ret[j] = i
                    if ACounter[j]:
                        seenCount[i].add(j)
        return ret

    sieve(10 ** 6 + 1)

    # print({k: v for k, v in seenCount.items() if v})
    hasPair = any(len(v) > 1 for k, v in seenCount.items())

if hasPair:
    g = 0
    for x in A:
        g = gcd(g, x)
    if g == 1:
        print("setwise coprime")
    else:
        print("not coprime")
else:
    print("pairwise coprime")

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

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

# n = 10**6
# A = [i+1 for i in range(n)]

A.sort()
p_ng = 0
l = 10**6 + 5
B = [0] * l

B[0] = 1
B[1] = 1

for i in range(2, l):
    if B[i] == 0:
        j = 2
        ind = j * i
        while ind < l:
            B[ind] = 1
            j += 1
            ind = j * i

# for i in range(100):
#     print(i, B[i])

C = [0] * l
for i in range(n):
    # print(i, A[i])
    if A[B[i]] == 0:
        if C[B[i]] == 1:
            p_ng = 1
            break
        C[i] = 1
    else:
        a = A[i]
        w = 2
        one = []
        while a != 1:
            f = 1

            while a%w == 0:
                a//=w
                if f == 1 and C[w] == 1:
                    p_ng = 1
                    break
                f = 0
                one.append(w)
            w += 1
            if B[a] == 0:
                if C[a] == 1:
                    p_ng = 1
                    break
                one.append(a)
                break
            # print(a,w)
            if p_ng== 1:
                break
        for ii in one:
            C[ii] = 1
        if p_ng == 1:
            break


# ind = 0
# while ind < n and A[ind] == 1:
#     ind += 1

# if ind < n:
#     for j in range(ind, n):
#         # print(B[:10])
#         for i in range(1, (l-1) // A[j] + 1):
#             indj = i * A[j]
#             # print(indj)
#             if i == 1 and B[indj] == 1:
#                 p_ng = 1
#                 break
#             B[indj] = 1
#         if j > 0 and A[j-1] == A[j]:
#             p_ng = 1
#             break
#         if p_ng == 1:
#             break

if p_ng == 0:
    print("pairwise coprime")
    sys.exit()

from math import gcd
g = A[0]
for i in range(1, n):
    g = gcd(g, A[i])

if g == 1:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Accepted

Solution code:
from bisect import *
from collections import *
from itertools import *
import functools
import sys
import math
from decimal import *
from copy import *
from heapq import *
from fractions import *
getcontext().prec = 30
MAX = sys.maxsize
MAXN = 1000010
MOD = 10**9+7
spf = [i for i in range(MAXN)]
spf[0]=-1
def sieve():
    for i in range(2,MAXN,2):
        spf[i] = 2
    for i in range(3,int(MAXN**0.5)+1):
        if spf[i]==i:
            for j in range(i,MAXN,i):
                if spf[j]==j:
                    spf[j]=i
def fib(n,m):
    if n == 0:
        return [0, 1]
    else:
        a, b = fib(n // 2)
        c = ((a%m) * ((b%m) * 2 - (a%m)))%m
        d = ((a%m) * (a%m))%m + ((b)%m * (b)%m)%m
        if n % 2 == 0:
            return [c, d]
        else:
            return [d, c + d]
 
def charIN(x= ' '):
    return(sys.stdin.readline().strip().split(x))
 
def arrIN(x = ' '):
    return list(map(int,sys.stdin.readline().strip().split(x)))
 
def ncr(n,r):
    num=den=1
    for i in range(r):
        num = (num*(n-i))%MOD
        den = (den*(i+1))%MOD
 
    return (num*(pow(den,MOD-2,MOD)))%MOD
 
def flush():
    return sys.stdout.flush()




'''*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*'''
sieve()



def fun(x,k):
    while x>1:
        d[spf[x]].add(k)
        x//=spf[x]

n = int(input())
a = arrIN()
d = defaultdict(set)

for i in range(n):
    fun(a[i],i)

g = a[0]

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


for i in d.keys():
    if i>1 and len(d[i])>1:
        if g!=1:
            print('not coprime')
        else:
            print('setwise coprime')
        break
else:
    print('pairwise coprime')

Submission status: Accepted

Solution code:
import sys
import io, os
input = sys.stdin.buffer.readline
#input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline

import math
N = 10**6+50

def main():

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

    spf = [-1]*(N+1)
    for i in range(N+1):
        spf[i] = i
    for i in range(2, int(math.sqrt(N))+1):
        if spf[i] == i:
            for j in range(i*2, N+1, i):
                if spf[j] == j:
                    spf[j] = i

    S = [0]*N
    for a in A:
        s = set()
        while a != 1:
            p = spf[a]
            if p not in s:
                S[p] += 1
            s.add(p)
            a //= p
        #print(S[0:10])


    #print(S[0:10])
    flag = False
    for i in range(len(S)):
        if S[i] == n:
            print('not coprime')
            exit()
        elif S[i] >= 2:
            flag = True
        else:
            pass
    if flag:
        print('setwise coprime')
    else:
        print('pairwise coprime')

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math
from functools import reduce


def gcd_list(numbers):
    return reduce(math.gcd, numbers)
  

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

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

gcdl = gcd_list(a)
if gcdl > 1:
    print('not coprime')
    exit()
    
visited = [False] * (10**6 + 10)
for i in a:
    p = prime_factorize(i)
    for j in p:
        if visited[j]:
            print('setwise coprime')
            exit()
    for j in p:
        visited[j] = True
print('pairwise coprime')

Submission status: Accepted

Solution code:
from math import gcd
N=int(input())
A=list(map(int,input().split()))
g=gcd(A[0],A[1])
for i in A:
    g=gcd(g,i)
if g>1:
    print("not coprime")
    exit()
l=[0]*1000001
for i in A:
    l[i]+=1
for i in range(2,1000000):
    c=0
    for j in range(i,1000001,i):
        c+=l[j]
    if c>1:
        print("setwise coprime")
        break
else:
    print("pairwise coprime")

Submission status: Accepted

Solution code:
import math
import functools

def gcd(num : list):
    return functools.reduce(math.gcd, num)

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            while temp%i==0:
                temp //= i
            arr.append(i)

    if temp!=1:
        arr.append(temp)

    if arr==[]:
        arr.append(n)

    return arr

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

    checked_prime = [0] * 1000001

    for a in A:
        if a != 1:
            fac_a = factorization(a)
            for f in fac_a:
                if checked_prime[f] == 0:
                    checked_prime[f] = 1
                else:
                    if gcd(A) == 1:
                        print("setwise coprime")
                        exit()
                    else:
                        print("not coprime")
                        exit()
    print("pairwise coprime")

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from math import *
n = int(input())
a = list(map(int,input().split()))
g = 0
for i in range(n):
    g = gcd(g,a[i])
    
if g == 1:
    x = a.count(1)
    a = list(set(a))
    m = len(a)
    
    sw2 = 0

    if x >= 2:
        if m != n - x + 1:
            sw2 = 1
    else:
        if m != n:
            sw2 = 1
    
    if sw2 == 1:
        print("setwise coprime")
        
    else:
    
        b = [True]*(10**6+1)

        for i in range(m):
            b[a[i]] = False

        sw = 1
        
        for i in range(2, 10**6+1):
            q = 0
            j = 1
            while i*j <= 10**6:
                if b[i*j] == False:
                    q += 1
                j += 1
                
                
            if q >= 2:
                sw = 0
                break

        if sw == 0:
            print("setwise coprime")
        else:
            print("pairwise coprime")
        
else:
    print("not coprime")

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
a = list(map(int, input().split()))
from math import gcd
def hurui(n):
    """n以下の素数のリストを返す
    """
    l = list(range(2,n+1))
    p = 2
    i = 0
    while True:
        l = [item for item in l if item==p or item%p!=0]
        i += 1
        p = l[i]
        if p*p>n:
            break
    return l
b = [0]*(max(a)+1)
done = False
if max(a)>=10:
    l = hurui(max(a)+1)
else:
    l = [2,3,5,7]
for num in a:
    b[num] += 1
for num in l:
    val = sum(b[i] for i in range(num, len(b), num))
    if val>=2:
        g = a[0]
        for i in range(1,n):
            g = gcd(g, a[i])
            if g==1:
                print("setwise coprime")
                done = True
                break
        else:
            print("not coprime")
            done = True
    if done:
        break
else:
    print("pairwise coprime")

Submission status: Accepted

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


N = int(input())
*A, = map(int, input().split())
m = max(A)
c = [0]*(m+1)
for i in range(N):
    c[A[i]] += 1

pc = True
for i in range(2, m):
    k = i
    same = 0
    while k <= m:
        same += c[k]
        k += i
        if same >= 2:
            break
    if same >= 2:
        pc = False
        break

if pc:
    print("pairwise coprime")
else:
    g = gcd(A[0], A[1])
    for i in range(2, N):
        g = gcd(g, A[i])
    if g == 1:
        print("setwise coprime")
    else:
        print("not coprime")

Submission status: Accepted

Solution code:
def factorize(x):
    f = set()
    if x%2==0: f.add(2)
    while x%2==0: x//=2
    
    p = 3
    while x>=p*p:
        if x%p==0: f.add(p)
        while x%p==0: x//=p
        p+=2
    if x>1: f.add(x)
    return f

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

F = [0]*(10**6+5)

for a in A:
    for f in factorize(a):
        F[f] += 1

m = max(F)
if m<=1:
    print('pairwise coprime')
elif m<N:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from math import gcd
from functools import reduce
def input(): return sys.stdin.readline().rstrip()

def pairwaise(bools):
    for i in range(2,10**6):
        hantei=0
        for j in range(i,10**6+1,i):
            hantei+=bools[j]
        if hantei>1:
            return False
    return True


def main():
    n=int(input())
    A=list(map(int, input().split()))
    gcds=reduce(gcd,A)
    if gcds>1:
        print('not coprime')
    else:
        bools=[0]*(10**6+5)
        for AA in A:
            if bools[AA]==1 and AA!=1:
                print('setwise coprime')
                exit()
            bools[AA]+=1
        if pairwaise(bools):
            print('pairwise coprime')
        else:
            print('setwise coprime')

    
    


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys, math
from collections import defaultdict, deque, Counter
from bisect import bisect_left, bisect_right
from itertools import combinations, permutations, product
from heapq import heappush, heappop
from functools import lru_cache
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mat = lambda x, y, v: [[v]*y for _ in range(x)]
ten = lambda x, y, z, v: [mat(y, z, v) for _ in range(x)]
mod = 1000000007
sys.setrecursionlimit(1000000)

from fractions import gcd
from functools import reduce

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

def get_gcd(A):
	return reduce(gcd, A)

def get_lcm(A):
	def lcm_base(a, b):
		return a*b//gcd(a,b)
	return reduce(lcm_base , A, 1)


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

N = ri()
A = rl()

pc = True

h = set()
for a in A:
	ps = get_primes(a)
	for p in ps:
		if p in h:
			pc = False
			break
		h.add(p)
	if pc == False: break

if pc:
	print('pairwise coprime')
	exit()

sc = (get_gcd(A) == 1)
if sc:
	print('setwise coprime')
else:
	print('not coprime')

Submission status: Accepted

Solution code:
from math import gcd
def prime_table(n):
    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
    return [i for i in range(n + 1) if is_prime[i]]

N = int(input())
A = list(map(int,input().split()))
g = A[0]
for i in range(1,N):
    g = gcd(g,A[i])
    if g == 1:
        break
if g != 1:
    print('not coprime')
else:
    PT = prime_table(10**6+1)
    l = len(PT)
    flag = set()
    for j in range(N):
        n = A[j]
        for i in range(l):
            p = PT[i]
            if n % p == 0:
                while n % p == 0:
                    n //= p
                if p in flag:
                    print('setwise coprime')
                    exit()
                else:
                    flag.add(p)
            if p*p > n:
                if n in flag and n != 1:
                    print('setwise coprime')
                    exit()
                else:
                    if n != 1:
                        flag.add(n)
                break
    print('pairwise coprime')

Submission status: Accepted

Solution code:
from math import sqrt, gcd
def factoring(k): #kを因数分解し、素因数とその個数を辞書に入れて返す。
    dic = dict()
    n = int(sqrt(k))+2
    for i in range(2, n):
        count = 0
        while k%i == 0:
            count += 1
            k = k//i
        if count != 0:
            dic[i] = count
    if k != 1: #sqrt(k)までチェックしてもkが1になっていない --> kが素因数
        dic[k] = 1
    return dic

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

from collections import defaultdict
from bisect import bisect_left

n = bisect_left(A, 1.5) # 1の数

dic = defaultdict(int)

if N <= 10 ** 5 + n:
    count = 0
    for a in A[max(0, n - 1):]:
        tmp = factoring(a)
        for i in tmp:
            dic[i] = max(tmp[i], dic[i])
            count += tmp[i]

    tmp = 0
    for i in dic:
        tmp += dic[i]

    if count == tmp:
        print ('pairwise coprime')
        exit()

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

if GCD == 1:
    print ('setwise coprime')
else:
    print ('not coprime')

Submission status: Accepted

Solution code:
from math import gcd
from functools import reduce


def pairwise_coprime(a):
    check = [set() for _ in range(10 ** 6 + 10)]
    for i, aa in enumerate(a):
        now = aa
        while now % 2 == 0:
            if len(check[2]) > 0 and i not in check[2]:
                return False
            now //= 2
            check[2].add(i)
        f = 3
        while f * f <= now:
            if now % f == 0:
                if len(check[f]) > 0 and i not in check[f]:
                    return False
                now //= f
                check[f].add(i)
            else:
                f += 2
        if now != 1:
            if len(check[now]) > 0 and i not in check[now]:
                return False
            check[now].add(i)
    return True


def main():
    n = int(input())
    a = list(map(int, input().split()))
    if pairwise_coprime(a):
        print("pairwise coprime")
    elif reduce(gcd, a) == 1:
        print("setwise coprime")
    else:
        print("not coprime")


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict
from functools import reduce
input = lambda: sys.stdin.readline().rstrip()

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

def prime_factorize(n):
    # Return list of prime factorized result
    # O(sqrt(n))
    a = set()
    while n % 2 == 0:
        a.add(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.add(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.add(n)
    return a

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

d = defaultdict(lambda: 0)
f = True
for v in a:
    factors = prime_factorize(v)
    for f in factors:
        if d[f] > 0:
            f = False
            break
        d[f] += 1
    if not f:
        break
if f:
    case = 1

if case != 1:
    g = a[0]
    for v in a[1:]:
        g = gcd(g, v)
    if g == 1:
        case = 2

if case == 1:
    print("pairwise coprime")
elif case == 2:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7) #再帰関数の上限,10**5以上の場合python
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque, defaultdict
#deque(l), pop(), append(x), popleft(), appendleft(x)
#q.rotate(n)で → にn回ローテート
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate,combinations,permutations,product#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
from functools import reduce,lru_cache#pypyでもうごく
#@lru_cache(maxsize = None)#maxsizeは保存するデータ数の最大値、2**nが最も高効率
from decimal import Decimal
from argparse import ArgumentParser

args=ArgumentParser()
args.add_argument('-loc', '--local', type=bool,default=False)
LOCAL=args.parse_args().local

def input(): 
    x=sys.stdin.readline(); 
    if x[-1]=="\n": 
        return x.rstrip() 
    return x
    
def printe(*x):_=print("## ",*x,file=sys.stderr) if LOCAL else 0
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def binr(x): return bin(x)[2:]
def bitcount(x): #xは64bit整数
    x= x - ((x >> 1) & 0x5555555555555555)
    x= (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x= (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f 
    x+= (x >> 8); x+= (x >> 16); x+= (x >> 32) 
    return x & 0x7f

def main():
    mod = 1000000007
    #w.sort(key=itemgetter(1),reverse=True)  #二個目の要素で降順並び替え

    N = int(input())
    #N, K = map(int, input().split())
    A = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列
    tot=0
    def primes(n):
        a = set()
        while n % 2 == 0:
            a.add(2)
            n //= 2
        f = 3
        while f * f <= n:
            if n % f == 0:
                a.add(f)
                n //= f
            else:
                f += 2
        if n != 1:
            a.add(n)
        return a

    for a in A:
        tot=math.gcd(tot,a)
    if tot!=1:
        print("not coprime")
        return
    tN=N
    for a in A:
        if a==1:
            tN-=1
            
    if tN>78498:
        print("setwise coprime")
        return 

    cur=set()
    for a in A:
        s=primes(a)
        if len(s&cur)!=0:
            print("setwise coprime")
            return 
        cur|=s

    print("pairwise coprime")


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import math
import time

start=time.time()

N=int(input())
ls=[int(s) for s in input().split()]
M=max(ls)
SQRT_M=int(math.sqrt(M))+1
#素数のリスト作成
prime=[1 for i in range(SQRT_M+1)]
prime[0]=0
prime[1]=0
primels=[]
primedic={}
for i in range(2,SQRT_M+1):
  if prime[i]==1:
    primels.append(i)
    primedic[i]=0
    a=1
    while a*i<=SQRT_M:
      prime[a*i]=0
      a+=1

for e in ls:
  for p in primels:
    if e%p==0:
      primedic[p]+=1
      while e%p==0:
        e//=p
    if e==1:
      break
  else:
    if e in primedic:
      primedic[e]+=1
    else:
      primedic[e]=1
  if time.time()-start>1.9:
    break
    

A=max(primedic.values())

if A==len(ls):
  print('not coprime')
elif A>1:
  print('setwise coprime')
else:
  print('pairwise coprime')