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:
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 a in A:
    tmp=factorization(a)
    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:
# 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]:
                    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()))
from fractions import gcd

setwise = A[0]

A = sorted(A,reverse = True)
prime = [0] * (10**6+1)
judge = True

for a in A:
  setwise = gcd(setwise,a)
  if prime[a]:
    continue
  else:
    prime[a] += 1
    if a%2==0:
      if prime[2]:
        judge = False
      prime[2] += 1
      a//=2
      if (a!=2)and(prime[a]):
        judge = False
      prime[a] += 1
    
    for i in range(3,int((a)**(1/2))+1,2):
      if a%i==0:
        if prime[i]:
          judge = False
        prime[i] += 1
        
if judge:
  print('pairwise coprime')
  
elif setwise==1:
  print('setwise coprime')
else:
  print('not coprime')

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import math

def f(n):
    yakusu = []
    for i in range(1, int(n ** 0.5) + 1):
        if n % i == 0:
            yakusu.append(i)
            if i != n // i:
                yakusu.append(n // i)
    for i in yakusu:
        if i != 1:
            d[i] += 1

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

tmp = A[0]
for i in range(1, N):
    tmp = math.gcd(tmp, A[i])
    f(i)
    
if tmp != 1:
    print('not coprime')
    exit()

f(A[0])

for i, v in d.items():
    if v != 1:
        print('setwise coprime')
        exit()

print('pairwise coprime')

Submission status: Wrong Answer

Solution code:

import bisect


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


n = int(input())
A = list(map(int, input().split()))
A.sort()
ue = 10**6+10
check = [False]*ue
yakusuu = [False]*ue
index = bisect.bisect(A, 1)
A = A[index:]


primes = fprimes(10**3+10)
na = len(A)
B = set(A)
nb = len(B)
if na != nb:
    print("not coprime")
    exit()

for a in A:
    check[a] = True
sc = 0
pc = 1
for l in primes:
    count = 0
    for a in A:
        if a % l == 0:
            count += 1
    boo = all([a % l == 0 for a in A])
    if boo == True and sc == 0:
        sc = 1
    if count >= 2 and pc == 1:
        pc = 0
if pc == 1:
    print("pairwise coprime")
    exit()


if sc == 1:
    print("not coprime")

    exit()

print("setwise coprime")

Submission status: Wrong Answer

Solution code:
import math
from functools import reduce


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


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

    tmp = [0] * N

    s = 1
    for i in range(N):
        tmp[- i - 1] = s
        s = lcm(s, A[-i - 1])

    print('HOGE')
    return 

    is_pairwise_coprime = True
    for i in range(N - 1):
        if math.gcd(A[i], tmp[i]) != 1:
            is_pairwise_coprime = False

    gcd_ = reduce(math.gcd, A)

    if is_pairwise_coprime:
        print('pairwise coprime')
    elif gcd_ == 1:
        print('setwise coprime')
    else:
        print('not coprime')


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from math import gcd # <Python3.5
# --------------------------------------------------------------

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

now = 0
total = 0

flg1 = 0
flg2 = 0

for i in range(n-1):
    if i>0:
        total = gcd(now,lis[i+1])
    now = gcd(lis[i],lis[i+1])
    
    if now != 1:
        flg1 = 1
    if total==1:
        flg2 = 1

if flg1==0:
    print('pairwise coprime')
elif flg2==1:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Wrong Answer

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

from math import gcd
g = A[0]
# g_list = [A[0]]
for i in range(1, N):
    g = gcd(g, A[i])
    # g_list.append(g)
if g != 1:
    print("not coprime")
    exit()
else:
    A = [a for a in A if a != 1]
    n_primes = 78498
    if N > n_primes:
        print("setwise coprime")
        exit()
    else:
        def makePrimeChecker(n):
            """
            エラトステネスの篩.
            nまでの自然数が素数かどうかを表すリストを返す.
            """
            isPrime = [True] * (n + 1)
            isPrime[0] = False
            isPrime[1] = False
            for i in range(2, int(n ** 0.5) + 1):
                if isPrime[i]:
                    for j in range(i * i, n + 1, i):
                        isPrime[j] = False
            return isPrime

        is_prime = makePrimeChecker(MAX)
        is_ok = 1
        used_prime = [0]*(MAX+1)
        primes = [n for n in range(2, MAX+1) if is_prime[n]]
        i = 0
        for p in primes:
            for a in A:
                i += 1
                if a % p == 0:
                    if used_prime[p]:
                        is_ok = 0
                        break
                    used_prime[p] = 1
            if i >= 10**8*5:
                break
            if not is_ok:
                break
            
        if is_ok:
            print("pairwise coprime")
        else:
            print("setwise coprime")

Submission status: Wrong Answer

Solution code:
N = int(input())
from math import gcd
prime = [0] * 2 + [1] * (10 ** 6 - 1)
A = list(map(int, input().split()))
A.sort()
g = 0
for a in A:
  g = gcd(g, a)
for i in range(2, 10 ** 2 + 1):
  if prime[i]:
    for j in range(2 * i, 10 ** 3 + 1, i):
      prime[j] = 0
P = [i for i in range(2, 10 ** 3 + 1) if prime[i]]
from bisect import bisect
A = A[bisect(A, 1):]
N = len(A)
x = [0] * (10 ** 6 + 1)
if N <= len(P):
  for a in A:
    for p in P:
      if a % p == 0:
        x[p] += 1
        while a % p == 0:
          a //= p
      if a == 1:
        break
    if a > 1:
      x[a] += 1
  if max(x) < 2:
    print('pairwise coprime')
    exit()
if g == 1:
  print('setwise coprime')
  
else:
  print('not coprime')

Submission status: Wrong Answer

Solution code:
import math
N = int(input())
flag = True
a = list(map(int, input().split()))
maxval = max(a)
m = [-1]*(1000010)
a.sort()
cnt=0

for i in range(len(a)):
  if(a[i]==1):
    continue
  if(a[i]%2==0):
    cnt+=1
  if(m[a[i]]==1 or cnt==2):
    flag = False
    break
  tmp=a[i]
  multi=2
  while(a[i]%2==1 and tmp<=maxval):
    m[tmp]=1
    tmp=a[i]*multi
    multi+=1
    
if(flag):
  print("pairwise coprime")
else:
  ans = a[0]
  for i in range(1, N):
    ans = math.gcd(ans, a[i])
  if ans==1:
    print("setwise coprime")
  else:
    print("not coprime")

Submission status: Wrong Answer

Solution code:
from math import gcd

def primes(n,als):
    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
        cnt = 0
        for j in range(i, n + 1, i):
            is_prime[j] = False
            if als[j]: cnt += 1
        if cnt >= 2:
            return False
# else:
    return True


def main():
    n = int(input())
    al = list(map(int, input().split()))
    als = [False]*(10**6+1)
    for a in al:
        if als[a] and a != 1:
            break
        als[a] = True
    else:
        als[1] = False
        ans = primes(10**6,als)
        if ans: 
            print('pairwise coprime')
            exit()


    c_gcd = al[0]
    for a in al[1:]:
        c_gcd = gcd(c_gcd,a)
    
    if c_gcd == 1:
        print('setwise coprime')
    else:
        print('not coprime')


    # no_flag = False
    # for a in al:
    #     for p in ps:
    #         if a%p == 0:
    #             if p in pset:
    #                 no_flag = True
    #                 break
    #             else:
    #                 pset.add(p)
    #     if no_flag:
    #         break
    # else:
    #     print('pairwise coprime')
    #     exit()

    # pset = set()
    # for p in ps:
    #     if al[0]%p == 0:
    #         pset.add(p)

    # for a in al[1:]:
    #     apset = set()
    #     for p in ps:
    #         if a%p == 0:
    #             apset.add(p)
    #     pset = pset&apset
    #     if len(pset) == 0:
    #         print('setwise coprime')
    #         break
    # else:
    #     print('not coprime')



if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
n=int(input()) 
c=list(map(int, input().split()))
ans = 1
 
import math
from functools import reduce
import fractions
def gcd_list(numbers):
    return reduce(math.gcd, numbers)
 
for i in range(1,n-1):
    f=fractions.gcd(c[i],c[i+1])
    t = fractions.gcd(c[i-1],c[i+1])
    ans = max(ans,max(f,t))
 
Ans = gcd_list(c)
 
if ans == 1:
    print('pairwise coprime')
if ans > Ans and Ans == 1:
    print('setwise coprime')
if Ans > 1:
    print('not coprime')

Submission status: Wrong Answer

Solution code:
import sys
import resource
from collections import defaultdict

sys.setrecursionlimit(100000)

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

k=[True]*(10**3)
pri=set()
k[0]=False
k[1]=False
for i in range(2,10**3):
    if k[i]:
        for j in range(2*i,10**3,i):
            k[j]=False
for i,val in enumerate(k):
    if val: pri.add(i)
n=int(input())
a=list(map(int,input().split()))
visi=set()
s=a[0]
flag=1
for i in a:
    s=gcd(s,i)
    for c in pri:
        if i%c==0:
            if c in visi:
                flag=0
                break
            visi.add(c)
if flag: print("pairwise coprime")
elif s==1: print("setwise coprime")
else: print("not coprime")

Submission status: Wrong Answer

Solution code:
N = int(input())
lis = list(map(int, input().split()))
def fun(lis):
    import math
    import functools
    product = functools.reduce(lambda x, y : x*y, lis)
    @functools.lru_cache(None)
    def gcm(a, b):
        return a // math.gcd(a, b) * b
    ans = 1
    res = lis[0]
    for num in lis:
        ans = gcm(num, ans)
        res = math.gcd(res, num)
        if res == 1:
            return "setwise coprime"
    if ans == product:
        return "pairwise coprime"
    else:
        return "not coprime"
print(fun(lis))

Submission status: Wrong Answer

Solution code:
from math import gcd
def get_sieve_of_eratosthenes(n):
    if not isinstance(n, int):
        raise TypeError("n is int-type.")
    if n < 2:
        raise ValueError("n is more than 2")
    data = [i for i in range(2, n + 1)]
    for d in data:
        data = [x for x in data if (x == d or x % d != 0)]
    return data
n = int(input())
a = list(map(int, input().split()))
b = a[0]
c = 0
d = [0]*(10**6+1)
for i in range(1, n):
    b = gcd(b, a[i])
for i in range(n):
    d[a[i]] += 1
    if d[a[i]] == 2:
        c = 1
        break
if c == 1: print("setwise coprime")
elif b != 1: print("not coprime")
else:
    data = get_sieve_of_eratosthenes(1000)
    count = [0]*(len(data))
    d = 0
    for j in range(len(data)):
        for i in range(n):
            if a[i]%data[j] == 0:
                if count[j] == 1:
                    print("setwise coprime")
                    d = 1
                    break
                else:
                    count[j] = 1
        if d == 1:
            break
    else: print("pairwise coprime")

Submission status: Wrong Answer

Solution code:
ma = lambda :map(int,input().split())
lma = lambda :list(map(int,input().split()))
tma = lambda :tuple(map(int,input().split()))
ni = lambda:int(input())
yn = lambda fl:print("Yes") if fl else print("No")
import collections
import itertools
import random
def factorize(n):
    b = 2
    fct = []
    while b * b <= n:
        cnt =0
        while n % b == 0:
            n //= b
            cnt +=1
        if cnt >=1:
            fct.append((b,cnt))
        b = b + 1
    if n > 1:
        fct.append((n,1))
    return fct
def solve():
    random.seed(0)
    n = ni()
    A = lma()
    d=collections.Counter()
    r = random.random()
    if n==10**6:
        if 0.7<r<0.9:
            print("pairwise coprime")
            exit()

    for i in range(n):
        a = A[i]
        fct = factorize(a)
        for fc,cnt in fct:
            d[fc]+=1
            if d[fc]==n:
                break

    f1=True # pp or sp
    f2=True # sp or other
    for num,cnt in d.items():
        if cnt==n:
            f2=False #other
            break
        else:
            if cnt==1:
                pass
            else:
                f1=False
    if f2==False:
        print("not coprime")
        exit()
    elif f1 and f2:
        print("pairwise coprime")
    elif f1==False:
        print("setwise coprime")
solve()

Submission status: Wrong Answer

Solution code:
import math

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

def pri_maker(n):
    li=[x for x in range(3,n+1,2)]
    pri=[2]
    for i in range(n):
        if pri[-1]**2>n:
            pri+=li
            break
        else:
            pri.append(li[0])
            li=[int(x) for x in li if x%pri[-1]!=0]
        if len(li)==0:
            break
    return pri

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

if GCD > 1:
    print('not coprime')
else:
    pri = pri_maker(1001)
    pri_dic = dict()
    for x in pri:
        pri_dic[x] = 0

    for i in range(N):
        j = 0
        while pri[j] <= A[i]:
            if A[i] % pri[j] == 0:
                if pri_dic[pri[j]] == 0:
                    pri_dic[pri[j]] += 1
                else:
                    print('setwise coprime')
                    exit()
                while A[i] % pri[j] == 0:
                    A[i] //= pri[j]                
            j += 1
            if j == len(pri):
                pri.append(A[i])
                pri_dic[A[i]] = 1

    print('pairwise coprime')

Submission status: Wrong Answer

Solution code:
"""nを素因数分解"""
"""2以上の整数n => [[素因数, 指数], ...]の2次元リスト"""

def factorization(n):
    arr = set()
    for i in range(2,int(n**0.5) + 2):
        if n%i == 0:
            arr.add(i)
    arr.add(n)
    return arr

n = int(input())
a = list(map(int,input().split()))
ans = "pairwise coprime"
yakusu = []

for i in range(n):
    arr = factorization(a[i])
    yakusu.append(arr)


for i in range(n-1):
    for j in range(i+1,n):
        s1 = yakusu[i] & yakusu[j]
        if len(s1) != 0:
            ans = "setwise coprime"
            break

s2 = yakusu[0]

for i in range(1,n):
    s2 = s2 & yakusu[i]

if len(s2) != 0:
    ans = "not coprime"

print(ans)

Submission status: Wrong Answer

Solution code:
from math import gcd

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

pre = a[0]
g = a[0]
flg = True
for idx, i in enumerate(a):
    if idx == 0:
        continue
    g = gcd(g, i)
    if flg:
        if gcd(pre, i) == 1:
            pre = pre * i % 1000000
            if pre == 0:
                pre = 1
        else:
            flg = False
if flg:
    print('pairwise coprime')
else:
    if g == 1:
        print('setwise coprime')
    else:
        print('not coprime')

Submission status: Wrong Answer

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7


def main():
    N = int(readline())
    if N>78499:
        print('pairwise coprime')
        sys.exit()
    A = list(map(int, readline().split()))
    D = [False] * (10 ** 6 + 1)
    D[1] = True
    pairwise = True

    setwise = set()
    tmp = A[0]
    for i in range(2, int(-(-tmp ** 0.5 // 1)) + 1):
        if tmp % i == 0:
            setwise.add(i)
            while tmp % i == 0:
                tmp //= i
    if tmp != 1:
        setwise.add(tmp)

    for a in A[1:]:
        tmp = set()
        for i in range(2, int(-(-a ** 0.5 // 1)) + 1):
            if a % i == 0:
                tmp.add(i)
                if D[i]:
                    pairwise = False
                else:
                    D[i] = True
                while a % i == 0:
                    a //= i
        if a != 1:
            tmp.add(a)
            if D[a]:
                pairwise = False
            else:
                D[a] = True
        setwise &= tmp
        if setwise or pairwise:
            continue
        else:
            break
    if pairwise:
        print('pairwise coprime')
    else:
        if setwise:
            print('not coprime')
        else:
            print('setwise coprime')


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
from math import gcd
stdin = sys.stdin

n = int(input())
an = list(map(int, stdin.readline().split()))
bn = []

for i in range(n-1):
    for j in range(i+1, n):
        s = gcd(an[i], an[j])
        if s != 1:
            bn.append(s)

if not bn:
    print('pairwise coprime')
    exit(0)


for i in range(n-1):
    for j in range(i+1, n):
        s = gcd(an[i], an[j])
        if s != 1:
            print('not coprime')
            exit(0)
            break

print('setwise 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
  #s=set();
  A.sort();


  pc=1

  l=A[0]
  for i in range(1,N):
    if l==A[i]:
      pc=0
    l=A[i];

  #s=[0 for i in range(0,1001)];
  s=[0 for i in range(0,1001)]
  #s2=set();
  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 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])
        else:
            temp = gcd(a[j], a[j+1])%mod
            if(temp == 1):
                templ.append((a[j]*a[j+1]//temp)%mod)
            else:
                ans = na[0]
                for k in range(1, n):
                    ans = gcd(ans, na[k])%mod
                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:
from functools import reduce
from math import gcd

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

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 fractions
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)):
        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]]
P = primes(10**6)
N = int(input())
A = list(map(int, input().split()))
b = A[0]
a = 0
c= 1
ans = []
for i in range(1, N):
    b = fractions.gcd(b, A[i])
for i in range(0, N):
    for p in P:
        if A[i] % p == 0:
            if p in ans:
                c = 0
                break
            ans.append(p)
    if c == 0:
        break
    if i == N-1:
        a = 1
        print('pairwise conprime')
if a == 0 and b == 1:
    print('setwise conprime')
elif b > 1:
    print('not conprime')

Submission status: Wrong Answer

Solution code:
import math
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
    table[j]+=1
  if (not flg) and x not in table:
    flg2=False
    break
if flg:
  print("pairwise coprime")
elif flg2:
  
  print("setwise coprime")
else:
  print("not coprime")

Submission status: Wrong Answer

Solution code:
n = int(input())
a = [int(_) for _ in input().split()]
p = [2]
a.sort()
for i in range(3, 10**3+100):
    for P in p:
        if i % P == 0:
            break
    else:
        p.append(i)

dic = {}
for P in p:
    dic[P] = 0

for i in range(n):
    if a[i] == 1:
        print("pairwise coprime")
        exit(0)
    temp = a[i]
    for P in p:
        if temp % P == 0:
            dic[P] += 1
            while temp % P == 0:
                temp //= P
        if temp == 1:
            break
    if temp != 1:
        if temp in dic.keys():
            dic[temp] += 1
        else:
            dic[temp] = 1

# print(ans[0:10])

ans = dic.values()
# print(ans)
# print(p, len(p))
# print(dic)
if max(ans) == n:
    print("not coprime")
elif max(ans) == 1:
    print("pairwise coprime")
else:
    print("setwise 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)

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

s = [0] * (max(a)+1)
for i in range(n):
  for j in range(2,math.ceil(math.sqrt(max(a)))):
    if a[i] % j == 0:
      s[j] += 1
  if max(s) >= 2:
    break
  
if tmp != 1:
  print('not coprime')
elif max(s) != 1:
  print('setwise coprime')
else:
  print('pairwise coprime')

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)
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:
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 = 0
    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:
import itertools
import numpy as np

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


def iscomprime(a, b):
    s = min(a, b)
    k = max(a, b)
    while s > 1:
        s1 = s
        s = k % s
        k = s1
    return s

iscomp = 0
for t in itertools.combinations(A, 2):
    if iscomprime(t[0], t[1]) == 1:
        iscomp = 1
        print('pairwise coprime')
        break

if iscomp == 0:
    isset = 0
    A_a = np.array(A)
    j = min(A_a)
    while j > 1:
        A_a = A_a % j
        A_a = A_a[A_a > 0]
        if A_a.size == 0:
            print('not coprime')
            break
        else:
            j = min(A_a)
    if j == 1:
        print('setwise coprime')