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:
##https://www.codechef.com/viewsolution/20131475

from math import gcd

def main():
    n = int(input())
    A = list(map(int , input().split()))
    N = max(A)+1

    if N > 9*10**5:
        print("not coprime")
        exit()

    sv = [i for i in range(N)]
    for i in range(2 ,int(N**2)+1) :
        if i * i >= N : break
        if sv[i] < i : continue
        for j in range(i * i , N , i) :
            sv[j] = min(sv[j] , i)

    def getPrimes(a) :
        pr = []
        if a == 1 : return pr
        pr.append(sv[a])
        while a > 1 :
            if sv[a] != pr[-1] :
                pr.append(sv[a])
            a //= sv[a]
        return pr

    np = [0] * N
    F = [0] * N


    for a in A :
        pr = getPrimes(a)
        for i in range(1 << len(pr)) :
            prod , nb = 1 , 0
            for j in range(len(pr)) :
                if i & (1<<j) :
                    prod *= pr[j]
                    nb += 1
            F[prod] += 1
            np[prod] = nb

    ans = 0
    for i in range(N) :
        cnt = F[i]
        cnt = (cnt * (cnt-1))//2
        if np[i] & 1 : ans -= cnt
        else : ans += cnt

    if ans == (n*(n-1))//2:
        print("pairwise coprime")
        exit()

    A.sort()
    d = A[0]

    for i in A:
        d = gcd(i,d)
        if d == 1 or d > 10**2:
            break

    if d == 1:
        print("setwise coprime")
    else:
        print("not coprime")

main()

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
            soinsu.append(prime)
            if a // prime in set_primes:
                soinsu.append(a // prime)
    if flg:
        soinsu.append(a)

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

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

pairwise_flag=True
total_set=set()
common_set=set()
i_set = [set() for i in range(n)]

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)
#prime_list = list(prime_list)
#used_flag=[1 for i in range(len(prime_list))]

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

    #total_set = total_set.union(i_set[i])
    # if i==0:
    #     common_set=i_set[i]
    # else:
    #     common_set=common_set.intersection(i_set[i])

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

Submission status: Wrong Answer

Solution code:
from sys import stdin,stdout
from math import gcd
n=int(stdin.readline())
a=list(map(int,stdin.readline().split()))
s=set(a)
p=2;d={}
N=10**6+2
primes=[1]*N;not_pairwise=0
# vis=set()
while p*p<=N:
    if primes[p]:
        for mul in range(p,N,p):
            primes[mul]=0
            if mul in s:
                # vis.add(mul)
                d[p]=d.get(p,0)+1
                if d[p]>=2:not_pairwise=1;break;
        if not_pairwise:break
    p+=1
g=a[0]
for v in a:
    g=gcd(g,v)
if not_pairwise==0:print('pairwise coprime')
elif g==1: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(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:
import math

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

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 arr


def setwise_coprime(a):
    b=a.copy()
    one=b.pop()
    for i in range(n-1):
        two=b.pop()
        one=math.gcd(one,two)
    if one==1:
        return True
    return False

def pairwise_coprime(an):
    frui=[0]*(10**6+1)
    for a in an:
        soinnsuu_list=factorization(a)
        for i in soinnsuu_list:
            if frui[i]==1:
                return False
            for k in range(1,int(10**6/i)+1):
                frui[i*k]=1
    return True


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

Submission status: Wrong Answer

Solution code:
import math

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

flag = 0
pairw = 0
setw = a[n-1]

for i in range(n-1):
    pairw = math.gcd(a[i],a[i+1])
    setw = math.gcd(setw,a[i])
    if pairw != 1:
        flag = 1

pairw = math.gcd(a[n-1],a[1])
if pairw != 1:
    flag = 1

if flag == 1:
    if setw == 1:
        print('setwise coprime')
    else:
        print('not coprime')
else:
    print('pairwise 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
    a = [i for i in a if i != 1]
    k = len(a)
    for i in prime:
        if len(sieve(a,i)) < k-1:
            count = 1
            break
    if count == 1:
        print("setwise coprime")
    else:
        print("pairwise 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
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])
            if(temp == 1):
                templ.append(a[j]*a[j+1]//temp)
                flag = 1
            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 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[-1] == 1 and left.count(1) == n-1:
  print("pairwise coprime ")
elif left[-1] == 1 and left.count(1) != n-1:
  print("setwise coprime")
else:
  print("not coprime")

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(1000)
    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:
import math

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

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

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

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

checker = eratosthenes(a[-1])
x = a[0]

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

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

Submission status: Wrong Answer

Solution code:
from math import gcd

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

n=int(input())

a=input().split()

gcd_all=10000000
lcm_all=1

for i in a:
  if gcd_all!=1:
    gcd_all=gcd(gcd_all,int(i))
  lcm_all=lcm(lcm_all,int(i))
  
for i in a:
  lcm_all = lcm_all // int(i)
  
if lcm_all==1:
  print("pairwise coprime")
elif gcd_all==1:
  print("setwise coprime")
else:
  print("not coprime")

Submission status: Wrong Answer

Solution code:
import sys
## io ##
def IS(): return sys.stdin.readline().rstrip()
def II(): return int(IS())
def MII(): return list(map(int, IS().split()))
def MIIZ(): return list(map(lambda x: x-1, MII()))
def gcd(x,y):
    while y: x,y = y,x%y
    return x
def prime_factor(n):
    res = []
    for i in range(2,int(n**0.5)+1):
        while n%i==0: res.append(i); n //= i
    if n != 1: res.append(n)
    return res
from functools import reduce
#======================================================#
def main():
    n = II()
    aa = MII()
    head_prime = prime_factor(aa[0])

    pw_flag = True
    nc_flag = True
    for a in aa[1:]:
        nc_tmp = False
        for p in head_prime:
            if a%p == 0:
                nc_tmp = True
                pw_flag = False
        nc_flag &= nc_tmp

    if reduce(gcd, aa) != 1:
        print('not coprime')
    elif nc_flag and reduce(gcd, aa) == 1:
        print('setwise coprime')
    else:
        print('pairwise coprime')


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
##https://www.codechef.com/viewsolution/20131475

from math import gcd

def main():
    n = int(input())
    A = list(map(int , input().split()))
    N = max(A)+1

    if N > 10**5:
        print("not coprime")
        exit()

    sv = [i for i in range(N)]
    for i in range(2 ,int(N**2)+1) :
        if i * i >= N : break
        if sv[i] < i : continue
        for j in range(i * i , N , i) :
            sv[j] = min(sv[j] , i)

    def getPrimes(a) :
        pr = []
        if a == 1 : return pr
        pr.append(sv[a])
        while a > 1 :
            if sv[a] != pr[-1] :
                pr.append(sv[a])
            a //= sv[a]
        return pr

    np = [0] * N
    F = [0] * N


    for a in A :
        pr = getPrimes(a)
        for i in range(1 << len(pr)) :
            prod , nb = 1 , 0
            for j in range(len(pr)) :
                if i & (1<<j) :
                    prod *= pr[j]
                    nb += 1
            F[prod] += 1
            np[prod] = nb

    ans = 0
    for i in range(N) :
        cnt = F[i]
        cnt = (cnt * (cnt-1))//2
        if np[i] & 1 : ans -= cnt
        else : ans += cnt

    if ans == (n*(n-1))//2:
        print("pairwise coprime")
        exit()

    A.sort()
    d = A[0]

    for i in A:
        d = gcd(i,d)
        if d == 1 or d > 10**2:
            break

    if d == 1:
        print("setwise coprime")
    else:
        print("not coprime")

main()

Submission status: Wrong Answer

Solution code:
from math import gcd
def g(a):
    al=len(a)
    if al==2:
        return gcd(a[0],a[1])
    elif al==1:
        return a[0]
    return gcd(g(a[:al//2]),g(a[al//2:]))
n=int(input())
a=list(map(int,input().split()))
if g(a)!=1:
    print("not coprime")
    exit()
one=a.count(1)
if n-one>168:
    print("setwise coprime")
    exit()
a=[i for i in a if i!=1]
n=len(a)
for i in range(n-1):
    for j in range(i+1,n):
        if gcd(a[i],a[j])!=1:
            print("setwise coprime")
            exit()
print("pairwise coprime")

Submission status: Wrong Answer

Solution code:
from math import sqrt
from collections import Counter
import sys
import numpy as np

def factorize(n):
    rt = int(sqrt(n)+1)
    facts = []
    for i in range(2, rt+1):
        if n % i == 0:
            facts.append(i)
            while n % i == 0:
                n //= i
    if n != 1:
        facts.append(n)
    return facts

def sieve(n):
    S = [True] * (n+1)
    S[0] = S[1] = False
    i = 2
    while i * i <= n:
        if S[i]:
            k = i * i
            while k <= n:
                S[k] = False
                k += i
        i += 1
    return S


n = int(input())
A = list(map(int, input().split()))
amax = max(A)
primes= np.arange(amax+1)[sieve(amax)]


facts = {}
for a in A:
    rt = int(sqrt(a)+1)
    for p in primes:
        if p > rt: break
        if a % p == 0:
            if facts.get(p) is None:
                facts[p] = 1
            else:
                facts[p] += 1

p_max = max(facts.values()) if facts  else 1
if  p_max == 1:
    print('pairwise coprime')
elif  p_max <  n:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Wrong Answer

Solution code:
import math
from math import gcd
from functools import reduce

def gcd_list(numbers):
    return reduce(gcd, numbers)
def lcm(x, y):
    return (x * y) // gcd(x, y)

N = int(input())
A = [int(i) for i in input().split()]

left = [0] * N
for i in range(1, N):
    left[i] = gcd(A[i - 1], left[i - 1])
right = [0] * N
for i in range(N - 2, -1, -1):
    right[i] = gcd(A[i + 1], right[i + 1])

left[0] = 1
right[-1] = 1

flag = True
for a, l, r in zip(A, left, right):
    if gcd(l, a) != 1 and gcd(r, a) != 1:
        flag = False
        break

if flag:
    print("pairwise coprime")
else:
    if gcd_list(A) == 1:
        print("setwise coprime")
    else:
        print("not coprime")

Submission status: Wrong Answer

Solution code:
import sys
import  math
import fractions
from collections import defaultdict
import heapq
import numpy as np
from bisect import bisect_left,bisect

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


def factorization(c,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)
            c[i]+=1
            if(c[i]==2):
                flag=False
                return c,flag

    if temp!=1:
        arr.append(temp)
        c[temp]+=1
        if(c[temp]==2):
            flag=False
            return c,flag

    if arr==[]:
        c[n]+=1
        if(c[n]==2):
            flag=False
            return c,flag

    flag=True
    return c,flag

def factorization1(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 arr

def factorization2(c2,n):
    arr = []
    temp = n
    for i in c2:
        if temp%i==0:
            arr.append(i)

    return arr

N=int(input())
A=nl()
c=[0]*(10**6)
flag=True
for i in range(N):
    if(flag==True):
        c,flag=factorization(c,A[i])
    else:
        break

if(flag==True):
    print("pairwise coprime")
    sys.exit(0)

c2=factorization1(A[0])
for i in range(N):
        c2=factorization2(c2,A[i])
        if(c2==[]):
            print("setwise coprime")
            sys.exit(0)

print("not 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():
    n = ni()
    A = lma()
    d=collections.Counter()
    r = random.random()
    if n==10**6:
        if r<0.25:
            print("setwise coprime")
            exit()
        elif 0.25<r<0.5:
            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:
N,*A=map(int,open(0).read().split())

def prime_factorize(n):
    a = set()
    while n % 2 == 0:
        a.add(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.add(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.add(n)
    return a

prev=set()
pairwise=True
swd=prime_factorize(A[0])
for a in A:
    s=prime_factorize(a)
    if pairwise:
        if s.isdisjoint(prev):
            prev=s
        else:
            pairwise=False
    swd &= s
setwise=not pairwise and len(swd)==0
if pairwise:
    print('pairwise coprime')
elif setwise:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Wrong Answer

Solution code:
import sys, bisect, math, itertools, heapq, collections
from operator import itemgetter
# a.sort(key=itemgetter(i)) # i番目要素でsort
from functools import lru_cache
import copy
# @lru_cache(maxsize=None)
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
mod = 10**9 + 7
eps = 10**-7


def inp():
    '''
    一つの整数
    '''
    return int(input())


def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))


def str_inp():
    '''
    文字列をリストとして読み込む
    '''
    return list(input()[:-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]


n = inp()
a = inpl()

data = get_sieve_of_eratosthenes(10**6)
tmp = a[0]
for i in range(1, n):
    tmp = math.gcd(tmp, a[i])
    if tmp == 1:
        break
if tmp != 1:
    print("not coprime")
    exit()

dp = {i: 0 for i in data}
for i in range(n):
    tmp = a[i]
    for j in data:
        if tmp == 1:
            break
        if tmp % j == 0:
            dp[j] += 1
            while tmp % j == 0:
                tmp //= j
ans = max(list(dp.values()))
if ans == 1:
    print("pairwise coprime")
else:
    print("setwise coprime")
# ans = "pairwise coprime"
# for i in data:
#     coprime = 0
#     for j in range(n):
#         if a[j] % i == 0:
#             coprime += 1
#         elif a[j] % i != 0 and (coprime >= 2 or ans == "setwise coprime"):
#             break
#     if coprime == n:
#         ans = "not coprime"
#         break
#     elif coprime >= 2:
#         ans = "setwise coprime"
# print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict


def factorization(n):

    arr = defaultdict(int)
    tmp = n
    for i in range(2, int(-(-n**0.5 // 1)) + 1):  # sqrt(n) まで

        # i で割れるだけ割る、を繰り返す
        if tmp % i == 0:
            cnt = 0

            while tmp % i == 0:
                cnt += 1
                tmp //= i

            arr[i] = cnt  # 結果を追加

    if tmp != 1:
        arr[tmp] = 1  # まだ余っていれば追加しておく

    # if arr == {}:
    #    arr[n] = 1  # このブロック、必要か？

    return arr


N = int(sys.stdin.readline().rstrip())
A = [int(x) for x in sys.stdin.readline().rstrip().split()]

pc = True
sp = True

maxlist = factorization(A[0])
minlist = factorization(A[0])

for i in range(1, N):
    d = factorization(A[i])
    for p in maxlist.keys():

        if pc and min(maxlist[p], d[p]) != 0:
            pc = False
        maxlist[p] = max(maxlist[p], d[p])
        minlist[p] = min(minlist[p], d[p])


for p in minlist.keys():
    if minlist[p] != 0:
        sp = False


if pc:
    print("pairwise coprime")
elif sp:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Wrong Answer

Solution code:
import itertools
import collections
from math import gcd
def prime_factor_table(n):
    table = [0] * (n + 1)
    
    for i in range(2, n + 1):
        if table[i] == 0:
            for j in range(i + i, n + 1, i):
                table[j] = i
    
    return table

def prime_factor(n, prime_factor_table):
    prime_count = dict()
    
    while prime_factor_table[n] != 0:
        prime_count[prime_factor_table[n]] = 1
        n //= prime_factor_table[n]
    prime_count[n] = 1
    
    return prime_count

pp = prime_factor_table(10**6)
#print(prime_factor(1, pp))
N, = map(int, input().split())
X = list(map(int, input().split()))
d = dict()
f = 0
for x in X:
    y = prime_factor(x, pp)
    if x == 1:
        N-=1
    for k in y:
        if k in d:
            f = 1
            d[k] += 1
        else:
            d[k] = 1
if f:
    m = 0
#    print(d)
    for k in d:
        m = max(m, d[k])
    if m != N:
        print("setwise coprime")
    else:
        print("not coprime")
else:
    print("pairwise coprime")

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    input = sys.stdin.buffer.readline
    from math import gcd
    N = int(input())
    A = list(map(int, input().split()))
    g = A[0]

    S = 1
    for x in A:
        S *= x

    def factorization(n):
        ret = set()
        temp = n
        for i in range(2, int(-(-n**0.5//1))+1):
            if temp % i == 0:
                cnt = 0
                while temp % i == 0:
                    cnt += 1
                    temp //= i
                ret.add(i)

        if temp != 1:
            ret.add(temp)

        if len(ret) == 0 and n != 1:
            ret.add(n)

        return ret

    flag = False
    for i, x in enumerate(A[::-1]):
        g = gcd(g, x)
        S //= x
        if flag and gcd(x, S) > 1:
            flag = False

    if flag:
        print("pairwise coprime")
    elif g == 1:
        print("setwise coprime")

    else:
        print("not coprime")


main()

Submission status: Wrong Answer

Solution code:
import sys

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


def main():
    N = int(readline())
    if N>78499:
        print('not coprime')
        sys.exit()
    A = list(map(int, readline().split()))
    setwise = True
    pairwise = True
    primes = [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]
    for p in primes:
        if not setwise and not pairwise:
            break
        tmp = 0
        for a in A:
            if a % p == 0:
                tmp += 1
        if tmp >=2:
            pairwise = False
            if tmp == N:
                setwise = False
        else:
            continue

    if pairwise:
        print('pairwise coprime')
    else:
        if setwise:
            print('setwise coprime')
        else:
            print('not coprime')


if __name__ == '__main__':
    main()

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(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:
# -*- coding: utf-8 -*-
import copy

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

    return divisors


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

pcf = len(a) == n
pc = set(make_divisors(a.pop()))
pcl = len(pc)
sc = copy.deepcopy(pc)

for i in a:
    d = set(make_divisors(i))
    dl = len(d) - 1
    pc = pc.union(d)
    pcl2 = len(pc)
    if pcl + dl != pcl2:
        pcf = False
    pcl = pcl2

    sc = sc.intersection(d)

if pcf:
    print("pairwise coprime")
elif len(sc) == 1:
    print("setwise coprime")
else:
    print("not coprime")