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:
import sys
from math import gcd
input=sys.stdin.readline
#sys.setrecursionlimit(10**6)

def Ed(num,ycnt):
    for i in range(1,int(num**0.5)+1):
        if num%i==0:
            ycnt[i]+=1
            if num//i!=i:
                ycnt[num//i]+=1

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

    ycnt=[0]*(10**6+1)
    gsum=a[0]

    for i in a:
        gsum=gcd(gsum,i)
        Ed(i,ycnt)

    if max(ycnt)<2:
        print("pairwise coprime")
    elif gsum==1:
        print("setwise coprime")
    else:print("not coprime")

if __name__=="__main__":main()

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
tmp = [False if i == 0 or i == 1 else True for i in range(1000)]
p, s = True, True

for i in range(2, 1000):
    t = 0
    if not tmp[i]:
        continue
    for j in A:
        if j % i == 0:
            t += 1

    for j in range(i * 2, 1000, i):
        tmp[j] = False

    if t >= 2:
        p = False

    if t == N:
        s = False
        break

print('pairwise coprime' if p else 'setwise coprime' if s else 'not coprime')

Submission status: Wrong Answer

Solution code:
from math import gcd

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

setgcd = A[0]
for i in range(N):
    setgcd = gcd(setgcd,A[i])
    if A[i]==1:
        print("setwise coprime")
        exit()
is_set = True
if setgcd != 1:
    is_set=False

M = max(A)
is_prime=[1]*(M+1)#Mまで行きたい
is_inA=[0]*(M+1)
for i in range(N):
    is_inA[A[i]]=1

is_pair = True
is_prime[0]=0
is_prime[1]=0
for i in range(2,M+1):
    count = 0
    if is_inA[i]==1:
        count=1
    if is_prime[i]==1:
        for j in range(2*i,M+1,i):
            is_prime[j]=0
            if is_inA[j]==1:
                count+=1
    if count >= 2:
        is_pair = False

if is_pair:
    print("pairwise coprime")
elif is_set:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Wrong Answer

Solution code:
def sieve_eratosthenes(n):
    primes = [0, 1] * (n // 2 + 1)
    if n % 2 == 0:
        primes.pop()
    primes[1] = 0
    primes[2] = 1
    for p in range(3, n + 1, 2):
        if primes[p]:
            for q in range(p * p, n + 1, 2 * p):
                primes[q] = 0
    return primes

N = int(input())
A = list(map(int,input().split()))
P = sieve_eratosthenes(10**6)
Ps = []
for i in range(10**6):
    if P[i]==1:
        Ps.append(i)
PN = len(Ps)

if N>PN+1:
    print("not coprime")
else:
    flag = 0
    pf={}
    for i in range(N):
        pf1 = {}
        m=A[i]
        for i in range(2,int(m**0.5)+1):
            while m%i==0:
                pf1[i]=pf1.get(i,0)+1
                m//=i
        if m>1:pf1[m]=1
        for i in pf1.keys():
            pf[i]=pf.get(i,0)+1
            if pf[i]>1:
                flag = 1
    if flag==0:
        print("pairwise coprime")
    else:
        import fractions
        ans = A[0]
        for i in range(1, N):
            ans = fractions.gcd(ans, A[i])
        if ans==1:
            print("setwise coprime")
        else:
            print("not coprime")

Submission status: Wrong Answer

Solution code:
def factorize(n):
    tmp = n
    flag = False

    for i in range(2, int(-(-n**0.5//1))+1):
        if tmp % i == 0:
            cnt = 0
            while tmp % i == 0:
                cnt += 1
                tmp //= i
            if i in prime_cnt:
                prime_cnt[i] += 1
            else:
                prime_cnt[i] = 1
            flag = True
         
    if tmp != 1:
        if tmp in prime_cnt:
            prime_cnt[tmp] += 1
        else:
            prime_cnt[tmp] = 1
        flag = True
    
    if not flag:
        if n in prime_cnt:
            prime_cnt[n] += 1
        else:
            prime_cnt[n] = 1

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

prime_cnt = {}

for i in range(N):
    if A[i] != 1:
        factorize(A[i])

pw_cp = True
st_cp = True

for val in prime_cnt.values():
    if val != 1:
        pw_cp = False
    if val == N:
        st_cp = False

print(prime_cnt)

if pw_cp:
    print('pairwise coprime')
elif st_cp:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Wrong Answer

Solution code:
def divisor(i):
    s = []
    for j in range(1, int(i ** (1 / 2)) + 1):
        if i % j == 0:
            s.append(i // j)
            s.append(j)
    return sorted(set(s))

import math

n = int(input())
a = list(map(int, input().split()))
ans = ["pairwise coprime", "setwise coprime", "not coprime"]
if n >= 200000:
    g = a[0]
    for i in a:
        g = math.gcd(i, g)
        if g == 1:
            print(ans[1])
            exit()
    print(ans[2])
    exit()
else:
    x = [0] * 1000005
    for i in a:
        if not i == 1:
            s = divisor(i)
            t = 1
            for j in s:
                if j == 1:
                    continue
                if x[j] == 1:
                    t = 0
                    break
                x[j] = 1
            if t == 0:
                break
    if t == 1:
        print(ans[0])
        exit()
    g = a[0]
    for i in a:
        g = math.gcd(i, g)
        if g == 1:
            print(ans[1])
            exit()
    print(ans[2])
    exit()

Submission status: Wrong Answer

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

import math 

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

if ans!=1:
    print("not coprime")
    exit()
else:
    checked=[0]*(int(max(a)**(0.5))+100)

    for item in a:

        for j in range(2,int(item**0.5)+1):
            if item%j==0 and j*j<=item:
                if checked[j]==0:
                    checked[j]+=1
                else:
                    print(item,j,checked)
                    #print("setwise coprime")
                    exit()
print("pairwise coprime")

Submission status: Wrong Answer

Solution code:
def make_divisors(n):
    lower_divisors, upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return set(lower_divisors[1:] + upper_divisors[::-1])


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

is_pairwise = True
is_setwise = False

f_set = set()
n_set = set()

for item in a:
    if item in n_set:
        is_pairwise = False
        break
    else:
        n_set.add(item)
    for fc in make_divisors(item):
        if fc in f_set:
            is_pairwise = False
            break
        else:
            f_set.add(fc)
    if not is_pairwise:
        break

s_set = make_divisors(a[0])
for item in a[1:]:
    tmp_set = make_divisors(item)
    s_set = s_set & tmp_set
    if len(s_set) == 0:
        is_setwise = True

if is_pairwise:
    print('pairwise coprime')
elif is_setwise:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Wrong Answer

Solution code:
import math

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

# n以下の素数列挙(O(n log(n))
def primes(n):
    ans = []
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n ** 0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    for i in range(len(is_prime)):
        if is_prime[i]:
            ans.append(i)
    return ans


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


P = primes(A[-1])
L = len(P)

# MAX以下の素数の数より多い
if N <= L:
    USED = [False] * (10 ** 6 + 10)
    ok = True
    for a in A:
        f = fctr1(a)
        for x, c in f:
            if not USED[x]:
                USED[x] = True
            else:
                ok = False
                break

    if ok:
        print("pairwise coprime")
        exit()

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

if t == 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()))

check1 = False
check2 = True

def gcd_list(numbers):
    return reduce(math.gcd, numbers)
  
def prime_decomposition(x):
  i = 2
  ls = []
  while i * i <= x:
    while x % i == 0:
      x /= i
      ls.append(i)
    i += 1
  if x > 1:
    ls.append(x)
  return ls
  

if gcd_list(A) == 1:
  check1 = True
  
A.sort()
for i in set(prime_decomposition(A[0])):
  for j in A[1:]:
    if j % i == 0:
      check2 = False
      break
  if not check2:
    break
    
if check1 and check2:
  print("pairwise coprime")
elif check1:
  print("setwise coprime")
else:
  print("not coprime")

Submission status: Wrong Answer

Solution code:
n = int(input())
*arr, = map(int, input().split())

def pairwise_coprime(arr):
    mx = max(arr)
    data = [0] * (mx + 1)
    for v in arr:
        data[v] = 1
    primes = [1] * (mx + 1)
    for v in range(2, mx + 1):
        if primes[v]:
            cnt = 0
            if data[v]:
                cnt += 1
            for nonprime in range(2 * v, mx + 1, v):
                primes[nonprime] = 0
                if data[nonprime]:
                    cnt += 1
            if cnt > 1:
                return False
    return True

def gcd(a, b):
    if a > b:
        a, b = b, a

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


def setwise_coprime(arr):
    common_gcd = arr[0]
    for i in range(1, len(arr)):
        common_gcd = gcd(common_gcd, arr[i])
    return common_gcd == 1


if pairwise_coprime(arr):
    print("pairwise coprime")
elif setwise_coprime(arr):
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Wrong Answer

Solution code:
def gcd(x,y):
  return y if x%y==0else gcd(y,x%y)

N=int(input())

A=list(map(int,input().split()))
primes=[];
isprime=[1 for i in range(0,1001)];
for i in range(2,1001):
  if isprime[i]:
    primes.append(i)
    j=2;
    while i*j<=1000:
      isprime[i*j]=0;
      j+=1
s=set();
pc=1

for i in range(N):
  a=A[i];
  
  for p in primes:
    if a==1:
      break
    if(a%p==0):
      #while(a%p==0):
      #  a//=p;
      if p in s:
        pc=0
      s.add(p)
      
    #if a>1000:
    #  if a in s:
    #    pc=0
    #  s.add(a)

g=A[0];
for i in range(1,N):
  g=gcd(g,A[i])
print("pairwise coprime"if pc else("setwise coprime"if g==1 else "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, 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()))

a.sort()

jd=[True]*(a[-1]+10)

pairwise=True

for i in a:
    xxx=factorization(i)
    for j in xxx:
        if jd[j[0]]==True:
          jd[j[0]]=False
        else:
            pairwise=False
            break
    
    if pairwise==False:
        break

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


zzz=factorization(a[0])

for i in zzz:
    pin=i[0]
    flag=True
    cnt=0
    for j in a:
      if j%pin==0:
          cnt+=1
    
    if cnt==n:
        print('not coprime')


print('setwise coprime')

Submission status: Wrong Answer

Solution code:
from math import gcd

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

setgcd = A[0]
for i in range(N):
    setgcd = gcd(setgcd,A[i])
    if A[i]==1:
        print("not coprime")
        exit()
is_set = True
if setgcd != 1:
    is_set=False

M = max(A)
is_prime=[1]*(M+1)#Mまで行きたい
is_inA=[0]*(M+1)
for i in range(N):
    is_inA[A[i]]=1

is_pair = True
is_prime[0]=0
is_prime[1]=0
for i in range(2,M+1):
    count = 0
    if is_inA[i]==1:
        count=1
    if is_prime[i]==1:
        for j in range(2*i,M+1,i):
            is_prime[j]=0
            if is_inA[j]==1:
                count+=1
    if count >= 2:
        is_pair = False

if is_pair:
    print("pairwise coprime")
elif is_set:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Wrong Answer

Solution code:
from math import gcd
from functools import reduce
N = int(input())
*A, = map(int, input().split())
mod = 10**9 + 7

def lcm(a, b):
    return a*b//gcd(a,b) % mod

def mul(a, b):
    return a*b%mod

if reduce(lcm, A) == reduce(mul, A):
    print('pairwise coprime')
elif reduce(gcd, A) == 1:
    print("setwise coprime")
else:
    print('not coprime')

Submission status: Wrong Answer

Solution code:
import sys,math
n=int(input())
a=list(map(int,input().split()))
sieve=[0]*(10**6+1)
numbers=set()
flag=0
for i in range(n):
  if a[i] in numbers:
    flag=1
    break
  numbers.add(a[i])
pointer=2
while pointer<10**6+1:
  if sieve[pointer]==1:
    pointer+=1
    continue
  count=0
  pointer2=pointer
  while pointer2<10**6+1:
    if pointer2 in numbers:
      count+=1
    sieve[pointer2]=1
    pointer2+=pointer
  if count>=2:
    flag=1
    break
if flag==0:
  print('pairwise coprime')
  sys.exit()
ans=a[0]
for i in range(1,n):
  ans=math.gcd(a[i],ans)
if ans==1:
  print('setwise coprime')
else:
  print('not coprime')

Submission status: Wrong Answer

Solution code:
# coding: utf-8
from math import gcd

import math

# 素数判定関数
def isPrime(num):
    # 2未満の数字は素数ではない
    if num < 2: return False
    # 2は素数
    elif num == 2: return True
    # 偶数は素数ではない
    elif num % 2 == 0: return False

    # 3 ~ numまでループし、途中で割り切れる数があるか検索
    # 途中で割り切れる場合は素数ではない
    for i in range(3, math.floor(math.sqrt(num))+1, 2):
        if num % i == 0:
            return False

    # 素数
    return True

# 素数判定
def callIsPrime(input_num=1000):
    numbers = []
    # ループしながら素数を検索する
    for i in range(1, input_num):
        if isPrime(i):
            numbers.append(i)

    # 素数配列を返す
    return numbers

# 関数の呼び出し
prime_list = callIsPrime(10**3)

N=int(input())
A=list(map(int,input().split()))
prime_flg = [True for i in range(10**3)]
pc_flg=True

if len(A)!=len(set(A)):
    pc_flg=False

for i in range(N):
    for j in range(len(prime_list)):
        p=prime_list[j]
        if A[i]%p == 0:
            if prime_flg[p]:
                prime_flg[p]=False
            else:
                pc_flg=False

x = A[-1]

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


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

g = A[0]
l = A[0]
prod = A[0]
for i in range(1, N):
	g = gcd(g, A[i])
	l = (l * A[i]) // g
	prod *= A[i]
	
if g != 1:
	print("not coprime")
else:
	if l == prod:
		print("pairwise coprime")
	else:
		print("setwise coprime")

Submission status: Wrong Answer

Solution code:
from math import gcd
n = int(input())
a = list(map(int, input().split()))
a.sort()

g = a[0]
pair = True
for i in range(n-1):
    g = gcd(g, a[i+1])
    # 一度でも互いに素でない組合せが出たらpariwise coprimeではない
    if g > 1: pair = False
if g > 1:
    print('not coprime')
    exit(0)
if not pair:
    print('setwise coprime')
    exit(0)
else:
    print('pairwise coprime')

Submission status: Wrong Answer

Solution code:
def pair (inp):
    from collections import Counter
    z=max(inp)
    arr=[1]*(z+1)
    c=Counter(inp)
    for i in range(2,int(pow(z,0.5))+1):
        if arr[i]==1:
            k=2
            f=0
            while k*i<len(arr):
                arr[k*i]=0
                if c[k*i]!=0:
                    f+=1
                k+=1
            if f>=2:
                return -1
    return 1
def gcd (a,b):
    if a%b==0:
        return b
    if b%a==0:
        return a
    if a>b:
        return gcd(b,a%b)
    if b>a:
        return gcd(a,b%a)
n=int(input())
arr=list(map(int,input().split()))
if pair(arr)==1:
    print ('pairwise coprime')
else:
    k=arr[0]
    for i in range(1,len(arr)):
        k=gcd(k,arr[i])
        if k==1:
            break
    if k==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()))

check1 = False
check2 = True

def gcd_list(numbers):
    return reduce(math.gcd, numbers)
  
def prime_decomposition(x):
  i = 2
  ls = []
  while i * i <= x:
    while x % i == 0:
      x /= i
      ls.append(i)
    i += 1
  if x > 1:
    ls.append(x)
  return ls
  

if gcd_list(A) == 1:
  check1 = True
  
  A.sort()
  for i in set(prime_decomposition(A[0])):
    for j in A[1:]:
      if j % i == 0:
        check2 = False
        break
    if not check2:
      break

else:
  check1 = False
  check2 = False
    
if check1 and check2:
  print("pairwise coprime")
elif check1:
  print("setwise coprime")
else:
  print("not coprime")

Submission status: Wrong Answer

Solution code:
'''
自宅用PCでの解答
'''
import math
#import numpy as np
import itertools
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7 #998244353
dir = [(-1,0),(0,-1),(1,0),(0,1)]
alp = "abcdefghijklmnopqrstuvwxyz"

#nまでの素数の配列を返す関数
def primes(n):
    if n == 1:
        return []
    else:
        tbl = [True]*(n+1)
        pri = set([2])
        for i in range(2,n+1,2):
            tbl[i] = False
        k = 3
        while k <= n:
            if tbl[k]:
                pri.add(k)
                for i in range(k,n+1,k):
                    tbl[i] = False
            k += 2
        return pri

def main():
    n = int(ipt())
    ps = primes(10**3)
    d = defaultdict(bool)
    nm = 0
    a = []
    for i in map(int,ipt().split()):
        if i != 1:
            a.append(i)
    n = len(a)
    if n == 0:
        print("pairwise coprime")
        exit()
    g = a[0]
    f = True
    if n > 78500:
        f = False

    for i in a:
        g = math.gcd(g,i)
        if f:
            ni = i
            for j in ps:
                ff = True
                while ni%j == 0:
                    if ff and d[i]:
                        f = False
                    d[i] = True
                    ff = False
                    ni //= j
                    if ni == 1:
                        break
            if ni == 1:
                continue
            if d[ni]:
                f = False
            d[ni] = True
        if g == 1 and not f:
            break

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




    return None

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
import math
from collections import deque
from collections import defaultdict

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid(h, w, num): return [[int(num)] * w for _ in range(h)]


# Nの素因数分解を辞書で返す
def prime_fact(n):
    if n == 1:
        return {1: 1}

    root = int(math.sqrt(n))
    prime_dict = {}
    for i in range(2, root+1):
        cnt = 0
        while n % i == 0:
            cnt += 1
            n = n // i
        if cnt:
            prime_dict[i] = cnt
        if n == 1:
            break
    if n != 1:
        prime_dict[n] = 1
    return prime_dict


def main():
    N = NI()
    A = NLI()
    
    if max(A) == 1:
        print("pairwise coprime")
        exit()
    if min(A) == 1:
        print("setwise coprime")
        exit()
    
    
    p_cnt = defaultdict(int)
    PD_list = defaultdict(dict)
    for a in A:
        if PD_list[a]:
            AP = PD_list[a]
        else:
            AP = prime_fact(a)
        PD_list[a] = AP
        for apk in AP.keys():
            p_cnt[apk] += 1

    max_p = max(p_cnt.values())
    if max_p == 1:
        print("pairwise coprime")
    elif max_p == N:
        print("not coprime")
    else:
        print("setwise coprime")



if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def sieve_eratosthenes(n):
    primes = [0, 1] * (n // 2 + 1)
    if n % 2 == 0:
        primes.pop()
    primes[1] = 0
    primes[2] = 1
    for p in range(3, n + 1, 2):
        if primes[p]:
            for q in range(p * p, n + 1, 2 * p):
                primes[q] = 0
    return primes

N = int(input())
A = list(map(int,input().split()))
P = sieve_eratosthenes(10**6)
Ps = []
for i in range(10**6):
    if P[i]==1:
        Ps.append(i)
PN = len(Ps)

if N>PN+1:
    print("Not coprime")
else:
    flag = 0
    pf={}
    for i in range(N):
        pf1 = {}
        m=A[i]
        for i in range(2,int(m**0.5)+1):
            while m%i==0:
                pf1[i]=pf1.get(i,0)+1
                m//=i
        if m>1:pf1[m]=1
        for i in pf1.keys():
            pf[i]=pf.get(i,0)+1
            if pf[i]>1:
                flag = 1
    if flag==0:
        print("pairwise coprime")
    else:
        import fractions
        ans = A[0]
        for i in range(1, N):
            ans = fractions.gcd(ans, A[i])
        if ans==1:
            print("setwise coprime")
        else:
            print("not coprime")

Submission status: Wrong Answer

Solution code:
def gcd(x,y):
  return y if x%y==0else gcd(y,x%y)

N=int(input())

A=list(map(int,input().split()))
primes=[];
isprime=[1 for i in range(0,1001)];
for i in range(2,1001):
  if isprime[i]:
    primes.append(i)
    j=2;
    while i*j<=1000:
      isprime[i*j]=0;
      j+=1
s=set();
pc=1

for i in range(N):
  a=A[i];
  
  for p in primes:
    if a==1:
      break
    if(a%p==0):
      while(a%p==0):
        a//=p;
      if p in s:
        pc=0
      s.add(p)
      
    if a>1000:
      if a in s:
        pc=0
      s.add(a)

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

Submission status: Wrong Answer

Solution code:
#dt = {} for i in x: dt[i] = dt.get(i,0)+1
import sys;input = sys.stdin.readline
inp,ip = lambda :int(input()),lambda :[int(w) for w in input().split()]

#from fractions import gcd

def gcd(a, b) : 
    if a == 0 : return b 
    if b == 0 : return a 
    k = 0
    while ((a | b) & 1) == 0: 
        a >>= 1
        b >>= 1
        k += 1
    while (a & 1) == 0: 
        a >>= 1
    while b:  
        while (b & 1) == 0: 
            b >>= 1
        if a > b : 
            a,b = b,a
        b = b - a 
    return a << k 

n = inp()
x = ip()
ans = 'pairwise coprime'
prev = x[0]
for i in range(1,n):
    t = gcd(prev,x[i])
    #print(t)
    prev = t
    if t != 1:
        ans = 'setwise coprime'
if t != 1:
    ans = 'not coprime'
print(ans)

Submission status: Wrong Answer

Solution code:
import math
N = int(input())
A = list(map(int,input().rstrip().split(" ")))
M = int(math.sqrt(max(A))) + 1
sosuu = set()
sosuu.add(2)
for i in range(3,M,2):
    for j in sosuu:
        if i % j == 0:
            break
    else:
        sosuu.add(i)

pair = True
setw = True
counter = 0
lis = [0 for i in range(1001)]
for i in A:
    remset = set()
    for j in sosuu:
        if i % j == 0:
            lis[j] += 1
            if lis[j] == 2:
                pair = False
        else:
            if lis[j] >= 2 or pair == False:
                remset.add(j)
    for j in remset:
        sosuu.remove(j)

for i in sosuu:
    if lis[i] == len(A):
        setw = False

if pair:
    print("pairwise coprime")
elif setw:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)
# input = sys.stdin.readline    ####
def int1(x): return int(x) - 1
def II(): return int(input())
def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())
def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def MS(): return input().split()
def LS(): return list(input())
def LLS(rows_number): return [LS() for _ in range(rows_number)]
def printlist(lst, k=' '): print(k.join(list(map(str, lst))))
INF = float('inf')
# from math import ceil, floor, log2
# from collections import deque, defaultdict
# from itertools import combinations as comb, combinations_with_replacement as comb_w, accumulate, product, permutations
# from heapq import heapify, heappop, heappush
# import numpy as np    # cumsum
# from bisect import bisect_left, bisect_right

# from fractions import gcd
from math import gcd
# def lcm(x, y):
#   return x // gcd(x, y) * y

def solve():
    N = II()
    A = LI()
    
    g = A[0]
    flag_pc = True
    for a in A[1:]:
        g = gcd(g, a)
        # print(g)
        if g != 1:
            flag_pc = False
    if g == 1:
        if flag_pc:
            print('pairwise coprime')
        else:
            print('setwise coprime')
    else:
        print('not coprime')


if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

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

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

def fac(n):
    arr = set()
    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.add(i)
            arr.add(cnt)
    if temp!=1:
        arr.add(temp)
        arr.add(1)
    if arr==set():
        arr.add(n)
        arr.add(1)
    return arr
###############################################################
ans=pc
st = set()

for num in A:
    tmp = fac(num)
    #print(num,tmp)
    for p in tmp:
        if p!=1:
            if p in st:
                ans = sc
                break
            else:
                st.add(p)
if ans==pc:
    pass
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:
import math
mod = 10 ** 9 + 7

n = int(input())
a = [int(i) for i in input().split()]
tmp = a[0]
set_v = a[0]
pairwise = True
setwise = False
for i in range(1, n):
    gcd = math.gcd(tmp, a[i])
    set_v = math.gcd(set_v, a[i])
    if gcd  > 1:
        pairwise = False
    elif gcd == 1:
        setwise = True
    tmp = (a[i] * tmp) // gcd
    tmp = tmp % mod
if pairwise == True:
    ans = 'pairwise coprime'
elif set_v == 1:
    ans = 'setwise coprime'
else:
    ans = 'not coprime'
print(ans)

Submission status: Wrong Answer

Solution code:
from math import gcd

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

setgcd = A[0]
for i in range(N):
    setgcd = gcd(setgcd,A[i])
is_set = True
if setgcd != 1:
    is_set=False

M = max(A)
is_prime=[1]*(M+1)#Mまで行きたい
is_inA=[0]*(M+1)
for i in range(N):
    is_inA[A[i]]=1

is_pair = True
is_prime[0]=0
is_prime[1]=0
for i in range(2,M+1):
    count = 0
    if is_inA[i]==1:
        count=1
    if is_prime[i]==1:
        for j in range(2*i,M+1,i):
            is_prime[j]=0
            if is_inA[j]==1:
                count+=1
    if count >= 2:
        is_pair = False

if is_pair:
    print("pairwise coprime")
elif is_set:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Wrong Answer

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

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

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

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

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


def lcm(a, b):
    return a*b//math.gcd(a, b)


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

    l = np.lcm.reduce(A)
    g = np.gcd.reduce(A)
    p = np.prod(A)

    if g == 1 and l == p:
        print('pairwise coprime')
    elif g == 1:
        print('setwise coprime')
    else:
        print('not coprime')

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline

n = int(input())
a = [int(item) for item in input().split()]

smallest_factor = [-1] * (10**6 + 10) 
for i in range(n, 1, -1):
    base = i
    j = 2
    while base * j <= (10**6 + 1):
        smallest_factor[base * j] = i
        j += 1

factor_count = [0] * (10**6 + 10)
is_pairwise = True
for item in a:
    val = item
    pset = set() 
    while smallest_factor[val] != -1:
        pset.add(factor_count[smallest_factor[val]])
        val //= smallest_factor[val]
    pset.add(val)
    for item in pset:
        factor_count[item] += 1
same_p = max(factor_count)
if same_p == 1:
    print("pairwise coprime")
elif same_p == n:
    print("not coprime")
else:
    print("setwise coprime")

Submission status: Wrong Answer

Solution code:
import sys
# sys.setrecursionlimit(100000)


def gcd(x: int, y: int) -> int:
    if x < y:
        x, y = y, x
    while y > 0:
        r = x % y
        x, y = y, r
    return x


def input():
    return sys.stdin.readline().strip()


def main():
    n = int(input())
    A = [int(i) for i in input().split()]
    set_gcd = A[0]
    is_pair_gcd = True
    for i in range(1, n):
        set_gcd = gcd(set_gcd, A[i])
        if is_pair_gcd and gcd(A[i], A[i - 1]) == 1:
            continue
        else:
            is_pair_gcd = False

    if is_pair_gcd:
        print("pairwise coprime")
    elif not is_pair_gcd and set_gcd == 1:
        print("setwise coprime")
    else:
        print("not coprime")

    return


if __name__ == "__main__":
    main()