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:
#!/usr/bin/env python3
import sys
import collections
from math import gcd
from functools import reduce

from random import randint

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

def find_gcd(list):
    x = reduce(gcd, list)
    return x

def find_lcm(list):
    x = reduce(lambda a,b: lcm(a,b)% MOD, list)
    return x

MOD = 10**9 + 7
def solve(N: int, A: "List[int]"):



    # q2 = True
    # for a in A:
    #     for b in A:
    #         if a!=b and gcd(a, b) != 1:
    #             q2 = False
    #             break

    q2 = True
    for i in range(N-1):
        _q = lcm(A[i], A[i+1]) == A[i] * A[i+1]
        q2 = q2 and _q

    q1 = reduce(gcd, A) == 1

    if q1 and q2:
        print('pairwise coprime')
    elif q1:
        print('setwise coprime')
    else:
        print('not coprime')
    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"

    solve(N, A)

if __name__ == '__main__':
    main()

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']
P=[0]*(10**6+1)
k=0
s=set()
for i in range(1,N+1):
    tmp=factorization(A[-i])
    if tmp&s==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:
N = int(input())
A = list(map(int, input().split()))


def gcd(x, y):
    while y != 0:
        x, y = y, x % y
    return x


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==[]:  # n=1のとき、[1,1]を返す
    #     arr.append([n, 1])

    return arr


# factorization(24)
## [[2, 3], [3, 1]]
##  24 = 2^3 * 3^1

gcdall = A[0]
for i in range(1, N):
    gcdall = gcd(gcdall, A[i])

# print(gcdall)
if gcdall > 1:
    print("not coprime")
    exit()

MAX = 10 ** 6 + 10
num = [False] * MAX
A = sorted(A)[::-1]
primeset = set()
for a in A:
    if a == 1:
        continue
    if num[a]:
        print("setwise coprime")
        exit()
    fact = factorization(a)
    for p, nn in fact:
        if p in primeset:
            continue
        primeset.add(p)
        for j in range(p + p, MAX, p):
            num[j] = True

print("pairwise coprime")

Submission status: Wrong Answer

Solution code:
import math
N = int( input() )
A = sorted( list(map(int, input().split())))
ans = A[0]
L = []
mod = 10 ** 7 + 9

cnt = 0
for i in range(1, N):
    ans = math.gcd(ans, A[i])
    if ans == 1:
      break
    else:
      cnt += 1
if ans != 1:
  ret = "not coprime"
else:
  if cnt > 0:
    ret = "setwise coprime"
  else:
    product = 1
    for a in A:
      product = ( product * a ) % mod
    ret = "pairwise coprime"
    for a in A:
      ans = math.gcd(a, product // a)
      if ans != 1:
        ret = "setwise coprime"
        break
print( ret )

Submission status: Wrong Answer

Solution code:
from math import gcd
def lcm(a):
    x = a[0]
    for i in range(1, len(a)):
        x = (x * a[i]) // gcd(x, a[i])
    return x

n = int(input())
a = list(map(int, input().split()))
lenn = n
na = a
flag = 0
mod = 67280421310721
for i in range(n):
    templ = []
    for j in range(0, lenn, 2):
        if(j + 1 >= lenn):
            templ.append(a[j]%mod)
        else:
            temp = gcd(a[j], a[j+1])%mod
            if(temp == 1):
                templ.append(((a[j]*a[j+1])%mod//temp)%mod)
            else:
                ans = na[0]
                for k in range(1, n):
                    ans = gcd(ans, na[k])
                if(ans == 1):
                    flag = 1
                else:
                    flag = 0
                break
    a = templ
    lenn = len(templ)
    if(lenn == 1):
        flag = 2
        break
if(flag == 2):
    print("pairwise coprime")
elif(flag == 1):
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Wrong Answer

Solution code:
import os
import heapq
import sys, threading
import math
import operator
from collections import defaultdict, deque
from io import BytesIO, IOBase
import math as mt

sys.setrecursionlimit(10 ** 5)
threading.stack_size(2 ** 27)


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


"""def pw(a,b):
    result=1
    while(b>0):
        if(b%2==1): result*=a
        a*=a
        b//=2
    return result"""


def inpt():
    return [int(k) for k in input().split()]


def main():
    MAXN = 1000001
    prime = [0] * MAXN
    prime[1] = 1
    for i in range(2, MAXN):
        prime[i] = i

    for i in range(4, MAXN, 2):
        prime[i] = 2

    for i in range(3, mt.ceil(mt.sqrt(MAXN))):
        if (prime[i] == i):
            for j in range(i * i, MAXN, i):
                if (prime[j] == j):
                    prime[j] = i
    n = int(input())
    ar = inpt()
    d = defaultdict(set)
    ok = True
    for i in ar:
        x = i
        while (x != 1):
            tp = prime[x]
            x = x // prime[x]
            d[tp].add(i)

    for i in d.keys():
        if (len(d[i]) > 1):
            ok = False
            break

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

    gcd = ar[0]
    for i in range(1, n):
        gcd = mt.gcd(gcd, ar[i])

    if (gcd == 1):
        print('setwise coprime')
    else:
        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, cnt])

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

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

import math
N = int(input())
A = list(map(int, input().split()))
ans = A[0]
primes = {x:1 for (x, y) in factorization(A[0])}
flag = True
for i in range(1, N):
    for (p, _) in factorization(A[i]):
        if p not in primes:
            primes[p] = 1
        else:
            primes[p] += 1
    #ans = math.gcd(ans, A[i])
if ans == 1:
    if flag:
        print("pairwise coprime")
    else:
        print("setwise coprime")
else:
    print("not coprime")

Submission status: Wrong Answer

Solution code:
import sys
from math import gcd


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 = []

    for i in range(n - 1):
        c = gcd(c, A[i + 1])
        b.append(gcd(A[i], A[i + 1]))

    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 math import gcd 
def primes(max_number):
    pr = list(range(3, max_number+1, 2))
    lpr = len(pr)
    for i,n in enumerate(pr):
        if n:
            if n*n > max_number:
                break
            for j in range(i+n, lpr, n):
                pr[j] = 0
    yield 2
    yield from[i for i in pr if i]

pr = [False]*(10**6+5)
for k in list(primes(10**6+1)):
    pr[k] = True
pr[2] = False

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

gu = False
for a in A:
    if pr[a]: continue
    if gu and a%2 == 0:
        break
    if (not gu) and (a%2 == 0):
        gu = True
else:
    print('pairwise coprime')
    exit()

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

Submission status: Wrong Answer

Solution code:
from math import gcd
from collections import defaultdict
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])
    arr = [a[0] for a in arr]
    if a == [1]:
        return []
    else:
        return arr

N = int(input())
A = [int(i) for i in input().split()]
dict_A = defaultdict(int)
dep_flag = False
for a in A:
    dict_A[a] += 1
    if a != 1 and dict_A[a] >= 2:
        dep_flag=True
coprime = True
divisors = set()
for i,a in enumerate(dict_A.keys()):
    if i == 0:
        g = a
    else:
        g = gcd(g,a)
    temp = factorization(a)
    if coprime:
        for t in temp:
            if t in divisors:
                coprime = False
            else:
                divisors.add(t)
if g==1 and coprime and dep_flag == False:
    print('pairwise coprime')
elif g==1 and dep_flag==False:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Wrong Answer

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

import math
tmp = A[0]

for i in range(1,N):
    gcd = math.gcd(tmp,A[i])
    
if gcd != 1:
    print("not coprime")
    exit()
    
tmp_list = [0]*(max(A)+1)

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

    #divisors.sort()
    return tmp_list

for i in range(N):
    make_divisors(A[i],tmp_list)

tmp_list
for i in range(2,max(A)+1):
    if tmp_list[i] > 1:
        print("setwise coprime")
        exit()
        
print("pairwise coprime")

Submission status: Wrong Answer

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

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


def solve(N,A):
  primes=[];
  isprime=[1 for i in range(0,1001)];
  isprime[1]=0;isprime[0]=0
  for i in range(2,1001):
    if isprime[i]:
      primes.append(i)
      j=2;
      while i*j<=1000:
        isprime[i*j]=0;
        j+=1
  A.sort();
  pc=1
  l=A[0]
  for i in range(1,N):
    if l==A[i] and l!=1:
      pc=0
    l=A[i];

  s=[0 for i in range(0,1001)]
  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 s[p]:
          pc=0
        s[p]=1
      #if a>=1000:
      #if a!=1:
        #if a in s2:
        #if s[a]:
        #  pc=0
        #s2.add(a)
        #s[a]=1


  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"))
def solve2(N,A):
  pc=1;
  for i in range(N):
    for j in range(i+1,N):
      pc*=(gcd(A[i],A[j])==1)
  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"))
#import random
#N=random.randrange(1,10)  
#A=[]
#for i in range(N):
#  A.append(random.randrange(1000000));
#  print(A[i])
solve(N,A)
#solve2(N,A)
#solve(2,[1,1])
#solve2(2,[1,1])

Submission status: Wrong Answer

Solution code:
from fractions import gcd
import sys
input = lambda : sys.stdin.readline().rstrip()

n = int(input())
As = map(int, input().split(" "))

is_set = False
out_min = 10**6+1

first = True
A0 = As[0]

def fctr1(n): 
    f=[]
    c=0
    r=int(n**0.5)
    for i in range(2,r+2):
        if 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


for i in range(1, n):
    if i == 1:
        g = gcd(A0, As[i])
    else:
        g = gcd(g, As[i])

    if g == 1:
        is_set = True
        break


hontai_flags = [False] * out_min
#flags = [False] * out_min

if is_set:
    is_pair = True
    
    #for A in As:
    #    hontai_flags[A] = True

    As = list(set(As))
    n = len(As)

    #for i in range(1, out_min):
    #    if hontai_flags[i]:
    #        A = i

    #        for A in As:
    #            r = 2  
    #            while True:
    #                A0 = A*r
    #                if out_min <= A0:
    #                    break

    #                cur_flag = hontai_flags[A0]
    #                if cur_flag:
    #                    is_pair = False
    #                    break
    #                #flags[A0] = True

    #                r += 1

    #        if not is_pair:
    #            break

    for i in range(n):
        ds = fctr1(As[i])
        for d, _ in ds:
            if hontai_flags[d]:
                is_pair = False
                break
            hontai_flags[d] = True
else:
    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 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

d = {}
N = int(input())
A = list(map(int,input().split()))
for ai in A:
	for prime in factorization(ai):
		if prime[0] in d.keys():
			d[prime[0]] += 1
		else:
			d[prime[0]] = 1
if max(d.values()) == N:
	print("not coprime")
elif max(d.values()) == 1:
	print("pairwise coprime")
else:
	print("setwise coprime")

Submission status: Wrong Answer

Solution code:
from math import gcd
def lcm(a):
    x = a[0]
    for i in range(1, len(a)):
        x = (x * a[i]) // gcd(x, a[i])
    return x

n = int(input())
a = list(map(int, input().split()))
lenn = n
na = a
flag = 0
mod = 10**9 + 7
for i in range(n):
    templ = []
    for j in range(0, lenn, 2):
        if(j + 1 >= lenn):
            templ.append(a[j]%mod)
        else:
            temp = gcd(a[j], a[j+1])%mod
            if(temp == 1):
                templ.append(((a[j]*a[j+1])%mod//temp)%mod)
            else:
                ans = na[0]
                for k in range(1, n):
                    ans = gcd(ans, na[k])
                if(ans == 1):
                    flag = 1
                else:
                    flag = 0
                break
    a = templ
    lenn = len(templ)
    if(lenn == 1):
        flag = 2
        break
if(flag == 2):
    print("pairwise coprime")
elif(flag == 1):
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np
sys = sys.stdin.buffer.readline
N = int(input())
A = np.array(list(map(int, input().split())))


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


def factorization(n):
    arr = []
    temp = n
    for i in range(2, n):
        if i * i > n:
            break
        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)
    # if temp != 1:
    #     arr.append([temp, 1])
    # if arr == []:
    #     arr.append([n, 1])
    return arr


# A = sorted(A)
# print(f'{A=}')
# print(primes)
arr = set(factorization(A[0]))
S = set([])
for a in A:
    # print(f'{a=}')
    tmp = set(factorization(a))
    # print(f'{arr=}, {tmp=}')
    arr = arr & tmp
    S = S | tmp
    # print(f'{arr=}, {S=}')

print(A)
# print(np.count_nonzero(A % 2))
if len(arr) != 0:
    print('not coprime')
else:
    for s in S:
        # print(A % s, s)
        if np.count_nonzero(A % s) >= 2:
            exit()
        print('setwise coprime')
    print('pairwise coprime')

Submission status: Wrong Answer

Solution code:
def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]
    
import heapq

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

P=primes(1000000)
lP=len(P)
p_lis=[0]*lP

f_pair=True
f_set=True

for _ in range(N):
    a=heapq.heappop(A)
    
    for pi,p in enumerate(P):
        if a%p==0:
            a%=p
            p_lis[pi]+=1
            if p_lis[pi]==2:
                f_pair=False
            if p_lis[pi]==N:
                f_set=False
        if a==0:
            break
    if f_pair and f_set == False:
        break
#print(p_lis)

if f_pair:
    print('pairwise coprime')
elif f_set:
    print('setwise coprime')
else:
    print('not coprime')
    
"""
6 :[1,1,0,0,]
10:[1,0,1,0,]
15:[0,1,1,0,]

"""

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**6)]
pc_flg=True

cnt_one=0
for i in range(N):
    if A[i]==1:
        cnt_one+=1

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

if cnt_one!=0:
    if len(A)==len(set(A))+cnt_one-1:
        pc_flg=True



x = A[0]

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

A = list(set(A))

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


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

Submission status: Wrong Answer

Solution code:
n = int(input())
A = list(map(int, input().split()))
min_A = min(A)
one_num = 0

from sys import exit
if min_A == 1:
    one_num = A.count(1)
    A = [num for num in A if num != 1]

from collections import Counter
prime_list = []
for num in range(2, 10**3 + 1):
    for prime in prime_list:
        if num % prime == 0:
            break
    else:
        prime_list.append(num)
#print(prime_list)


cnt = Counter()
set_primes = set(prime_list)
for a in A:
    soinsu = []
    flg = True
    for prime in prime_list:
        if prime ** 2 > a:
            break
        if a % prime == 0:
            flg = False
            cnt[prime] += 1
            if a // prime in set_primes and prime**2 != a:
                cnt[a // prime] += 1
    if flg:
        cnt[a] += 1
"""
    for num in list(set(soinsu)):
        cnt[num] += 1

"""
print(cnt)

if len(cnt) == 0:
    print("pairwise coprime")
    exit()

max_cnt = max(cnt.values())
if max_cnt == 1:
    print("pairwise coprime")
elif max_cnt == n and one_num == 0:
    print("not coprime")
else:
    print("setwise coprime")

Submission status: Wrong Answer

Solution code:
from random import randint

def miller_rabin(n, rep=100): #random.randint
    if n == 2: return True
    if n == 1 or n % 2 == 0: return False
    d = (n - 1) // 2
    while d % 2 == 0:
        d //= 2
    for k in range(rep):
        a = randint(1, n - 1)
        t = d
        y = pow(a, t, n)
        while t != n - 1 and y != 1 and y != n - 1:
            y = (y * y) % n
            t *= 2
        if y != n - 1 and t % 2 == 0:
            return False
    return True

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

def pollard_rho(n): #gcd, factorize, miller_rabin
    res = []
    stack = [n]
    while stack:
        tmp = stack.pop()
        if tmp < 10**3:
            res.extend(factorize(tmp))
            continue
        if miller_rabin(tmp):
            res.append(tmp)
            continue
        seed = 1
        while True:
            x, y, d = 2, 2, 1
            f = lambda x: (x**2 + seed) % tmp
            while d == 1:
                x = f(x)
                y = f(f(y))
                d = gcd(abs(x - y), tmp)
            if d != n:
                break
            seed += 1
        stack.append(d)
        stack.append(tmp // d)
    return sorted(res)

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

from collections import Counter, defaultdict

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

D = set()

flag = True
for i in range(N):
    if A[i] == 1:
        continue
    C = set(pollard_rho(A[i]))
    for k in C:
        if k in D:
            flag = False
            break
        else:
            C.add(k)

if flag:
    print('pairwise coprime')

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

Submission status: Wrong Answer

Solution code:
import sys
import math
from functools import reduce


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


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


def main():
    input = sys.stdin.buffer.readline
    n = int(input())
    a = list(map(int, input().split()))
    a.sort()
    if gcd_list(a) != 1:
        print("not coprime")
    else:
        a = set(a)
        ans = False
        for i in range(2, 10 ** 3 + 1):
            checked = False
            for j in range(i, 10 ** 6 + 1, i):
                if j in a:
                    if checked == True:
                        ans = True
                    else:
                        checked = True
        print("setwise coprime" if ans else "pairwise coprime")


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import math
from functools import reduce

N  = int(input())
a = list(map(int,input().split()))
temp = 0


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

for i in range(N):
    for l in range(N):
        if a[i] % a[l] != 1:
            temp += 1
if temp == 0:
    print('pairwise coprime')
elif gcd_list(a) == 1:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Wrong Answer

Solution code:
import math

def divisorGenerator(n):
    large_divisors = []
    for i in range(1, int(math.sqrt(n) + 1)):
        if n % i == 0:
            yield i
            if i*i != n:
                large_divisors.append(n // i)
    for divisor in reversed(large_divisors):
        yield divisor

if __name__ == '__main__':

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

    gcd_ = math.gcd(A[0], A[1])
    for i in range(2, len(A)):
        gcd_ = math.gcd(gcd_, A[i])

    set_wise = False
    if gcd_ == 1:
        set_wise = True
    if not(set_wise):
        print("not coprime")
    else:
        pairwise = False
        divs = dict()
        for i in A:
            res = list(divisorGenerator(i))
            for el in res:
                if el != 1:
                    if not(el in divs):
                        divs[el] = 0
                    divs[el] += 1
        for value in divs.values():
            if value == 1:
                pairwise = True
        if pairwise:
            print("pairwise coprime")
        else:
            print("set coprime")

Submission status: Wrong Answer

Solution code:
import math

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

def pairwise_or_not():
  for i in range(N):
    for k in range(i):
      if math.gcd(s[i],s[k])!=1:
        return 'No'
  return 'Yes'

def setwise_or_not():
  for i in p:
    c=0
    for k in s:
      if k%i==0:
        c+=1
      if c>1:
        return 'No'
  return 'Yes'

if pairwise_or_not()=='Yes':
  print('pairwise coprime')
elif setwise_or_not()=='Yes':
  print('setwise coprime')
else:
  print('not coprime')

Submission status: Wrong Answer

Solution code:
import sys
import math

def soinsu(dic, x):
  i = 2
  while i*i <= x:
    if x % i == 0 and i in dic.keys():
      print(i, dic)
      return False
    
    while x % i == 0:
      dic.setdefault(i, 0)
      dic[i] += 1
      x //= i
      
    i += 1
      
      
  if x == 1:
    return True
  
  if x in dic.keys():
    return False
  
  dic.setdefault(x, 1)
  return True
    

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

flag = False
for i in range(n):
  if not soinsu(dic, a[i]):
    flag = True
    break

if not flag:
  print("pairwise coprime")
  sys.exit()
  
tmp = a[0]
for i in range(1,n):
  tmp = math.gcd(tmp, a[i])
  
if tmp == 1:
  print("setwise coprime")
else:
  print("not coprime")

Submission status: Wrong Answer

Solution code:
import math
from functools import reduce

def primes(N): 
  A=list(range(2,N+1))
  p=list()
  while A[0]**2<=N:
      tmp=A[0]
      p.append(tmp)
      A=[e for e in A if e%tmp!=0]
  primes = p+A
  
  return primes

def gcd(*numbers):
    return reduce(math.gcd, numbers)
  
def test(N):
  i=2
  ans=dict()
  n=N
  while i*i <=N:
      while n%i==0:
          n=n//i
          if i in ans:
              ans[i]+=1
          else:
              ans[i]=1
      i+=1
  if n!=1:
      ans[n]=1
  return list(ans.items())

dict = {}
for i in primes(10**6):
  dict[i] = 0
count = 0
n = int(input())
A = list(map(int, input().split()))
if gcd(A) != 1:
  print('not coprime')
else:
  for i in range(n):
    a = test(A[i])
    for j in a:
      dict[j[0]] += 1
    if dict[j[0]] >= 2:
      count = 1
      break
  if count == 1:
    print('setwise coprime')
  else:
    print('pairwise coprime')

Submission status: Wrong Answer

Solution code:
import sys
import bisect as bi
import math
from collections import defaultdict as dd
import heapq
import itertools
input=sys.stdin.readline
from random import randint
##import numpy as np
##sys.setrecursionlimit(10**7)
mo=10**9+7
def cin():
    return map(int,sin().split())
def ain():            
    return list(map(int,sin().split()))
def sin():
    return input()
def inin():
    return int(input())
##def gcd(a,b): 
##    if a == 0: 
##        return b 
##    return gcd(b % a, a)
prime1=[]
def SieveOfEratosthenes(n): #list of primes upto n
    global prime1
    prime1 = [True for i in range(n+1)] 
    p = 2
    while (p * p <= n): 
        if (prime1[p] == True): 
            for i in range(p * p, n+1, p): 
                prime1[i] = False
        p += 1
    f=[]
    for p in range(2, n): 
        if prime1[p]: 
            f.append(p)
    return f

def lcm(a,b): 
    return (a*b) // math.gcd(a,b) 
for _ in range(1):
    n=inin()
    l=ain()
    f1,f2=0,0
    gc=l[0]
    d=dd(int)
    if(l.count(1)>0):gc=1
    else:
        for i in range(1,n):
            gc=math.gcd(gc,l[i])
    if(gc!=1):print("not coprime")
    else:
        lp=SieveOfEratosthenes(int(max(l)**(0.5))+2)
        for i in l:
            if(i!=1):
                for j in lp:
                    if(i%j==0):
                        if(d[j]==1):
                            f1=1
                            break
                        d[j]=1
            if(f1):break
        if(f1):
            print("setwise coprime")
        else:
            print("pairwise coprime")
        
        
    
    
    

 
    
    
    
    
        
        
    
    
    
    


    




##def msb(n):n|=n>>1;n|=n>>2;n|=n>>4;n|=n>>8;n|=n>>16;n|=n>>32;n|=n>>64;return n-(n>>1) #2 ki power
##def pref(a,n,f):             
##    pre=[0]*n
##    if(f==0):         ##from beginning
##        pre[0]=a[0]
##        for i in range(1,n):
##            pre[i]=a[i]+pre[i-1]
##    else:              ##from end
##        pre[-1]=a[-1]
##        for i in range(n-2,-1,-1):
##            pre[i]=pre[i+1]+a[i]
##    return pre
##maxint=10**24 
##def kadane(a,size): 
##    max_so_far = -maxint - 1
##    max_ending_here = 0
##       
##    for i in range(0, size): 
##        max_ending_here = max_ending_here + a[i] 
##        if (max_so_far < max_ending_here): 
##            max_so_far = max_ending_here 
##  
##        if max_ending_here < 0: 
##            max_ending_here = 0   
##    return max_so_far
##def power(x, y):
##    if(y == 0):return 1
##    temp = power(x, int(y / 2))%mo
##    if (y % 2 == 0):return (temp * temp)%mo 
##    else:
##        if(y > 0):return (x * temp * temp)%mo 
##        else:return ((temp * temp)//x )%mo