Problem:


Score : 500 points

Problem Statement

We have N integers. The i-th number is A_i.

\{A_i\} is said to be pairwise coprime when GCD(A_i,A_j)=1 holds for every pair (i, j) such that 1\leq i < j \leq N.

\{A_i\} is said to be setwise coprime when \{A_i\} is not pairwise coprime but GCD(A_1,\ldots,A_N)=1.

Determine if \{A_i\} is pairwise coprime, setwise coprime, or neither.

Here, GCD(\ldots) denotes greatest common divisor.

Constraints

2 \leq N \leq 10^6

1 \leq A_i\leq 10^6

Input

Input is given from Standard Input in the following format:

N
A_1 \ldots A_N

Output

If \{A_i\} is pairwise coprime, print pairwise coprime; if \{A_i\} is setwise coprime, print setwise coprime; if neither, print not coprime.

Sample Input 1

3
3 4 5

Sample Output 1

pairwise coprime

GCD(3,4)=GCD(3,5)=GCD(4,5)=1, so they are pairwise coprime.

Sample Input 2

3
6 10 15

Sample Output 2

setwise coprime

Since GCD(6,10)=2, they are not pairwise coprime. However, since GCD(6,10,15)=1, they are setwise coprime.

Sample Input 3

3
6 10 16

Sample Output 3

not coprime

GCD(6,10,16)=2, so they are neither pairwise coprime nor setwise coprime.



Sample input:
3
3 4 5


Sample output:
pairwise coprime

Submission status: Wrong Answer

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

pl =[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 fact(n):
    arr = []
    temp = n
    for i in pl:
        if temp%i==0:
            while temp%i==0:
                temp //= i
            arr.append(i)
 
    if temp!=1:
        arr.append(temp)
 
    if arr==[]:
        arr.append(n)
 
    return arr

alb = [i for i in al if i != 1]
bb = len(alb)

if bb >168:
    import math
    a = al[0]
    for i in range(1,n):
        if math.gcd(a,al[i]) ==1:
            print("setwise coprime")
            exit()
        a *=al[i]
    print("not coprime")
    
else:
    dp = [0]*(10**6)
    for i in range(bb):
        for j in fact(alb[i]):
            dp[j] +=1
    if max(dp)<=1:
        print("pairwise coprime")
    elif max(dp) ==n:
        print("not coprime")
    else:
        print("setwise coprime")

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

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:
import math

def sieve(data,num):
    return [x for x in data if (x % num != 0)]

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

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

prime = [i for i in prime if M > i]

# 累積GCD
left = [0] * (n + 1)
right = [0] * (n + 1)
for i in range(n):
    left[i + 1] = (math.gcd(left[i], a[i]))
    right[n - i - 1] = (math.gcd(right[n - i], a[n - 1 - i]))

#print(left,right)
if left[n] != 1 or right[0] != 1:
    print("not coprime")
else:
    count = 0
    b = [i for i in a if i != 1]
    k = len(b)
    for i in prime:
        if len(sieve(b,i)) < k-1:
            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)

    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

Submission status: Wrong Answer

Solution code:
import math


def eratosthenes(limit):
    A = [i for i in range(2, limit+1)]
    P = []

    while True:
        prime = min(A)

        if prime > math.sqrt(limit):
            break

        P.append(prime)

        i = 0
        while i < len(A):
            if A[i] % prime == 0:
                A.pop(i)
                continue
            i += 1

    for a in A:
        P.append(a)

    return P


er = eratosthenes(1500)
s_er = set(er)


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

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

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

    a = set(arr)
    if 1 in a:
        a.remove(1)

    return a


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:
        if item != 1:
            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:
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 b != 1: print("not coprime")
elif c == 1: print("setwise coprime")
else:
    data = get_sieve_of_eratosthenes(10000)
    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:
import math, sys
from functools import reduce

def gcd_set(n):
    return reduce(math.gcd, n)

N = int(input())
A = set(map(int, input().split()))
for a in A:
    for b in A:
        if b > a:
            continue
        if a == b:
            continue
        if math.gcd(a, b) != 1:
            if gcd_set(A) == 1:
                print('setwise coprime')
            else:
                print('not coprime')
            sys.exit()
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 r>0.5:
            print("setwise 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:
n=int(input())
import copy
a=list(map(int,input().split()))
q=copy.copy(a)
l=[]
for i in range(n):
  b=a[i]**0.5
  ll=set()
  j=2
  while j<=int(b):
    if a[i]%j==0:
      ll.add(j)
      a[i]//=j
    else:
      j+=1
  if a[i]>b:
    l.append(b)
  l+=list(ll)
x=len(l)
y=len(set(l))
if x==y:
  print('pairwise coprime')
  exit()
from math import gcd
g=gcd(q[0],q[1])
if n==2:
  print('setwise coprime' if g==1 else 'not coprime')
  exit()
for i in range(2,n):
  g=gcd(g,q[i])
if g==1:
  print('setwise coprime')

Submission status: Wrong Answer

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

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

now = 0
total = 0

flg1 = 0
flg2 = 0

for i in range(n-1):
    if i>0:
        total = gcd(now,i+1)
    now = gcd(i,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:
import math, sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))

def prime(n):
    p = []
    flag = [True] * (n - 1)
    for i in range(n - 1):
        if flag[i] == True:
            p.append(i + 2)
            num = i
            while num <= n - 2:
                flag[num] = False
                num += i + 2
    return p

gcd = 0
for i in range(n):
    gcd = math.gcd(gcd, a[i])
if gcd != 1:
    print("not coprime")
else:
    p = prime(997)
    flag = True
    a2 = []
    for i in p:
        temp = 0
        for j in a:
            if j % i == 0:
                temp += 1
            if temp == 2:
                flag = False
                break
            while j % i == 0:
                j //= i
            a2.append(j)
        if flag == False:
            break
    if flag == False:
        print("setwise coprime")
    else:
        num = set()
        for i in a2:
            if i == 1:
                continue
            if i in num:
                print("setwise coprime")
                break
            else:
                num.add(i)
        else:
            print("pairwise coprime")

Submission status: Wrong Answer

Solution code:
import math

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

pairwise_flag=True
total_set=set()
common_set=set()
i_max= max(a)
num_list = [i for i in range(2, i_max + 1)]
prime_list = set(num_list)
for i in num_list:
    if i in prime_list:
        tmp = i+i
        while tmp < i_max:
            tmp+=i
            prime_list.discard(tmp)

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

for i in range(n):
    tmp = a[i]
    tmp_list=[]
    for j in prime_list:
        if tmp%j ==0:
            while tmp%j==0:
                 tmp//=j
        # if tmp < j:
        #     break
        tmp_list.append(j)
    for j in tmp_list:
        prime_list.discard(j)
    if tmp !=1:
        pairwise_flag=False
        break


if pairwise_flag:
    print("pairwise coprime")
elif total_gcd>1:
    print("not coprime")
else:
    print("setwise coprime")

Submission status: Wrong Answer

Solution code:
#import sys
MOD = 10 ** 9 + 7
INFI = 10**10
#input = sys.stdin.readline
import math
from collections import deque
import itertools
import heapq
#import bisect
from fractions import Fraction
import copy
from functools import lru_cache
from collections import defaultdict
import pprint

#oo=list("ABCDEFGHIJKLMNOPQRSTUVWXYZ")
# ko=list("abcdefghijklmnopqrstuvwxyz")

def sosuhante(n):
    for k in range(2, int(math.sqrt(n))+1):
        if n% k ==0:
            return False
    return True
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

def kingaku(a,b,n):
    keta=len(str(n))
    return a*n+b*keta

def my_index(l, x, default=False):
    if x in l:
        return l.index(x)
    else:
        return default

#    h,w,a,b = map(int, input().split())
#    c = [[0 for j in range(n)] for i in range(n)]

def ret(a):
    c=[None]*(len(a)-1)
    if len(a)==1:
        return a[0]
    elif len(a)==0:
        return 0
    for i in range(1,len(a)):
        c[i-1]=abs(a[i]-a[i-1])
    return ret(c)

def soinsubunkai(n):
    a = []
    i = 1
    while i*i <= n:
        if n % i == 0 and i!=1:
            a.append(i)
            n=n//i

        if n% i !=0 or i==1:
            i += 1
    nokori=[n]
    return a + nokori

def soinsubunkai2(n,m):
    a = []
    i = 1
    nnn=int(math.sqrt(n)+10)
    for i in m:
        if n % i == 0 and i!=1:
            a.append(i)
            n=n//i

        if n% i !=0 or i==1:
            i += 1
        if i>=nnn:
            break
    nokori=[n]
    return a + nokori

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 lower_divisors + upper_divisors[::-1]


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')
    prime = []
    limit = math.sqrt(n)
    data = [i + 1 for i in range(1, n)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]

def main():
    #l,r,d=map(int,input().split())
    n=int(input())
    a=list(map(int,input().split()))
    sosu=[]
    ccc=get_sieve_of_eratosthenes(int(math.sqrt(n)+10))
    memo = defaultdict(int)
    for i in range(n):
        if a[i]!=1:
            temp=set(soinsubunkai2(a[i],ccc))
        else:
            temp={}
        for j in temp:
            memo[j]+=1

    memo.pop(1,None)
 #   print(sosu)
 #   print(memo)
 #   print(memo.values())
    if len(memo)>=1:
        mmm=max(memo.values())
    else:
        mmm=1
    if mmm<=1:
        print("pairwise coprime")
    elif mmm<n:
        print("setwise coprime")
    else:
        print("not coprime")








if __name__ == "__main__":

    main()

Submission status: Wrong Answer

Solution code:
MOD = 10**9+7
lim = 200000
inv_t = [-1 for i in range(lim+1)]
factrial = [-1 for i in range(lim+1)]
factrial_inv = [-1 for i in range(lim+1)]


def mod_inv(x, mod=MOD):
    y, u, v, _x = mod, 1, 0, x
    while y:
        t = _x//y
        _x -= t*y
        _x, y = y, _x
        u -= t*v
        u, v = v, u
    u %= mod
    if u < 0:
        u += mod
    return u


def mod_pow(a, n, mod=MOD):
    res = 1
    while n:
        if n & 1:
            res = res*a % mod
        a = a*a % mod
        n >>= 1
    return res


def COMinit(max=lim, mod=MOD):
    factrial[0] = factrial_inv[0] = 1
    factrial[1] = factrial_inv[1] = 1
    inv_t[0] = inv_t[1] = 1
    for i in range(2, max):
        factrial[i] = factrial[i-1]*i % mod
        inv_t[i] = -inv_t[mod % i]*(mod//i) % mod
        factrial_inv[i] = factrial_inv[i-1]*inv_t[i] % mod


def comb(a, b, mod=MOD):
    if a < b:
        return 0
    if factrial[0] == -1:
        COMinit()
    return (factrial[a]*factrial_inv[b]*factrial_inv[a-b]) % mod


def prime_factor(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 = [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:
import math
n=int(input())
l=list(map(int,input().split()))
e=0
e1=0
e2=0
e3=0
c=l[0]
for i in range(1,n):
    c=math.gcd(l[i],c)
for i in range(n):
    if(l[i]%2==0):
        e+=1
    if(l[i]%3==0):
        e1+=1
    if(l[i]%5==0):
        e2+=1
    if(l[i]%7==0):
        e3+=1
l.sort()
aa=0
for i in range(n//2):
    for j in range(2,100):
        if(l[i]*j in l):
            aa=1
            break
    
if(e<=1 and e1<=1 and e2<=1 and e3<=1 and aa==0 and c==1):
    print("pairwise coprime")
elif(c==1):
    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())

MAX_N = max(A)+5
primes = list(range(MAX_N+1))
for i in range(2, int(MAX_N**0.5)+1):
    if primes[i] < i:
        continue
    for j in range(2*i, MAX_N+1, i):
        primes[j] = i

def check():
    S = set()
    for a in A:
        T = set()
        while True:
            p = primes[a]
            if p in S:
                return False
            T.add(p)
            if p == a:
                break
            a //= p
        S |= T
    return True

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

Submission status: Wrong Answer

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

from math import gcd
from functools import reduce

def gcd_list(L):
    return reduce(gcd, L)

# nまでの素数リスト
def prime_list(n):
    primes = set(range(2, n + 1))
    for i in range(2, int(n ** 0.5) + 1):
        primes.difference_update(range(i * 2, n + 1, i))
    return list(primes)

g = gcd_list(A)
# primes = prime_list(200)
# print(len(primes))

# cnt = [0] * 200
# bl = True
# for a in A:

    # for p in primes:
    #     if a % p == 0:
    #         cnt[p] += 1


# ma = max(cnt)


def init(init_val):
    #set_val
    for i in range(n):
        seg[i+num-1]=init_val[i]    
    #built
    for i in range(num-2,-1,-1) :
        seg[i]=gcd(seg[2*i+1],seg[2*i+2]) 
    
def update(k,x):
    k += num-1
    seg[k] = x
    while k:
        k = (k-1)//2
        seg[k] = gcd(seg[k*2+1],seg[k*2+2])
    
def query(p,q):
    if q<=p:
        return ide_ele
    p += num-1
    q += num-2
    res=ide_ele
    while q-p>1:
        if p&1 == 0:
            res = gcd(res,seg[p])
        if q&1 == 1:
            res = gcd(res,seg[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = gcd(res,seg[p])
    else:
        res = gcd(gcd(res,seg[p]),seg[q])
    return res




#####単位元######
ide_ele = 0

#num:n以上の最小の2のべき乗
num =2**(n-1).bit_length()
seg=[ide_ele]*2*num
init(A)

bl = True
for i in range(n):
    gcds = gcd(query(0,i),query(i+1,n))
    if gcds != 1:
        bl = False
    

if bl:
    print('pairwise coprime')
elif g == 1:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Wrong Answer

Solution code:
import math
from functools import reduce

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

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

def lcm(x, y, my_gcd):
    return (x * y) // my_gcd

# print('input >>')
N = input()
As = list(map(int,(input().split())))
As.sort()

my_gcd = As[0] 
GCD = my_gcd
my_lcm = As[0]
has_pair = False

for i in range(1, len(As)):
    GCD = math.gcd(GCD, As[i])
    if not has_pair:
        LCM = lcm(my_lcm, As[i], GCD)
        if LCM != my_lcm * As[i]:
            has_pair = True

# print('-----output-----')
if GCD == 1 and not has_pair:
    print('pairwise coprime')
elif GCD == 1 and has_pair:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Wrong Answer

Solution code:
from math import gcd
from time import time
start = time()
n = int(input())
A = list(map(int,input().split()))
g = A[0]
mul = A[0]
pflag = True
for i in range(n-1):
  if pflag:
    if gcd(mul,A[i+1]) != 1:
      pflag = False 
    mul *= A[i+1]
  g = gcd(g,A[i+1])
  if i % 100 == 0:
    if time()-start > 1.9:
      print("pairwise coprime")
      quit()
if g != 1:
  print("not coprime")
else:
  if pflag:
    print("pairwise coprime")
  else:
    print("setwise 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('not 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 math
from functools import reduce
 
n = int(input())
a = list(map(int,input().split()))
 
#累積GCD
left = [0] * (n + 1)
for i in range(n):
    left[i + 1] = (math.gcd(left[i],a[i]))

if left.count(1) == n-1:
  print("pairwise coprime ")
elif left.count(1) > 0:
  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 make_prime(U):
    is_prime = np.zeros(U, np.bool)
    is_prime[2] = 1
    is_prime[3::2] = 1
    M = int(U**.5) + 1
    for p in range(3, M, 2):
        if is_prime[p]:
            is_prime[p * p::p + p] = 0
    return is_prime, is_prime.nonzero()[0]


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=}')
is_prime, primes = make_prime(10**6)
primes = set(primes)
# 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(np.count_nonzero(A % 2))
if len(arr) != 0:
    print('not coprime')
else:
    for s in S:
        if np.count_nonzero(A % s) >= 2:
            print('pairwise coprime')
            exit()
    print('setwise coprime')

Submission status: Wrong Answer

Solution code:
import math
from functools import reduce

def gcd_lis(num_lis):
    return reduce(math.gcd, num_lis)

N = int(input())
lis = list(map(int, input().split()))
c1 = True
c2 = True
for i in range(N-1):
  if math.gcd(lis[i], lis[i+1]) != 1:
    c1 = False

if gcd_lis(lis) != 1:
  c2 = False

if c1:
  print("pairwise coprime")
if not c1 and c2:
  print("setwise coprime")
if not c1 and not c2:
  print("not coprime")

Submission status: Wrong Answer

Solution code:
import math

n = int(input())
aa = tuple(map(int, input().split()))

primes = [i for i in range(1000001)]
for j in range(2, 1001):
    if primes[j] is None:
        continue
    for i in range(j + j, len(primes), j):
        primes[i] = None
primes[0] = primes[1] = None
primes = set([p for p in primes if p is not None])

f = 0
p = aa[0]
for a in aa:
    p = math.gcd(p, a)
    if a not in primes:
        f += 1
if f <= 1:
    print("pairwise coprime")
elif p == 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()