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:
N = int(input())
A = list(map(int, input().split()))
A.sort()
R = int(A[-1]**0.5)

is_pairwise_coprime = True
is_setwise_coprime = True
checked = [0]*(R+2)
l = 0

for i in range(2, R+2):
    if checked[i]:
        continue
    
    # 調べる範囲を狭める
    while A[l] < i and l < N-1:
        l += 1
    if l == N-1:
        break
    
    # iで割り切れるAiの個数を数える
    tmp = 0
    for j in range(l, N):
        if A[j]%i == 0:
            tmp += 1
    # 2個以上あればnot pairwise coprime
    # N個あれば not setwise coprime
    if tmp > 1:
        is_pairwise_coprime = False
    if tmp == N:
        is_setwise_coprime = False
    
    if is_setwise_coprime == False:
        break
    
    # iの倍数はチェック済みにする
    n = i
    while n < R+2:
        checked[n] = 1
        n += i
    # print(checked, l)
if is_pairwise_coprime:
    print('pairwise coprime')
elif is_setwise_coprime:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    input = sys.stdin.buffer.readline
    from math import gcd
    N = int(input())
    A = list(map(int, input().split()))
    g = A[0]
    M = max(A)
    X = [i for i in range(M+1)]
    S = [True for i in range(M+1)]
    S[0] = False
    S[1] = False

    for i in range(1, M+1):
        if S[i]:
            for j in range(i, M+1, i):
                if S[j]:
                    S[j] = False
                    X[j] = i
    flag = True
    s = set()
    ls = 0
    for x in A:
        tmp = set()
        while(X[x] != 1):
            tmp.add(X[x])
            x //= X[x]
        l = len(tmp)
        s |= tmp
        if len(s) == ls + l:
            ls += l
            continue
        else:
            break

    if flag:
        print("pairwise coprime")
    else:
        for x in A[1:]:
            g = gcd(g, x)
        if g == 1:
            print("setwise coprime")

        else:
            print("not coprime")


main()

Submission status: Wrong Answer

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


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


g = a[0]
for x in a[1:]:
    g = gcd(g, x)

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


exist = [False] * (10**6+1)
for x in a:
    if x % 2 == 0:
        if exist[2]:
            print('setwise coprime')
            exit()
        while x % 2 == 0:
            x //= 2
        exist[2] = True
    div = 3
    while div * div <= x:
        if x % div == 0:
            if exist[div]:
                print('setwise coprime')
                exit()
            while x % div == 0:
                x //= div
            exist[div] = True
        div += 2
    if x > 1:
        exist[x] = True
print('pairwise coprime')

Submission status: Wrong Answer

Solution code:
import math

n = int(input())
lst = [int(i) for i in input().split()]
lst.sort(reverse=True)
primes = set()
flag = True
for i in range(n):
  if not flag:
    break
  num = lst[i]
  count = 0
  while num % 2 == 0:
    num //= 2
    count += 1
    if pow(2, count) in primes:
      flag = False
      break
    primes.add(pow(2, count))
  f = 3
  while f <= math.sqrt(lst[i]) and flag:
    count = 0
    while num % f == 0:
      num //= f
      count += 1
      if pow(f, count) in primes:
        flag = False
        break
      primes.add(pow(f, count))
    f += 2
if not flag:
  a = lst[0]
  for i in range(1, n):
    b = lst[i]
    c = math.gcd(a, b)
    a = c
  if a != 1:
    print('not coprime')
  else:
    print('setwise coprime')
else:
  print('pairwise 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
		while(ai != 1):
			if ai % factor == 0:
				if factor in seen:
					return False
				while(ai % factor == 0):
					ai /= factor

				seen.add(factor)
			factor +=1
	return True
ais = map(int, raw_input().split())
if g(ais):
	if f(ais):
		print 'pairwise coprime'
	else:
		print 'set coprime'
else:
	print 'not coprime'

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1
from math import gcd

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

M=10**6

D=[-1]*(M+1)
D[0]=D[1]=1
for i in range(2,int(M**0.5)+1):
    if D[i]!=-1:
        continue
    for j in range(i*2,M+1,i):
        if D[j]==-1:
            D[j]=i

f=[False]*(M+1)

for x in A:
    l=[]
    while x>1:
        if f[x]==True:
            break
        x=D[x]
        l.append(x)
    else:
        for y in l:
            f[y]=True
        continue
    break
else:
    print('pairwise coprime')
    exit()

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

Submission status: Wrong Answer

Solution code:
import math

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

ans = "not coprime"

a, b = als[1], als[0]
if a < b:
    a,b = b,a
while a % b != 0:
    a, b = b, a % b
    if n == 2 and b == 1:
        ans = "pairwise coprime"
        failed = True

for i in range(2, n):
    a = als[i]
    if a < b:
        a,b = b,a 
    while a % b != 0:
        a, b = b, a % b
if b == 1:
    ans = "setwise coprime"
    # break

existeven = False

failed = False

for i in range(n):
    if als[i] >= 2 and als[i]%2 == 0:
        if existeven:
            failed = True
            break
        else:
            existeven = True

maxa = max(als)

checklist = []

for i in range(3, int(math.sqrt(maxa))+1, 2):
    for j in range(n):
        if als[j] >= i and als[j]%i == 0:
            checklist.append(i)
            checklist.append(als[j]/i)

if not failed:
    for i in checklist:
        existfactrial = False
        failed = False
        for j in range(n):
            if als[j] >= i and als[j]%i == 0:
                if existfactrial:
                    failed = True
                    break
                else:
                    existfactrial = True
        if failed:
            break
    if not failed:
        ans = "pairwise coprime"

print(ans)

Submission status: Wrong Answer

Solution code:
import math
from functools import reduce

n=int(input())
a=list(map(int,input().split()))
mxa=max(a)

            
def fact(num):
    arr = []
    temp = num
    for i in range(2, int(-(-num**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(num)
    return arr

  
flg=True
flg2=True
table=[0]*(mxa+1)
for (i,x) in zip(a,range(len(a))):
  fc=fact(i)
  for j in fc:
    table[1]=0
    if table[j]==1:
      flg=False
      break
    table[j]+=1

g=a[0]
for i in a[1:]:
  g=g*i//math.gcd(g,i)
    
if flg:
  print("pairwise coprime")
elif g==1:
  print("setwise coprime")
else:
  print("not coprime")

Submission status: Wrong Answer

Solution code:
import math
from functools import reduce
n = int(input())
num_list = [int(i) for i in input().split()]
count = 0

# for i in range(n-1):
#     for j in range(i+1,n):
#         if math.gcd(num_list[i],num_list[j]) == 1:
#             count += 1
#         else:
#             break

# if count == n * (n-1) / 2:
#     print("pairwise coprime")

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

if reduce(lcm_base, num_list, 1):
    print("pairwise coprime")
elif reduce(math.gcd, num_list) == 1:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
r = max(a)+1
s = []
t = [0]*r
for i in range(r):
    s.append([])
for i in range(2,r):
    for j in range(1,-(-r//i)):
        s[i*j].append(i)
for i in range(n):
    for j in range(len(s[a[i]])):
        t[s[a[i]][j]] += 1
print(t)
if(max(t) == n):
    print('not coprime')
elif(max(t) <= 1):
    print('pairwise coprime')
else:
    print('setwise coprime')

Submission status: Wrong Answer

Solution code:
import math
n=int(input())
l=list(map(int,input().split()))
c=l[0]
aa=0
for i in range(1,n):
    c=math.gcd(l[i],c)
prime=[2,3,5,7,11,13,17,19,23]
count=[0]*9
for i in range(n):
    for j in range(9):
        if(l[i]%prime[j]==0):
            count[j]+=1
        if(count[j]>=2):
            aa=1
            break   
if(aa==0 and c==1):
    print("pairwise coprime")
elif(c==1):
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Wrong Answer

Solution code:
import math

n = int(input())
lst = [int(i) for i in input().split()]
lst.sort(reverse=True)
primes = set()
flag = True
for i in range(n):
  if not flag:
    break
  num = lst[i]
  count = 0
  while num % 2 == 0:
    num //= 2
    count += 1
    if pow(2, count) in primes:
      flag = False
      break
    primes.add(pow(2, count))
  f = 3
  while f <= math.sqrt(num) and flag:
    count = 0
    while num % f == 0:
      num //= f
      count += 1
      if pow(f, count) in primes:
        flag = False
        break
      primes.add(pow(f, count))
    f += 2
  if num in primes:
    flag = False
    break
  primes.add(num)
if not flag:
  a = lst[0]
  for i in range(1, n):
    b = lst[i]
    c = math.gcd(a, b)
    a = c
  if a != 1:
    print('not coprime')
  else:
    print('setwise coprime')
else:
  print('pairwise coprime')

Submission status: Wrong Answer

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

pc = "pairwise coprime"
sc = "setwise coprime"
nc = "not coprime"

maxi=max(A)
sumi=set()
safe=set()
for i in range(2,maxi+1):
    if i in sumi:
        pass
    else:
        safe.add(i)
        tmp=maxi//i
        for j in range(2,tmp+1):
            sumi.add(j*i)
    #print(i,safe,sumi)

cnt=0
for num in A:
    if num in sumi:
        cnt +=1
if cnt<=1:
    ans=pc
else:
    tmp2=A[0]
    for q in range(1,N):
        tmp2 = gcd(tmp2,A[q])
    if tmp2==1:
        ans=sc
    else:
        ans=nc

print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    input = sys.stdin.buffer.readline
    from math import gcd
    N = int(input())
    A = list(map(int, input().split()))
    g = A[0]
    M = max(A)
    X = [i for i in range(M+1)]
    S = [True for i in range(M+1)]
    S[0] = False
    S[1] = False

    for i in range(1, M+1):
        if S[i]:
            for j in range(i, M+1, i):
                if S[j]:
                    S[j] = False
                    X[j] = i
    flag = True
    s = set()
    for x in A:
        while(X[x] != x):
            if X[x] in s:
                flag = False
                break
            else:
                s.add(X[x])
            x //= X[x]

        if x != 1:
            if x in s:
                flag = False
                break
            s.add(x)
        if flag:
            continue
        else:
            break

    if flag:
        print("pairwise coprime")
    else:
        for x in A[1:]:
            g = gcd(g, x)
        if g == 1:
            print("setwise coprime")

        else:
            print("not coprime")


main()

Submission status: Wrong Answer

Solution code:
import math

n = int(input())
lst = [int(i) for i in input().split()]
lst.sort(reverse=True)
primes = set()
flag = True
for i in range(n):
  if not flag:
    break
  num = lst[i]
  count = 0
  while num % 2 == 0:
    num //= 2
    count += 1
    if pow(2, count) in primes:
      flag = False
      break
    primes.add(pow(2, count))
  f = 3
  while f <= math.sqrt(num) and flag:
    count = 0
    while num % f == 0:
      num //= f
      count += 1
      if pow(f, count) in primes:
        flag = False
        break
      primes.add(pow(f, count))
    f += 2
if not flag:
  a = lst[0]
  for i in range(1, n):
    b = lst[i]
    c = math.gcd(a, b)
    a = c
  if a != 1:
    print('not coprime')
  else:
    print('setwise coprime')
else:
  print('pairwise coprime')

Submission status: Wrong Answer

Solution code:
from functools import reduce

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
  
N=int(input())
*A,=map(int,input().split())

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

l = 0
for i in range(N):
  f = set(primeFactor(A[i]).keys())
  if i == 0:
    fset = f
    l += len(f)
    continue
  fset |= f
  l += len(f)
  
if l == len(fset):
  print('pairwise coprime')
  exit()
  
if reduce(gcd,A)==1:
  print('setwise coprime')
else:
  print('not coprimce')

Submission status: Wrong Answer

Solution code:
import math

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

ans = "not coprime"

a, b = als[1], als[0]
if a < b:
    a,b = b,a
while a % b != 0:
    a, b = b, a % b
    if n == 2 and b == 1:
        ans = "pairwise coprime"
        failed = True

for i in range(2, n):
    a = als[i]
    if a < b:
        a,b = b,a 
    while a % b != 0:
        a, b = b, a % b
if b == 1:
    ans = "setwise coprime"
    # break

existeven = False

failed = False

for i in range(n):
    if als[i] >= 2 and als[i]%2 == 0:
        if existeven:
            failed = True
            break
        else:
            existeven = True

maxa = max(als)

if not failed:
    for i in range(3, int(math.sqrt(maxa))+2, 2):
        existfactrial = False
        failed = False
        for j in range(n):
            if als[j] >= i and als[j]%i == 0:
                if existfactrial:
                    failed = True
                    break
                else:
                    existfactrial = True
        if failed:
            break
    if not failed:
        ans = "pairwise coprime"

print(ans)

Submission status: Wrong Answer

Solution code:
import sys, math

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 == [] and n != 1:
        arr.append([n, 1])

    return arr

N = int(input())
A = list(map(int, sys.stdin.readline().rsplit()))

ok = True
S = set()
for a in A:
    arr = factorization(a)
    print(arr)
    for b, _ in arr:
        if b in S:
            ok = False
            break
        else:
            S.add(b)
    if ok is False:
        break
if ok:
    print("pairwise coprime")
else:
    tmp = A[0]
    for a in A[1:]:
        tmp = math.gcd(a, tmp)
    if tmp != 1:
        print("not coprime")
    else:
        print("setwise coprime")

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
A.sort()
R = int(A[-1]**0.5)

is_pairwise_coprime = True
is_setwise_coprime = True
checked = [0]*(R+2)
l = 0

for i in range(2, R+2):
    if checked[i]:
        continue
    
    # 調べる範囲を狭める
    # while A[l] < i:
    #     l += 1
    # if l == N-1:
    #     break
    
    # iで割り切れるAiの個数を数える
    tmp = 0
    for j in range(l, N):
        if A[j]%i == 0:
            tmp += 1
    # 2個以上あればnot pairwise coprime
    # N個あれば not setwise coprime
    if tmp > 1:
        is_pairwise_coprime = False
    if tmp == N:
        is_setwise_coprime = False
    
    if is_setwise_coprime == False:
        break
    
    # iの倍数はチェック済みにする
    n = i
    while n < R+2:
        checked[n] = 1
        n += i
    # print(checked, l)
if is_pairwise_coprime:
    print('pairwise coprime')
elif is_setwise_coprime:
    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())))


@njit
def solve(arr):
    ans = True
    x = arr[0]
    for i in range(1, arr.shape[0]):
        g = np.gcd(x, arr[i])
        if g != 1:
            ans = False
            break
        x = x * arr[i] // g
    return ans


ans1 = solve(arr)
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:
from math import gcd

N = int(input())
A = list(map(int, input().split()))
sieve = [1] * (10**6+1)
for i in range(2, 10**3):
	if sieve[i] == 1:
		sieve[i] = i
		j = 2
		while(j * i <= 10**6):
			sieve[j * i] = i
			j += 1
sieve[1] = 0

g = A[0]
a = 0
for i in range(1, N):
	g = gcd(g, A[i])
	if A[i] == 1:
		a = 1
	
if g != 1:
	print("not coprime")
else:
	if a == 1:
		print("setwise coprime")
		exit()
	s = set()
	for i in range(N):
		if sieve[A[i]] in s:
			print("setwise coprime")
			exit()
		s.add(sieve[A[i]])
	print("pairwise coprime")

Submission status: Wrong Answer

Solution code:
import sys
from math import gcd
import numpy as np


stdin = sys.stdin
def ns(): return stdin.readline().rstrip()
def ni(): return int(stdin.readline().rstrip())
def nm(): return map(int, stdin.readline().split())
def nl(): return list(map(int, stdin.readline().split()))


def main():
    n = ni()
    A = nl()
    c = A[0]
    b = []

    m = np.prod(A)

    for a in A:
        c = gcd(c, a)
        b.append(gcd(a, m // a))

    if c == 1 and all([bb == 1 for bb in b]):
        print('pairwise coprime')
    elif c == 1:
        print('setwise coprime')
    else:
        print('not coprime')


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from functools import reduce
from fractions import gcd
import sys

N = int(input())
A = list(map(int, input().split()))
P = 10 ** 9 + 7

lcm = 1
flg = True
pia = 1
"""
for a in A:
    pia = (pia * a) % P
    if gcd(lcm, a) != 1:
        flg = False
        break
    lcm = (lcm*a)%P
if flg:
    print('pairwise coprime')
    sys.exit()
"""

gcd_ = A[0]
for a in A[1:]:
    gcd_ = gcd(gcd_, a)
    if gcd_ == 1:
        print('setwise coprime')
        sys.exit()

print('not 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 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:
n = int(input())
a = list(map(int,input().split()))


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


g = a[0]
for x in a[1:]:
    g = gcd(g, x)

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


exist = [False] * (10**6+1)
for x in a:
    if x % 2 == 0:
        if exist[2]:
            print('setwise coprime')
            exit()
        exist[2] = True
    div = 3
    while div * div <= x:
        if x % div == 0:
            if exist[div]:
                print('setwise coprime')
                exit()
            while x % div == 0:
                x //= div
            exist[div] = True
        div += 2
    if x > 1:
        exist[x] = True
print('pairwise coprime')

Submission status: Wrong Answer

Solution code:
N = 1000001

spf = [*range(N)]
i = 2
while i * i < N:
  if spf[i] == i:
    for j in range(i * i, N, i):
      if spf[j] == j:
        spf[j] = i
  i += 1
  
t = 'pairwise', None, 'setwise', 'not'
r = 0
input()
u = set()
i = None
for x in map(int, input().split()):
  s = set()
  while x > 1:
    p = spf[x]
    if p in u:
      r |= 1
    s.add(p)
    x //= p
  u |= s
  if i: i &= s
  else: i = s
if not i:
  r |= 2
print(t[r], '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 coprime']
k=0
s=set()
for a in A:
    tmp=factorization(a)
    if s&tmp==set():
        s|=tmp
    else:
        k=-1
        break
if k==-1:
    g=A[0]
    for a in A:
        g=math.gcd(g,a)
    if g==1:
        k=1
    else:
        k=2
print(ans[k])

Submission status: Wrong Answer

Solution code:

import math
from functools import *
import sys
sys.setrecursionlimit(100000)
input = sys.stdin.readline


def array(size, init=0):
    return [[init for j in range(size[1])] for i in range(size[0])]


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


def II():
    return int(input())


mod = 10**9+7


def factorial(n):
    fact = 1
    for integer in range(1, n + 1):
        fact *= integer
    return fact


def permutate(x, A):
    n = len(x)
    res = [-1]*n
    for i in range(n):

        res[i] = x[A[i]]
    return res


def generate_bin(digit):
    for b in range(2**digit):
        b = bin(b)
        tmp = b[2:].zfill(digit)
        yield list(map(int, tmp))
        # b=list(map(int,list(b[2:].zfill(digit))))
        # yield b


def search(x, count):
    #print("top", x, count)

    for d in directions:
        nx = d+x
        # print(nx)
        if np.all(0 <= nx) and np.all(nx < (H, W)):
            if field[nx[0]][nx[1]] == "E":
                count += 1
                field[nx[0]][nx[1]] = "V"
                count = serch(nx, count)
                continue
            if field[nx[0]][nx[1]] == "#":
                field[nx[0]][nx[1]] = "V"
                count = serch(nx, count)

    return count


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


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


N = int(input())
a = acinput()

dp = [0]*(10**6+1)
dp[1] = 1

flg = 0
for sa in a:
    arr = factorization(sa)

    for ss in arr:
        s = ss[0]
        if dp[s] == 1:
            flg = 1
            break
        dp[s] = 1
    if flg:
        break

if min(a) <= 0:
    print(print("not coprime"))
    sys.exit()
if flg == 0:
    print("pairwise coprime")
elif 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()))


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


g = a[0]
for x in a[1:]:
    g = gcd(g, x)

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


exist = [False] * (10**6+1)
for x in a:
    if x % 2 == 0:
        if exist[2]:
            print('setwise coprime')
            exit()
        exist[2] = True
    div = 3
    while div * div <= x:
        if x % div == 0:
            if exist[div]:
                print('setwise coprime')
                exit()
            while x % div == 0:
                x //= div
            exist[div] = True
        div += 2
print('pairwise coprime')

Submission status: Wrong Answer

Solution code:
N = 1000001

spf = [*range(N)]
i = 2
while i * i < N:
  if spf[i] == i:
    for j in range(i * i, N, i):
      if spf[j] == j:
        spf[j] = i
  i += 1
  
t = 'setwise', None, 'pairwise', 'not'
r = 0
input()
u = set()
i = None
for x in map(int, input().split()):
  s = set()
  while x > 1:
    p = spf[x]
    if p in u:
      r |= 1
    s.add(p)
    x //= p
  u |= s
  if i: i &= s
  else: i = s
if not i:
  r |= 2
print(t[r], 'coprime')

Submission status: Wrong Answer

Solution code:
import sys
import math

prime = []

for i in range(2,1001):
    det = 0
    for j in range(2,int(i**(1/2))+1):
        if i%j==0:
            det = -1
            break
    if det == 0:
        prime.append(i)

#print(prime)

N = int(input())
A = list(map(int,input().split()))
B = []###Aのうち1ではないもの
det = False###Aが1を含んでいたか否か

for i in range(N):
    if A[i] == 1:
        det = True
    else:
        B.append(A[i])

if len(B) <= len(prime):

    m = 1

    for p in prime:
        count = 0
        for b in B:
            if b%p==0:
                count += 1
        m = max(m,count)
        if m >= 2:
            break
    
    if m == 1:
        print('pairwise coprime')
        sys.exit(0)

if det:
    print('setwise 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: Wrong Answer

Solution code:
import math

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

def eratosthenes(n):
    checker = [0] * (n+1)
    checker[0] = 1 #素数でない
    checker[1] = 0 #素数でない
    for i in range(2, n):
        if checker[i] == 0:
            for j in range(2, n // i + 1):
                checker[i * j] = i
    return checker

def check_by_eratosthenes(x, checker):
    if checker[x] == 0:
        checker[x] = -1
        return True
    if checker[x] < 0:
        return False
    else:
        y = x // checker[x]
        if checker[y] != checker[x] and y != checker[x]:
            checker[checker[x]] = -1
        if y < checker[x]:
            checker[x] = -1
        return check_by_eratosthenes(y, checker)

n = int(input())
a = list(map(int, input().split()))
a.sort()
for i in range(n):
    if a[i] != 1:
        break
x = 1 if a[0] == 1 else a[i]
a = a[i:]
n -= i
if n == 1:
    print("pairwise coprime")
    quit()

checker = eratosthenes(a[-1])


pairwise = True
setwise = True
for i in range(n):
    if x != 1:
        x = gcd(x, a[i])
    if pairwise:
        pairwise = check_by_eratosthenes(a[i], checker)

if pairwise:
    print("pairwise coprime")
elif x == 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())))


@njit
def solve(arr):
    ans = True
    for i in range(arr.shape[0] - 1):
        if np.gcd(arr[i], arr[i + 1]) != 1:
            ans = False
            break
    return ans


ans1 = solve(arr)
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

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

def eratosthenes(n):
    checker = [0] * (n+1)
    checker[0] = 1 #素数でない
    checker[1] = 0 #素数でない
    for i in range(2, n):
        if checker[i] == 0:
            for j in range(2, n // i + 1):
                checker[i * j] = i
    return checker

def check_by_eratosthenes(x, checker):
    if checker[x] == 0:
        checker[x] = -1
        return True
    if checker[x] < 0:
        return False
    else:
        y = x // checker[x]
        if checker[y] != checker[x] and y != checker[x]:
            checker[checker[x]] = -1
        if y < checker[x]:
            checker[x] = -1
        return check_by_eratosthenes(y, checker)

n = int(input())
a = list(map(int, input().split()))
a.sort()
for i in range(n):
    if a[i] != 1:
        break
x = 1 if a[0] != 1 else a[i]
a = a[i:]
n -= i
if n == 1:
    print("pairwise coprime")
    quit()

checker = eratosthenes(a[-1])


pairwise = True
setwise = True
for i in range(n):
    if x != 1:
        x = gcd(x, a[i])
    if pairwise:
        pairwise = check_by_eratosthenes(a[i], checker)

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