Problem:


Score : 500 points

Problem Statement

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

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

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

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

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

Constraints

2 \leq N \leq 10^6

1 \leq A_i\leq 10^6

Input

Input is given from Standard Input in the following format:

N
A_1 \ldots A_N

Output

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

Sample Input 1

3
3 4 5

Sample Output 1

pairwise coprime

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

Sample Input 2

3
6 10 15

Sample Output 2

setwise coprime

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

Sample Input 3

3
6 10 16

Sample Output 3

not coprime

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



Sample input:
3
3 4 5


Sample output:
pairwise coprime

Submission status: Wrong Answer

Solution code:
import sys

def enum_div(n):
    ir=int(n**(0.5))+1
    ret=[]
    for i in range(1,ir):
        if n%i == 0:
            ret.append(i)
            if (i!= 1) & (i*i != n):
                ret.append(n//i)
    return ret


n=int(input())
ap=list(map(int,input().split()))
amin=min(ap)

if amin!=1:
    bp=enum_div(amin)+[amin]
#bp.sort()
#    bp=bp[1:]
    for bpi in bp:
        if bpi==1:
            continue
        lap=0
        for ai in ap:
            if ai%bpi==0:
                lap+=1
#        lap=len([ai for ai in ap if ai%bpi==0])
        if lap==n:
            print("not coprime")
            sys.exit()

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


ptype="pairwise coprime"
for pp in p:
    lap=0
    for ai in ap:
        if  ai%pp==0:
            lap+=1
        if lap>=2:
            ptype="setwise coprime"
            print(ptype)    
            sys.exit()
#    lap=len([ai for ai in ap if ai%pp==0])
#    print("pp:",pp,lap)
#    if lap==n:
#        ptype="not coprime"
#        print("not coprime")
#        break
#    if lap>=2:
#        if ptype!="not coprime":
#        ptype="setwise coprime"

print(ptype)

Submission status: Wrong Answer

Solution code:
import bisect, collections, copy, heapq, itertools, math, string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int, sys.stdin.readline().rstrip().split())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

def main():
    from collections import defaultdict
    def get_sieve_of_eratosthenes(n, D):
        limit = int(n ** 0.5)
        data = []
        for i in range(2, n + 1):
            data.append(i)
            D[i] = i

        while data[0]:
            p = data[0]
            if limit <= p:
                return D
            for i, d in enumerate(data):
                mod = d % p
                if mod != 0:
                    continue
                else:
                    D[d] = p
                    del data[i]
        return D



    N = I()
    A = LI()
    D = defaultdict()


    g = A[0]
    for a in A:
        g = math.gcd(g, a)
    if g > 1:
        print('not coprime')
        exit()

    A_ = set(A)
    A_.discard(1)
    if len(A_) >= 90000:
        print('setwise coprime')
        exit()

    max_a = max(A)
    if max_a == 1:
        print('pairwise coprime')
        exit()
    D = get_sieve_of_eratosthenes(max_a, D)
    B = defaultdict(int)
    for a in A:
        while a != 1:
            x = D[a]
            B[x] += 1
            a //= x

    max_b = max(B.values())
    if max_b == 1:
        print('pairwise coprime')
    else:
        print('setwise coprime')
    print('pairwise coprime')

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:

import sys

def enum_div(n):
    ir=int(n**(0.5))+1
    ret=[]
    for i in range(1,ir):
        if n%i == 0:
            ret.append(i)
            if (i!= 1) & (i*i != n):
                ret.append(n//i)
    return ret


n=int(input())
ap=list(map(int,input().split()))
amin=min(ap)

if amin!=1:
    bp=enum_div(amin)+[amin]
#bp.sort()
    bp=bp[1:]
    for bpi in bp:
        lap=0
        for ai in ap:
            if ai%bpi==0:
                lap+=1
#        lap=len([ai for ai in ap if ai%bpi==0])
        if lap==n:
            print("not coprime")
            sys.exit()

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


ptype="pairwise coprime"
for pp in p:
    lap=0
    for ai in ap:
        if  ai%pp==0:
            lap+=1
        if lap>=2:
            ptype="setwise coprime"
            print(ptype)    
            sys.exit()
#    lap=len([ai for ai in ap if ai%pp==0])
#    print("pp:",pp,lap)
#    if lap==n:
#        ptype="not coprime"
#        print("not coprime")
#        break
#    if lap>=2:
#        if ptype!="not coprime":
#        ptype="setwise coprime"

print(ptype)

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)


g = a[0]
for x in a[1:]:
    g = gcd(g, x)

if g > 1:
    print('not coprime')
    exit()


exist = [False] * (10**6+1)
for x in a:
    if x % 2 == 0:
        if exist[2]:
            print('setwise coprime')
            exit()
        while x % 2 == 0:
            x //= 2
        exist[2] = True
    div = 3
    while div * div <= x:
        if x % div == 0:
            if exist[div]:
                print('setwise coprime')
            exit()
            while x % div == 0:
                x //= div
            exist[div] = True
        div += 2
    if x > 1:
        if exist[x]:
#            print('setwise coprime')
            print('hoge')
            exit()
        exist[x] = True
print('pairwise coprime')

Submission status: Wrong Answer

Solution code:
# pairwise coprime <= setwise coprime の順に判定するのが効率が良い。
# 問題は pairwise をどのように効率よく計算するか。全探索は計算量の観点から厳しい。数字の設定的に O(N logN) 程度のアルゴリズムを想定していそう。
# エラトステネスで素数列挙　=> 全て素因数分解し、各素因数の出現回数を数える。
# もし各一回ずつなら、pairwise、ある素因数でn回出現するものがあれば、どちらでもない

def sieve(N):
    if N < 2:
        return None
    elif N == 2:
        return [2]
    data = [i for i in range(2,N+1)]
    P = []
    limit = min(int(N**0.5)+10,N)
    while True:
        p = data[0]
        if limit <= p:
            return P+data
        P.append(p)
        data = [e for e in data if e%p]


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

primes = sieve(10**6)
d = dict()

for a in A:
    for p in primes:
        if a%p == 0:
            if p in d:
                d[p] += 1
            else:
                d[p] = 1
        if p > a:break

T = 0
for p in d:
    T = max(T,d[p])
if T == N:
    print("not coprime")
elif T == 1:
    print('pairwise coprime')
else:
    print('setwise coprime')

Submission status: Wrong Answer

Solution code:

import sys

def enum_div(n):
    ir=int(n**(0.5))+1
    ret=[]
    for i in range(1,ir):
        if n%i == 0:
            ret.append(i)
            if (i!= 1) & (i*i != n):
                ret.append(n//i)
    return ret


n=int(input())
ap=list(map(int,input().split()))
amin=min(ap)

if amin!=1:
    bp=enum_div(amin)+[amin]
#bp.sort()
    bp=bp[1:]
    for bpi in bp:
        lap=len([ai for ai in ap if ai%bpi==0])
        if lap==n:
            print("not coprime")
            sys.exit()

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


ptype="pairwise coprime"
for pp in p:
    lap=0
    for ai in ap:
        if  ai%pp==0:
            lap+=1
        if lap>=2:
#        if ptype!="not coprime":
            ptype="setwise coprime"
            print(ptype)    
            sys.exit()
#    lap=len([ai for ai in ap if ai%pp==0])
#    print("pp:",pp,lap)
#    if lap==n:
#        ptype="not coprime"
#        print("not coprime")
#        break
#    if lap>=2:
#        if ptype!="not coprime":
#        ptype="setwise coprime"

print(ptype)

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)


g = a[0]
for x in a[1:]:
    g = gcd(g, x)

if g > 1:
    print('not coprime')
    exit()


exist = [False] * (10**6+1)
for x in a:
    if x % 2 == 0:
        if exist[2]:
            print('setwise coprime')
            exit()
        while x % 2 == 0:
            x //= 2
        exist[2] = True
    div = 3
    while div * div <= x:
        if x % div == 0:
            if exist[div]:
                print('setwise coprime')
            exit()
            while x % div == 0:
                x //= div
            exist[div] = True
        div += 2
    if x > 1:
        if exist[x]:
            print('setwise coprime')
            exit()
        exist[x] = True
print('pairwise coprime')

Submission status: Wrong Answer

Solution code:
import math

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

flag = 0 # 0をpairwise coprime

for i in range(N-1): 
    if math.gcd(A[i], A[i+1]) != 1:
        flag = 1 #1はpairwise coprimeではない
        break

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

if flag == 0:
    answer = 'pairwise coprime'
elif flag == 1 and g == 1:
    answer = 'setwise coprime'
else:
    answer = 'not coprime'

print(answer)

Submission status: Wrong Answer

Solution code:
import math

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

flag = 0 # 0をpairwise coprime

for i in range(N-1): 
    if math.gcd(A[i], A[i-1]) != 1:
        flag = 1 #1はpairwise coprimeではない
        break

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

if flag == 0:
    answer = 'pairwise coprime'
elif flag == 1 and g == 1:
    answer = 'setwise coprime'
else:
    answer = 'not coprime'

print(answer)

Submission status: Wrong Answer

Solution code:
from functools import reduce
from math import gcd


def main():
    n = int(input())
    a = set(int(i) for i in input().split())
    m = max(a)
    p = [i for i in range(m + 1)]
    for i in range(3, m + 1):
        for j in range(2, int(i**.5 + 1) + 1):
            if i % j == 0:
                p[i] = j
                break
    factors = set()
    for ai in a:
        f = set()
        while ai > p[ai]:
            f.add(p[ai])
            ai //= p[ai]
        f.add(ai)
        if factors & f:
            break
        factors |= f
    else:
        print("pairwise coprime")
        return
    if reduce(gcd, a) == 1:
        print("setwise coprime")
    else:
        print("not coprime")


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:

import sys

def enum_div(n):
    ir=int(n**(0.5))+1
    ret=[]
    for i in range(1,ir):
        if n%i == 0:
            ret.append(i)
            if (i!= 1) & (i*i != n):
                ret.append(n//i)
    return ret


n=int(input())
ap=list(map(int,input().split()))
amin=min(ap)

if amin!=1:
    bp=enum_div(amin)+[amin]
#bp.sort()
    bp=bp[1:]
    for bpi in bp:
        lap=len([ai for ai in ap if ai%bpi==0])
        if lap==n:
            print("not coprime")
            sys.exit()

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


ptype="pairwise coprime"
for pp in p:
    lap=len([ai for ai in ap if ai%pp==0])
#    print("pp:",pp,lap)
#    if lap==n:
#        ptype="not coprime"
#        print("not coprime")
#        break
    if lap>=2:
#        if ptype!="not coprime":
        ptype="setwise coprime"

print(ptype)

Submission status: Wrong Answer

Solution code:
from math import gcd


def main():
    n = int(input())
    a = [int(i) for i in input().split()]
    m = max(a)
    p = [i for i in range(m + 1)]
    for i in range(3, m + 1):
        for j in range(2, int(i**.5 + 1) + 1):
            if i % j == 0:
                p[i] = j
                break
    factors = set()
    for ai in a:
        f = set()
        while ai > p[ai]:
            f.add(p[ai])
            ai //= p[ai]
        f.add(ai)
        if factors & f:
            break
        factors |= f
    else:
        print("pairwise coprime")
        return
    g = a[0]
    for ai in a[1:]:
        g = gcd(ai, g)
        if g == 1:
            print("setwise coprime")
            return
    print("not coprime")


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

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)


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

for i in range(N):
    f(A[i])

cnt = 1
for i, v in d.items():
    if v != 1:
        cnt = max(cnt, v)

if cnt == N:
    print('not coprime')
elif cnt == 1:
    print('pairwise coprime')
else:
    print('setwise coprime')

Submission status: Wrong Answer

Solution code:
import sys

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

ap=a.copy()
for pp in p:
    lap=len([ai for ai in ap if ai%pp==0])
#    print("pp:",pp,lap)
#    if lap==n:
#        print("not coprime")
#        sys.exit()
    if lap>=2:
        print("setwise coprime")
        sys.exit()
    
print("pairwise coprime")

Submission status: Wrong Answer

Solution code:
from math import gcd


def main():
    n = int(input())
    a = [int(i) for i in input().split()]
    m = max(a)
    p = [i for i in range(m + 1)]
    for i in range(3, m + 1):
        for j in range(2, int(i**.5 + 1) + 1):
            if i % j == 0:
                p[i] = j
                break
    factors = set()
    for ai in a:
        f = set()
        while ai > p[ai]:
            f.add(p[ai])
            ai //= p[ai]
        if not f:
            f.add(ai)
        if factors & f:
            break
        factors |= f
    else:
        print("pairwise coprime")
        return
    g = a[0]
    for ai in a[1:]:
        g = gcd(ai, g)
        if g == 1:
            print("setwise coprime")
            return
    print("not coprime")


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def divisor(n):
    L = []
    for i in range(1,int(n**0.5)+1):

        if n%i == 0:
            L.append(i)
            L.append(n//i)
        if 1 in L:
            L.remove(1)
    return L


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

from math import gcd
from  functools import reduce

flag = False
s = set()
for i in range(n):
    li = divisor(LL[i])
    li = list(set(li))

    for j in range(len(li)):
        if li[j] not in s:
            s.add(li[j])
        else:
            flag = True
            break

a = reduce(gcd,LL)


if not flag and a ==1:
    print("pairwise coprime")
elif  flag and a == 1:
    print("setwise coprime") 
else:
    print("not coprime")

Submission status: Wrong Answer

Solution code:
def divisor(n):
    L = []
    for i in range(1,int(n**0.5)+1):

        if n%i == 0:
            L.append(i)
            L.append(n//i)
        if 1 in L:
            L.remove(1)
    return L


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

from math import gcd
from  functools import reduce

flag = False
li1 = []
s = set()
for i in range(n):
    li = divisor(LL[i])
    li = list(set(li))

    for j in range(len(li)):
        if li[j] not in s:
            s.add(li[j])
        else:
            flag = True
            #print(flag,li[j])
            break
            li1.append(li[j])

if len(LL) < len(li1):
    flag = True
a = reduce(gcd,LL)


if not flag and a ==1:
    print("pairwise coprime")
elif  flag and a == 1:
    print("setwise coprime") 
else:
    print("not coprime")

Submission status: Wrong Answer

Solution code:

import sys

def enum_div(n):
    ir=int(n**(0.5))+1
    ret=[]
    for i in range(1,ir):
        if n%i == 0:
            ret.append(i)
            if (i!= 1) & (i*i != n):
                ret.append(n//i)
    return ret


n=int(input())
ap=list(map(int,input().split()))
amin=min(ap)

if amin!=1:
    bp=enum_div(amin)+[amin]
#bp.sort()
    bp=bp[1:]
    for bpi in bp:
        lap=len([ai for ai in ap if ai%bpi==0])
        if lap==n:
            print("not coprime")
            sys.exit()

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


ptype="pairwise coprime"
for pp in p:
    lap=len([ai for ai in ap if ai%pp==0])
#    print("pp:",pp,lap)
    if lap==n:
        ptype="not coprime"
#        print("not coprime")
        break
    if lap>=2:
#        if ptype!="not coprime":
        ptype="setwise coprime"

print(ptype)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline


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

    counts = [0] * (10**6 + 1)
    for a in A:
        counts[a] += 1

    ans = 0
    for i in range(2, 10**6+1):
        co_primes = 0
        for j in range(i, 10**6+1, i):
            co_primes += counts[j]
        if ans < co_primes:
            ans = co_primes

    if ans == 1:
        print("pairwise coprime")
    elif ans < n:
        print("setwise coprime")
    else:
        print("not coprime")


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import numpy as np
from math import gcd
from functools import reduce

PC = True
SC = True

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

p = reduce(gcd, A)
if p != 1:
  for i in range(N):
    for j in range(N-1, i, -1):
      if A[i] < np.sqrt(A[j]):
        break
      if gcd(A[i],A[j]) != 1:
        PC = False
        break
else:
  PC = False
  SC = False
      
if PC == True:
  print('pairwise coprime')
else:
  if SC == True:
    print('setwise coprime')
  else:
    print('not coprime')

Submission status: Wrong Answer

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

dp = [0] * (max_A)
for i in range(N):
    dp[A[i]] += 1

pairwize = True

for i in range(2, max_A):
    cnt = 0
    # 素数の倍数がdp配列に存在するか。自分以外にあれば2以上になる
    for j in range(i, max_A, i):
        cnt += dp[j]
    if cnt > 1:
        pairwize = False

if pairwize:
    print("pairwize coprime")
    exit()

from math import gcd

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

Submission status: Wrong Answer

Solution code:
from math import *
from collections import *
n=int(input())
a=list(map(int,input().split()))
g=[[]for i in range(10**6+2)]
l=[]
for i in range(2,10**6+1):
    for j in (i,10**6+1,i):
        g[j].append(i)
flg1,flg2=True,True
for i in a:
    for j in g[i+1]:
        if j not in l:
            l.append(j)
        else:
            flg1=False
tmp=a[0]
for i in a:
    tmp=gcd(tmp,i)
if tmp>1:
    flg2=False
if flg1:
    print("pairwise coprime")
    exit()
if flg2:
    print("setwise coprime")
    exit()
print("not coprime")

Submission status: Wrong Answer

Solution code:

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

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

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

    return arr

n = int(input())
data = list(map(int, input().split()))
count = {}
for a in data:
    for factor, _ in factorization(a):
        count[factor] = count.get(factor, 0) + 1
pc = True
sc = True
for value in count.values():
    if value != 1:
        pc = False
    if value == n:
        sc = False
if pc is True:
    print("pairwise coprime")
elif sc is True:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Wrong Answer

Solution code:
import numpy as np
from math import gcd
from functools import reduce

PC = True
SC = True

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

p = reduce(gcd, A)
if p != 1:
  for i in range(N):
    for j in range(N-1, i, -1):
      if A[i] < np.sqrt(A[j]):
        break
      if gcd(A[i],A[j]) != 1:
        PC = False
        break
else:
  SC = False
      
if PC == True:
  print('pairwise coprime')
else:
  if SC == True:
    print('setwise coprime')
  else:
    print('not coprime')

Submission status: Wrong Answer

Solution code:
import numpy as np


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

    counts = [0] * (10**6 + 1)
    for a in A:
        counts[a] += 1

    A = np.array(A, dtype=np.int64)

    ans = 0
    for i in range(2, 10**6+1):
        co_primes = A[i+i::i].sum()
        if ans < co_primes:
            ans = co_primes

    if ans == 1:
        print("pairwise coprime")
    elif ans < n:
        print("setwise coprime")
    else:
        print("not coprime")


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import numpy as np

def calc_gcd(a,b):
  r = a % b
  while r != 0:
    a, b = b, r
    r = a % b
  return b

PC = True
AC = True
glst = []

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

for i in range(N):
  for j in range(N-1, i, -1):
    if A[i] < np.sqrt(A[j]):
      break
    gcd = calc_gcd(A[i],A[j])
    glst.append(gcd)
    if gcd != 1:
      PC = False
      if glst.count(gcd) != 1:
        AC = False
        break
      
if PC == True:
  print('pairwaise coprime')
else:
  if AC == True:
    print('setwise coprime')
  else:
    print('not coprime')

Submission status: Wrong Answer

Solution code:
import math
import sys
import random

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

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

def sieve_of_erastosthenes(num):
    input_list = [False if i % 2 == 0 or i % 3 == 0 or i % 5 == 0 else True for i in range(num)]
    input_list[0] = input_list[1] = False
    input_list[2] = input_list[3] = input_list[5] = True
    sqrt = math.sqrt(num)

    for serial in range(3, num, 2):

        if serial >= sqrt:
            return input_list

        for s in range(serial ** 2, num, serial): 
            input_list[s] = False

input_list = sieve_of_erastosthenes(10**6+1)
prime_list = [i for i, b in enumerate(input_list) if b == True]

def factorization(n):
    arr = []
    temp = n
    for i in prime_list:
        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
random.shuffle(a)
g = a[0]
arr = factorization(a[0])
used = set()
for i in arr:
    if i == 1: continue
    used.add(i)

# not coprimeか判定
for i in range(n-1):
    g = gcd(g, a[i+1])
if g > 1:
    print('not coprime')
    exit(0)

# pairwise coprimeか判定
used = [0] * (10**6+1)
pair = True
for _a in a:
    if used[_a]:
        print('setwise coprime')
        exit(0)
    else:
        used[_a] = True

for p in prime_list:
    v = p
    cnt = 0
    while v < 10**6+1:
        if used[v]:
            cnt+=1
        v += p
    if cnt > 1:
        print('setwise coprime')
        exit(0)
print('pairwise coprime')

Submission status: Wrong Answer

Solution code:
import numpy as np


def get_primes(a=10 ** 6) -> np.array:
    table = np.ones(a + 1)
    table[:2] = False
    for i in range(2, a):
        table[i + i::i] = False
    primes = np.where(table == True)[0]
    return primes


def main():
    n = int(input())
    A = np.array(input().split(), dtype=np.int64)
    primes = get_primes(A.max())

    if A.max() == 1:
        print("pairwise coprime")

    co_count = 0
    for prime in primes.tolist():
        count = (A % prime == 0).sum()
        co_count = max(count, co_count)

    if co_count == 1:
        print("pairwise coprime")
    elif co_count != n:
        print("setwise coprime")
    else:
        print("not coprime")


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import math
import sys
import random

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

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

def sieve_of_erastosthenes(num):
    input_list = [False if i % 2 == 0 or i % 3 == 0 or i % 5 == 0 else True for i in range(num)]
    input_list[0] = input_list[1] = False
    input_list[2] = input_list[3] = input_list[5] = True
    sqrt = math.sqrt(num)

    for serial in range(3, num, 2):

        if serial >= sqrt:
            return input_list

        for s in range(serial ** 2, num, serial): 
            input_list[s] = False

input_list = sieve_of_erastosthenes(int(-(-1000//1))+1)
prime_list = [i for i, b in enumerate(input_list) if b == True]

def factorization(n):
    arr = []
    temp = n
    for i in prime_list:
        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
random.shuffle(a)
g = a[0]
arr = factorization(a[0])
used = set()
for i in arr:
    if i == 1: continue
    used.add(i)

# not coprimeか判定
for i in range(n-1):
    g = gcd(g, a[i+1])
if g > 1:
    print('not coprime')
    exit(0)

# pairwise coprimeか判定
used = [0] * (10**6+1)
pair = True
for _a in a:
    if used[_a]:
        print('setwise coprime')
        exit(0)
    else:
        used[_a] = True

for p in prime_list:
    v = p
    cnt = 0
    while v < 10**6+1:
        if used[v]:
            cnt+=1
        v += p
    if cnt > 1:
        print('setwise coprime')
        exit(0)
print('pairwise coprime')

Submission status: Wrong Answer

Solution code:
import math
n = int(input())
alist = list(map(int,input().split()))

mod = 10**9 + 7
prod = 1

a_max = max(alist)
D = [math.inf]*(a_max+1)
D[0] = 1
D[1] = 1
p = 2
for i in range(1,a_max+1):
    if D[i] == math.inf:
        p = i
        mul_p = p
        while mul_p <= a_max:
            D[mul_p] = min(p,D[mul_p])
            mul_p += p


def factor(n):
    f = []
    f.append(n)
    while n > 1:
        f.append(D[n])
        n //= D[n]
    f.append(1)
    return f

factor_set = set()
pairwise = True
for i in range(n):
    a = alist[i]

    a_factor = factor(a)
    for f in a_factor:
        if f != 1 and f in factor_set:
            pairwise = False
            break
        factor_set.add(f)

    if pairwise == False:
        break
if pairwise == True: 
    print("pairwise coprime")
    exit()

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

#setwise
now = alist[0]
for i in range(1,n-1):
    now = gcf(now,gcf(alist[i],alist[i+1]))

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