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: Wrong Answer

Solution code:
from functools import reduce
from math import gcd

def sieve(L,R):
    if L<2:L=2
    flag=[0]*(2*R)
    for i in range(2, int(R**.5)+5):
        if flag[i] == 1:continue
        for j in range(i*2,R+i, i):
            if flag[j] == 1:continue
            if j % i == 0:
                flag[j] = 1
    
    return [i for i in range(L,R+1) if flag[i] == 0]
  
N=int(input())
*A,=map(int,input().split())

if N == 2:
  if gcd(A[0],A[1])==1:
    print('pairwise coprime')
  else:
    print('not coprime')
  exit()

primes = sieve(2,10**3+5)
num = [0]*(10**6+10**3+5)
for i in range(N):
  num[A[i]] += 1

flag=0
for p in primes:
  count=0
  for d in range(p,10**6+p+5,p):
    count += num[d]
  if count > 1:
    flag=1
    break
  
if flag==0:
  print('pairwise coprime')
elif reduce(gcd,A)==1:
  print('setwise coprime')
else:
  print('not coprime')

Submission status: Wrong Answer

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

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

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

n=int(input())
arr=list(map(int,input().split()))
cnt=collections.defaultdict(int)
tmp=arr[0]
for val in arr:
  tmp=gcd(tmp,val)
if tmp==1:
  is_setwise=True
else:
  is_setwise=False
is_pairwise=True
for val in arr:
  divisor=divisors(val)
  for val2 in divisor:
    cnt[val]+=1
    if cnt[val]==2:
      is_pairwise=False
      break
if is_pairwise==True:
  print('pairwise coprime')
elif is_setwise==True:
  print('setwise coprime')
else:
  print('not coprime')

Submission status: Wrong Answer

Solution code:
import math
n=int(input())
a=list(map(int,input().split()))
ma=max(a)
sa=set(a)
ans=[]
era=[1]*(10**6+1)
era[0]=0

k=2
while k<(10**6+1)**0.5+1:
  if era[k]==1:
    
    for i in range(k,10**6+1,k):
      if i!=k:
        era[i]=0
      if i in sa:
        ans.append(k)
  if k==2:
    k+=1
  else:
    k+=2
    
pflag=True
if len(ans)!=len(set(ans)):
  pflag=False

if pflag == False:
  setwise=a[0]
  for i in range(1,n):
    setwise=math.gcd(setwise,a[i])
  if setwise == 1:
    print("setwise coprime")
  else:
    print("not coprime")
else:
  print('pairwise coprime')

Submission status: Wrong Answer

Solution code:
from collections import Counter


def factorize(num):
    array = []
    tmp = num
    now = 2
    while now ** 2 <= num:
        if tmp % now == 0:
            while tmp % now == 0:
                tmp //= now
            array.append(now)
        now += 1
    if tmp != 1:
        array.append(tmp)
    if len(array) == 0:
        array.append(num)
    return array


N = int(input())
A = list(map(int, input().split()))
all_list = []
set_diff = set()
for i in A:
    fac = factorize(i)
    set_diff = set_diff ^ set(fac)
    all_list.extend(fac)
# print(Counter(all_list))
if Counter(all_list).most_common()[0][1] == 1:
    print("pairwise coprime")
elif len(set_diff) == 0:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Wrong Answer

Solution code:
from fractions import gcd
N = int(input())
A = list(map(int, input().split()))
C = [0 for i in range(10 ** 6)]
for a in A:
  C[a-1] = 1
pairwise = True
for i in range(2, 10 ** 6):
  count = 0
  for j in range(i, 10 ** 6, i):
    count += C[j-1]
  if count > 1:
    pairwise = False
if pairwise:
  print("pairwise coprime")
else:
  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: Wrong Answer

Solution code:
import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
from collections import defaultdict
def main():
    n, *a = map(int, read().split())
    from math import sqrt
    from math import ceil
    maxa = max(a)  # maxa＝「素数判定したい数字のうち最大の数字」
    maxa2 = ceil(sqrt(maxa))
    maxa2 = max(6, maxa2)  # maxa2が6未満だとエラーになる
    p = [False if i % 2 == 0 or i % 3 == 0 or i % 5 == 0 else True for i in range(maxa2)]
    p[0] = p[1] = False
    p[2] = p[3] = p[5] = True
    for is1 in range(3, maxa2, 2):
        for is2 in range(is1 ** 2, maxa2, is1):
            p[is2] = False
    prime_list = [i for i, b in enumerate(p) if b]

    d1 = defaultdict(int)
    for pn in prime_list:
        d1[pn] = sum([ae % pn == 0 for ae in a])
    d1v = d1.values()
    if max(d1v) == n:
        print('not coprime')
    elif all([i == 1 for i in d1v]):
        print('pairwise coprime')
    else:
        print('setwise coprime')

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from functools import reduce
from math import gcd

def sieve(L,R):
    if L<2:L=2
    flag=[0]*(R+1)
    for i in range(2, int(R**.5)+5):
        if flag[i] == 1:continue
        for j in range(i*2,R+1, i):
            if flag[j] == 1:continue
            if j % i == 0:
                flag[j] = 1
    
    return [i for i in range(L,R+1) if flag[i] == 0]
  
N=int(input())
*A,=map(int,input().split())

if N == 2:
  if gcd(A[0],A[1])==1:
    print('pairwise coprime')
  else:
    print('not coprime')
  exit()

primes = sieve(2,10**3+5)
num = [0]*(10**6+10**3+5)
for i in range(N):
  num[A[i]] += 1

flag=0
for p in primes:
  count=0
  for d in range(p,10**6+p+5,p):
    count += num[d]
  if count > 1:
    flag=1
    break
  
if flag==0:
  print('pairwise coprime')
elif reduce(gcd,A)==1:
  print('setwise coprime')
else:
  print('not coprime')

Submission status: Wrong Answer

Solution code:
import numpy as np
from numba import njit


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


n = 10**5 + 1
primes = set(range(3, n+1, 2))

for i in range(3, int(n**0.5+1)):
    primes.difference_update(range(i*2, n+1, i))
primes.add(2)


@njit
def solve(arr, primes):
    cnt = np.bincount(arr)
    for p in primes:
        if (cnt[p::p]).sum() > 1:
            return False
    else:
        return True


if np.gcd.reduce(arr) != 1:
    print("not coprime")
elif solve(arr, primes):
    print("pairwise coprime")
else:
    print("setwise coprime")

Submission status: Wrong Answer

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

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

isPairwise=True
isSetwise=True
for i in range(N):
    c[A[i]]+=1

for i in range(2,1000005):
    cnt=0
    for j in range(2,1000005,i):
        cnt+=c[j]
    
    if cnt>1:
        isPairwise=False

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

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

if isPairwise:
    print('pairwise coprime')
elif isSetwise:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Wrong Answer

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)

N = ri()
A = rl()

h = defaultdict(int)
for a in A:
	h[a] = 1

M = 10**6+5
c = 0
pc = True
for i in range(2, M):
	c = 0
	for j in range(i, M, i):
		c += h[j]
	if c > 1:
		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: Wrong Answer

Solution code:
import math
n=int(input())
a=list(map(int,input().split()))
ma=max(a)
sa=set(a)
ans=[]
k=2
while k<(10**6+1)**0.5+1:
  for i in range(k,10**6+1,k):
    if i in sa:
      ans.append(k)
  if k==2:
    k+=1
  else:
    k+=2
pflag=True

if len(ans)!=len(set(ans)):
  pflag=False

if pflag == False:
  setwise=a[0]
  for i in range(1,n):
    setwise=math.gcd(setwise,a[i])
  if setwise == 1:
    print("setwise coprime")
  else:
    print("not coprime")
else:
  print('pairwise coprime')

Submission status: Wrong Answer

Solution code:
import numpy as np
from numba import njit


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


n = 10**3
primes = set(range(3, n+1, 2))

for i in range(3, int(n**0.5+1)):
    primes.difference_update(range(i*2, n+1, i))
primes.add(2)


@njit
def solve(arr, primes):
    cnt = np.bincount(arr)
    for p in primes:
        if (cnt[p::p]).sum() > 1:
            return False
    else:
        return True


if np.gcd.reduce(arr) != 1:
    print("not coprime")
elif solve(arr, primes):
    print("pairwise coprime")
else:
    print("setwise coprime")

Submission status: Wrong Answer

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

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

isPairwise=True
isSetwise=True
for i in range(N):
    c[A[i]]+=1

for i in range(2,1000000):
    cnt=0
    for j in range(2,1000000,i):
        cnt+=c[j]
    
    if cnt>1:
        isPairwise=False

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

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

if isPairwise:
    print('pairwise coprime')
elif isSetwise:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Wrong Answer

Solution code:
import math 
from functools import reduce
N = int(input())
A = list(map(int, input().split()))
ans = ["pairwise coprime", "setwise coprime ", "not coprime"]

def gcd_list(numbers):
    return reduce(math.gcd, numbers)
  
if gcd_list(A) != 1:
  print(ans[2])
  quit()
  
def seachPrimeNum(N):
    max = int(N ** (1 / 2))
    D = [0] * N
    D[0] = 1
    seachList = [i for i in range(2,N+1)]
    primeNum = []
    while seachList[0] <= max:
        nn = seachList[0]
        D[nn - 1] = nn
        primeNum.append(nn)
        tmp = nn
        for i in seachList:
          if i != nn:
            if i % tmp == 0:
              D[i - 1] = nn
        seachList = [i for i in seachList if i % tmp != 0]
    for i in seachList:
      D[i - 1] = i
    primeNum.extend(seachList)
    
    return primeNum, D  
  
primeNum, D = seachPrimeNum(1000000)
used = [0] * len(primeNum)

for i in range(N):
  now = A[i]
  if now == 1:
    continue
  q = []
  #print(now, D[now - 1])
  while now != D[now - 1]:
    now = int(now / D[now - 1])
    if now in primeNum:
      q.append(now)
  q.append(now)      
  for i in q:
    if used[primeNum.index(i)] == 0:
      used[primeNum.index(i)] = 1
    else:
      print(ans[1])
      quit()  

print(ans[0])

Submission status: Wrong Answer

Solution code:
from functools import reduce
from math import gcd

def sieve(L,R):
    if L<2:L=2
    flag=[0]*(R+1)
    for i in range(2, int(R**.5)+5):
        if flag[i] == 1:continue
        for j in range(i*2,R+1, i):
            if flag[j] == 1:continue
            if j % i == 0:
                flag[j] = 1
    
    return [i for i in range(L,R+1) if flag[i] == 0]
  
N=int(input())
*A,=map(int,input().split())

primes = sieve(2,10**3+5)
num = [0]*(10**6+10**3+5)
for i in range(N):
  num[A[i]] += 1

flag=0
for p in primes:
  count=0
  for d in range(p,10**6+p+5,p):
    count += num[d]
  if count > 1:
    flag=1
    break
  
if flag==0:
  print('pairwise coprime')
elif reduce(gcd,A)==1:
  print('setwise coprime')
else:
  print('not coprime')

Submission status: Wrong Answer

Solution code:
import math
n=int(input())
a=list(map(int,input().split()))
ma=max(a)
sa=set(a)
ans=[]
k=2
while k<(10**6+1)**0.5+1:
  for i in range(2*k,10**6+1,k):
    if i in sa:
      ans.append(k)
  if k==2:
    k+=1
  else:
    k+=2
pflag=True
if len(ans)!=len(set(ans)):
  pflag=False

if pflag == False:
  setwise=a[0]
  for i in range(1,n):
    setwise=math.gcd(setwise,a[i])
  if setwise == 1:
    print("setwise coprime")
  else:
    print("not coprime")
else:
  print('pairwise coprime')

Submission status: Wrong Answer

Solution code:
import numpy as np
n=int(input())
a=list(map(int, input().split()))

c=[0]*max(a)

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

for i in range(n):
    tmp = factorization(a[i])
    for k in tmp:
        c[k[0]-1]+=1
    #print(tmp)

#print(c)   
maxcount=max(c)

if np.gcd.reduce(a) != 1:
    print('not coprime')
elif maxcount <= 1:
    print('pairwise coprime')
else:
    print('setwise coprime')

Submission status: Wrong Answer

Solution code:
import sys
import math

def prime(n):
    D = [i for i in range(n+1)]
    for i in range(2, n+1):
        if i != D[i]:
            break
        j = 2
        while j * i <= n:
            if D[j * i] == j * i:
                D[j * i] = D[i]
            j += 1
    return D

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

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

m = max(A)
if m == 1:
    print('pairwise coprime')
    sys.exit()

D = prime(m)

dic = {}

for i in range(n):
    if D[A[i]] not in dic:
        dic[D[A[i]]] = 1
    else:
        dic[D[A[i]]] += 1
#print(dic)
if n == len(dic) and (1 not in dic):
    print('pairwise coprime')
elif prime2(A) == 1:
    print('setwise coprime')
else:
    #print(prime2(A))
    print('not coprime')

Submission status: Wrong Answer

Solution code:
import sys
import math

def prime(n):
    D = [i for i in range(n+1)]
    for i in range(2, n+1):
        if i != D[i]:
            break
        j = 2
        while j * i <= n:
            if D[j * i] == j * i:
                D[j * i] = D[i]
            j += 1
    return D

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

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

m = max(A)
if m == 1:
    print('pairwise coprime')
    sys.exit()

D = prime(m)

dic = {}

for i in range(n):
    if D[A[i]] not in dic:
        dic[D[A[i]]] = 1
    else:
        dic[D[A[i]]] += 1
#print(dic)
if n == len(dic):
    print('pairwise coprime')
elif prime2(A) == 1:
    print('setwise coprime')
else:
    #print(prime2(A))
    print('not coprime')

Submission status: Wrong Answer

Solution code:
import numpy as np
from numba import njit


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


n = 10**3
primes = set(range(3, n+1, 2))

for i in range(3, int(n**0.5+1)):
    primes.difference_update(range(i*2, n+1, i))
primes.add(2)


@njit
def solve(arr, primes):
    used = [False] * 1000
    ans = True
    for x in arr:
        for p in primes:
            while x % p == 0:
                if used[p]:
                    ans = False
                    return ans
                while x % p == 0:
                    x //= p
                used[p] = True
    return ans


if np.gcd.reduce(arr) != 1:
    print("not coprime")
elif solve(arr, primes):
    print("pairwise coprime")
else:
    print("setwise coprime")

Submission status: Wrong Answer

Solution code:
INF=10**9+7
D = [INF]*(10**6+1)
L = [True]*(10**6+1)
L[0] = False
L[1] = False
D[1] = 1
for i in range(2, 10**6+1):
    if L[i]:
        D[i] = i
        for j in range(i*2, 10**6+1, i):
            L[j] = False
            D[j] = min(i, D[j])


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


def factorization(n):
    if n == 1:
        return {1}
    ans = set()
    ans.add(D[n])
    factorization(n//D[n])
    return ans


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

s = set(factorization(A[0])-{1})
for i in range(1, N):
    tmp = factorization(A[i])-{1}
    if tmp & s != set():
        break
    s |= tmp
else:
    print('pairwise coprime')
    exit()

L1 = A
while len(L1) > 1:
    l = len(L1)//2
    k = [0]*l
    for i in range(l):
        k[i] = egcd(L1[2*i], L1[2*i+1])
    if len(L1) % 2 == 1:
        k.append(L1[-1])
    L1 = k

if L1[0] == 1:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Wrong Answer

Solution code:
import math
from functools import reduce
n=int(input())
a=list(map(int, input().split()))
q=0
size=10**6
m=max(a)

judge=[0]*m #最小素因数の前計算
judge[0]=1
for i in range(2,m+1):
    for j in range(1,int(i**0.5)+1):
        if j==1:
            continue
        if i%j==0:
            judge[i-1]=j
            break
    if judge[i-1]==0:
        judge[i-1]=i

arr=[0]*m #出た素因数を-1にする
for i in range(len(a)):
    if arr[judge[a[i]-1]-1]<0:
        q=1
    else:
        arr[judge[a[i]-1]-1]=-1

if q>0:
    if reduce(math.gcd,a)!=1:
        q=2

if q==0:
    print('pairwise coprime')

elif q==1:
    print('setwise coprime')
        
else:
    print('not coprime')

Submission status: Wrong Answer

Solution code:
from collections import Counter
primes = []
flag = [True for i in range(10**3 + 1)]
for i in range(2, 10**3 + 1):
    if flag[i]:
        for j in range(2, 10**3 + 1):
            if i * j > 10**3:
                break
            flag[i * j] = False
        primes.append(i)


N = int(input())
adict = {}
for a in map(int, input().split()):
    f = True
    for p in primes:
        if a % p == 0:
            adict[p] = adict.setdefault(p, 0) + 1
            f = False
    if f:
        adict[a] = adict.setdefault(a, 0) + 1

count = Counter(adict.values())
_max = max(count)
if _max == 1:
    print("pairwise coprime")
elif _max == N:
    print("not coprime")
else:
    print("setwise coprime")

Submission status: Wrong Answer

Solution code:
import math
from functools import reduce

N = int(input())
A = list(map(int, input().split()))
MAX = 10**6 + 1

cut = [2 for _ in range(MAX)]
for i in range(3, MAX, 2):
    if cut[i] != 2:
        continue
    for j in range(i, MAX, i):
        cut[j] = i

if reduce(math.gcd, A) != 1:
    print('not coprime')
    exit()

already = set()
for a in A:
    now = set()
    while a != 1:
        if cut[a] in already:
            print('setwise coprime')
            exit()
        a //= cut[a]
        now.add(cut[a])
    already |= now

print('pairwise coprime')

Submission status: Wrong Answer

Solution code:
import numpy as np


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


cnt = np.bincount(arr)


ans1 = np.all([cnt[i::i].sum() <= 1 for i in range(2, 1000)])
ans2 = np.gcd.reduce(arr) == 1

if ans1 and ans2:
    print("pairwise coprime")
elif ans2:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Wrong Answer

Solution code:
import math
from functools import reduce

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

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


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

    if temp!=1:
        arr.append([temp, 1])

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

    return arr


N = int(input())
A = list(map(int, input().split()))
all_so = []
num2cnt = {}
cnt = 0
for i in range(N):
    so = [one[0] for one in factorization(A[i])]
    flag = False
    for one in so:
        if one not in all_so:
            all_so.append(one)
            flag=True
            
    if flag:
        cnt+=1
if cnt==N:
    print('pairwise coprime')
else:
    if gcd_list(A)==1:
        print('setwise coprime')
    else:
        print('not coprime')

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
sumA = sum(A)%(1000000007)
square = 0
for i in range(N):
    square -=  ( (A[i]%(1000000007))**2 ) % (1000000007)
    if square < 0:
      square = square + 1000000007
res = ( ((sumA * sumA + square)%(1000000007))*((1000000007+1)/2) ) % 1000000007
print(round(res))

Submission status: Wrong Answer

Solution code:
import sys

def prime(n):
    D = [i for i in range(n+1)]
    for i in range(2, n+1):
        if i != D[i]:
            break
        j = 2
        while j * i <= n:
            if D[j * i] == j * i:
                D[j * i] = D[i]
            j += 1
    return D

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

m = max(A)
if m == 1:
    print('pairwise coprime')
    sys.exit()

D = prime(m)

dic = {}

for i in range(n):
    if D[A[i]] not in dic:
        dic[D[A[i]]] = 1
    else:
        dic[D[A[i]]] += 1
#print(dic)
if n == len(dic):
    print('pairwise coprime')
elif len(dic) == 1:
    print('not coprime')
else:
    print('setwise coprime')

Submission status: Wrong Answer

Solution code:
from functools import reduce
from math import gcd

def sieve(L,R):
    if L<2:L=2
    flag=[0]*(R+1)
    for i in range(2, int(R**.5)+5):
        if flag[i] == 1:continue
        for j in range(i*2,R+1, i):
            if flag[j] == 1:continue
            if j % i == 0:
                flag[j] = 1
    
    return [i for i in range(L,R+1) if flag[i] == 0]
  
N=int(input())
*A,=map(int,input().split())

primes = sieve(2,10**3+5)
num = [0]*(10**6+5)
for i in range(N):
  num[A[i]] += 1

flag=0
for p in primes:
  count=0
  for d in range(p,10**6+5,p):
    count += num[d]
  if count > 1:
    flag=1
    break
  
if flag==0:
  print('pairwise coprime')
elif reduce(gcd,A)==1:
  print('setwise coprime')
else:
  print('not coprime')

Submission status: Wrong Answer

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

def g(ais): return reduce(gcd, ais) == 1

def f(ais):
	seen = set()
	for ai in ais:
		factor =2
		oi = ai
		while(ai != 1 and factor * factor <= oi):
			if ai % factor == 0:
				if factor in seen:
					return False
				while(ai % factor == 0):
					ai /= factor
				seen.add(factor)
			factor +=1
		if ai != 1:
			if ai in seen: return False
			seen.add(ai) 
	return True

ais = map(int, raw_input().split())
print ais
if f(ais):
	print 'pairwise coprime'
elif g(ais):
	print 'setwise coprime'
else:
	print 'not coprime'

Submission status: Wrong Answer

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

A = sorted(A,reverse = True)
prime = [0] * (10**6+1)
eratos = [True] * (A[0] + 1)
D = [0] * (A[0]+1)
D[1] = 1
for i in range(2,A[0] + 1):
  if not eratos[i]:
    continue
  else:
    for j in range(i,A[0] + 1,i):
      if not D[j]:
        D[j] = i
      if j!=i:
      	eratos[j] = False
  
for a in A:
  while a!=1:
    x = D[a]
    while a%x==0:
      a//=x
    prime[x] += 1

if max(prime)==1:
  print('pairwise coprime')
  
elif max(prime)!=N:
  print('setwise coprime')
else:
  print('not coprime')

Submission status: Wrong Answer

Solution code:
import sys
N = int(input())
A = list(map(int, input().split())) 
MAX = 10**6

not_pairwise_coprime = False #pairwise coprimeでないことを示すbool値(のちに更新)

# Aの要素に重複がある場合、少なくともpairwise coprimeではない
Ct = [0 for _ in range(MAX+1)]
for a in A:
  Ct[a] += 1 
if max(Ct[2:MAX+1]) > 1:
  not_pairwise_coprime = True
if max(Ct[2:MAX+1]) == N: # 全ての要素が等しい場合(例外処理)
  print("not coprime")
  sys.exit()
  
A = set(A) #集合型に書き換える(q in AをO(1)で判定するため)

for p in range(2,MAX+1):
  ct = 0 #pの倍数の個数を求める
  for q in range(p,MAX+1,p): #qはpの倍数全てを走る
    if q in A:
      ct += 1
  
  # ct = Nのとき、pはすべてのA_nの約数。つまり、Aはnot coprime
  if ct == N:
    print("not coprime")
    sys.exit()
  
  # 2 <= ct < Nのとき、pは2つ以上のA_nの約数。つまり、Aはpairwise coprimeではない。
  # setwise coprimeか、not coprimeかを判定するため、次のpを調べる必要あり。 
  elif ct >= 2:
    not_pairwise_coprime = True
  
  # ct <= 1のとき、pはどの２つのA_nの公約数にも一致しない。次のpを調べる必要あり。
  #else: continue
  
  
# ループが途中で終わるのは、not coprimeの場合であり、その場合に限る。
# したがって、この時点で可能性があるのは、setwise coprimeかpairwise coprimeのどちらか。
print("setwise coprime" if not_pairwise_coprime else "pairwise coprime")

Submission status: Wrong Answer

Solution code:
import sys
import math
from collections import defaultdict, deque, Counter
from copy import deepcopy
from bisect import bisect, bisect_right, bisect_left
from heapq import heapify, heappop, heappush
    
input = sys.stdin.readline
def RD(): return input().rstrip()
def F(): return float(input().rstrip())
def I(): return int(input().rstrip())
def MI(): return map(int, input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float,input().split()))
def Init(H, W, num): return [[num for i in range(W)] for j in range(H)]
    
    
def main():
    N = I()
    mylist = LI()
    max_num = max(mylist)
    max_num2 = math.ceil(math.sqrt(max_num))
    D = [True]* (max_num+1)
    D[0] = D[1] = False
    mylist = set(mylist)
    setwise = True
    pairwise = True

        
    for i in range(2, max_num+1):
        temp = 0
        if D[i]:
            for j in range(i, max_num+1, i):
                D[j] = False
                if j in mylist:
                    temp+=1
            if temp == N:
                print("not coprime")
                sys.exit()
            if temp >= 2:
                pairwise = False

    if pairwise:
        print("pairwise coprime")
    else:
        print("setwise coprime")
                    

            
    
    
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from collections import Counter
N = int(input())
A = list(map(int,input().split()))
countA = Counter(A)

#pairwiseかどうかを調べる
memo = [1]*(10**6+1)
memo[0] = 0
memo[1] = 0
for i in range(2,10**6+1):
    if memo[i] == 1:
        flag = False
        if i in countA:
            if countA[i] >= 2:
                break
            flag = True
        for j in range(i*2,10**6+1,i):
            if j in countA:
                if flag:
                    break
                else:
                    flag = True
            memo[j] = 0
        else:
            continue
        break
else:
    print("pairwise coprime")
    exit()



#setwise coprimeを判断
def gcd(a,b):
    return a if b==0 else gcd(b,a%b)

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: Wrong Answer

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

def g(ais): return reduce(gcd, ais) == 1

def f(ais):
	seen = set()
	for ai in ais:
		factor =2
		oi = ai
		while(ai != 1 and factor * factor <= oi):
			if ai % factor == 0:
				if factor in seen:
					return False
				while(ai % factor == 0):
					ai /= factor
				seen.add(factor)
			factor +=1
		if ai != 1:
			if ai in seen:
				return False
			seen.add(ai) 
	return True

ais = map(int, raw_input().split())

if f(ais):
	print 'pairwise coprime'
elif g(ais):
	print 'set coprime'
else:
	print 'not coprime'

Submission status: Wrong Answer

Solution code:
#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())

from math import gcd

def factorN(n):
    n1 = n + 1
    A = [2, 0] * ((n1+1)//2)
    for i in range(3, n1, 2):
        if A[i]: continue
        for j in range(i, n1, 2*i):
            A[j] = i

    def factor(n):
        if n == 1:
            return [(1, 1)]
        ans = []
        a, i = A[n], 1
        while n > 1:
            n //= a
            b = A[n]
            if a == b:
                i += 1
            else:
                ans.append((a, i))
                a = b
                i = 1

        return ans

    return factor

def resolve():
    it = map(int, sys.stdin.read().split())
    N = next(it)
    A = list(it)
    M = max(A)
    M1 = M + 1

    dp = [0] * M1

    g1 = A[0]
    f1 = factorN(M)
    for i, a in enumerate(A):
        g1 = gcd(g1, a)

        if a == 1:
            continue

        for x, _ in f1(a):
            if dp[x]:
                for i in range(i+1, N):
                    a = A[i]
                    g1 = gcd(g1, a)
                    if g1 == 1:
                        print("setwise coprime")
                        return
                print("not coprime")
                return
            dp[x] = 1

    print("pairwise coprime")

if __name__ == "__main__":
    resolve()

Submission status: Wrong Answer

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

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

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

    return set(arr)

import math
N=int(input())
A=list(map(int,input().split()))
ans=['pairwise coprime','setwise coprime1','not coprime']
k=0
s=factorization(A[0])
for a in A[1:]:
    tmp=factorization(a)
    if s&tmp==set():
        s|=tmp
    else:
        k=-1
        break
if k==-1:
    g=A[0]
    for a in A[1:]:
        g=math.gcd(g,a)
    if g==1:
        k=1
    else:
        k=2
print(ans[k])

Submission status: Wrong Answer

Solution code:
from math import gcd
n = int(input())
a = [int(i) for i in input().split()]

g = a[0]
for i in range(n):
    g = gcd(g,a[i])
if g != 1:
    print("not coprime")
    exit()

m = max(a)
fac = [1]*(m+1)
for i in range(2,m+1):
    if fac[i] != 1: continue
    for j in range(i,m+1,i): fac[j] = i
s = set()
for i in range(n):
    x = fac[a[i]]
    if x in s:
        print("setwise coprime")
        exit()
    s.add(x)
print("pairwise coprime")

Submission status: Wrong Answer

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

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

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

    return set(arr)

import math
N=int(input())
A=list(map(int,input().split()))
ans=['pairwise coprime','setwise coprime','not coprime1']
k=0
s=factorization(A[0])
for a in A[1:]:
    tmp=factorization(a)
    if s&tmp==set():
        s|=tmp
    else:
        k=-1
        break
if k==-1:
    g=A[0]
    for a in A[1:]:
        g=math.gcd(g,a)
    if g==1:
        k=1
    else:
        k=2
print(ans[k])