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())
aa=list(map(int,input().split()))
a=[x for x in aa if x!=1]
n=len(a)
if n<=1:
  print('pairwise coprime')
  exit()
  
# 素因数分解
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
tmp=[i for i,j in factorization(min(a))]
not_flg=False
for t in tmp:
  flg=True
  for x in a:
    if x%t==0:
      pass
    else:
      flg=False
      break
  if flg:
    not_flg=flg
    break
if not_flg:
  print('not coprime')
  exit()
#if n>78499:
if n>99999:
  print('setwise coprime')
  exit()
ary=set(())
for x in a:
  tmp={i for i,j in factorization(x)}
  for t in tmp:
    if t in ary:
      print('setwise coprime')
      exit()
    else:
      ary.add(t)
print('pairwise coprime')

Submission status: Wrong Answer

Solution code:
#coding: utf-8

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

maxA = max(A)
primes = [2]
for i in range(2, maxA):
    if all(i % p != 0 for p in primes):
        primes.append(i)

maxNumDiv = 0
for p in primes:
    numDiv = sum(1 for a in A if a % p == 0) 
    maxNumDiv = max(numDiv, maxNumDiv)

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

Submission status: Wrong Answer

Solution code:
def resolve():
    import sys
    from fractions import gcd
    input = sys.stdin.readline
    n=int(input())
    a=list(map(int,input().split()))
    m=10**6+5
    chk=[0]*m
    for i in a:
      chk[i]+=1
    pw=1
    for i in range(2,m):
      cnt=0
      for j in range(i,m,i):
        cnt+=chk[j]
      if cnt>1:
        pw=0
        break
    g=a[0]
    for i in a[1:]:
      g=gcd(g,i)
    if pw==2:
      print('pairwise coprime')
    elif g==1:
      print('setwise coprime')
    else:
      print('not coprime')

if __name__ == '__main__':
    resolve()

Submission status: Wrong Answer

Solution code:
#coding: utf-8

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

maxA = max(A)
primes = [2]
for i in range(2, maxA):
    if i * i > maxA: break
    if all(i % p != 0 for p in primes):
        primes.append(i)

maxNumDiv = 0
for p in primes:
    numDiv = sum(1 for a in A if a % p == 0) 
    maxNumDiv = max(numDiv, maxNumDiv)

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

Submission status: Wrong Answer

Solution code:
import sys
import bisect
from functools import lru_cache
from collections import defaultdict
inf = float('inf')
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10**6)
def input(): return sys.stdin.readline().rstrip()
def read():
  return int(readline())
def reads():
  return map(int, readline().split())
N=read()
A=list(reads())
import math

def create_sieve(n):
    sieve = [0] * (n + 1)

    for i in range(2, n + 1):
        if sieve[i] == 0:
            j = i ** 2
            while j <= n:
                sieve[j] = i
                j += i

    return sieve
def fast_factorization(n, sieve):
    from collections import Counter
    arr = Counter()
    while n > 1:
        p = sieve[n]
        if p == 0:
            arr[n] += 1
            break
        else:
            arr[p] += 1
            n //= p
    return arr
M = 10 ** 6
sieve = create_sieve(M)
done = set() # 素数の重複をチェックするためのset
dic=defaultdict(int)
res=""
for i in range(N-1,-1,-1):
  ls = fast_factorization(A[i], sieve)
  for lval in ls:
      dic[lval]+=1
  for j in range(len(ls)):
          if dic[ls[j]]!=1: 
              res=""
              break
          if j==len(ls)-1:
              res="pairwise coprime"
if res!="":
    print(res)
    exit()
for val in dic.values():
    if val==N:
        res="not coprime"
        print(res)
        exit()
print("setwise coprime")

Submission status: Wrong Answer

Solution code:
from math import gcd


def main():
    input()  # N
    array = [int(x) for x in input().split()]
    MAX_A = 10 ** 6 + 2
    histgram = [0] * MAX_A
    for x in array:
        histgram[int(x)] += 1
    pairwise = True
    for divider in range(2, MAX_A):
        count = 0
        for counted in histgram[divider::divider]:
            count += counted
        if count > 1:
            pairwise = False
    if pairwise:
        return 'pairwise coprime'
    gcd_now = 1
    for x in array:
        gcd_now = gcd(x, gcd_now)
    if gcd_now == 1:
        return 'setwise coprime'
    else:
        return 'not coprime'


if __name__ == '__main__':
    print(main())

Submission status: Wrong Answer

Solution code:
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
# def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  N=I()
  A=LI()
  
  l=[0]*1000100
  for x in A:
    for y in range(2,int(math.sqrt(x))+1):
      if x%y==0:
        a=x//y
        l[y]+=1
        if y!=a:
          l[a]+=1

  # print(l[:10])

  f1=True
  f2=False
  for x in l:
    if x>1:
      f1=False

  if f1:
    return 'pairwise coprime'

  g=0
  for x in A:
    g=math.gcd(g,x)

  if g==1:
    return 'setwise coprime'

  return 'not coprime'

# main()
print(main())

Submission status: Wrong Answer

Solution code:
import fractions
import functools

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

factors = [[] for _ in range(int(1e6)+1)]
for i in range(2, int(1e3)+1):
    for j in range(i, int(1e6)+1, i):
        factors[j].append(i)

def classify():
    set_factors = [False]*int(1e6+1)
    for a in A:
        for f in factors[a]:
            if set_factors[f]: break
            set_factors[f] = True
    else:
        return 'pairwise coprime'

    if functools.reduce(fractions.gcd, A) == 1:
        return 'setwise coprime'

    return 'not coprime'

print(classify())

Submission status: Wrong Answer

Solution code:
import numpy as np
import numba
from numba import njit, b1, i4, i8, f8

@njit((i8, i8[:]), cache=True)
def main(N,A):
  Amax = np.max(A)
  lis = np.zeros(Amax+1, np.int64)
  for i in range(N):
    lis[A[i]] += 1
  setwise = False
  for t in range(2,Amax+1):
    cnt = np.sum(lis[i:Amax+1:t])
    if cnt==N:
      return 'not coprime'
    if 2<=cnt<N:
      setwise=True
  if setwise==True:
    return 'setwise coprime'
  return 'pairwise coprime'

N = int(input())
A = np.array(list(map(int, input().split())))
print(main(N,A))

Submission status: Wrong Answer

Solution code:
import sys
import bisect
from functools import lru_cache
from collections import defaultdict
inf = float('inf')
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10**6)
def input(): return sys.stdin.readline().rstrip()
def read():
  return int(readline())
def reads():
  return map(int, readline().split())
N=read()
A=list(reads())
import math
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')
    dic=defaultdict(list)
    limit = math.sqrt(n)
    data = [i + 1 for i in range(1, n)]
    fulldata=data[:]
    while True:
        p = data[0]
        if len(data)==1:
            dic[p].append(p)
            return dic
        for e in fulldata :
            if e%p==0:
                dic[e].append(p)
        data = [e for e in data if e % p != 0]
data = get_sieve_of_eratosthenes(10**1)
dic=defaultdict(int)
res=""
for i in range(N-1,-1,-1):
  ls=data[A[i]]
  for lval in ls:
      dic[lval]+=1
  for j in range(len(ls)):
          if dic[ls[j]]!=1: 
              res=""
              break
          if j==len(ls)-1:
              res="pairwise coprime"
if res!="":
    print(res)
    exit()
for val in dic.values():
    if val==N:
        res="not coprime"
        print(res)
        exit()
print("setwise coprime")

Submission status: Wrong Answer

Solution code:
import sys
import bisect
from functools import lru_cache
from collections import defaultdict
inf = float('inf')
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10**6)
def input(): return sys.stdin.readline().rstrip()
def read():
  return int(readline())
def reads():
  return map(int, readline().split())
N=read()
A=list(reads())
import math
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')
    dic=defaultdict(list)
    limit = math.sqrt(n)
    data = [i + 1 for i in range(1, n)]
    while True:
        p = data[0]
        if limit <= p:
            dic[p].append(p)
            return dic
        for e in data :
            if e%p==0:
                dic[e].append(p)
        data = [e for e in data if e % p != 0]
data = get_sieve_of_eratosthenes(10**6)
#print(data)
dic=defaultdict(int)
res=""
for i in range(N-1,-1,-1):
  ls=data[A[i]]
  for lval in ls:
      dic[lval]+=1
  for j in range(len(ls)):
          if dic[ls[j]]!=1: 
              res=""
              break
          if j==len(ls)-1:
              res="pairwise coprime"
if res!="":
    print(res)
    exit()
for val in dic.values():
    if val==N:
        res="not coprime"
        print(res)
        exit()
print("setwise coprime")

Submission status: Wrong Answer

Solution code:
import sys
import bisect
from functools import lru_cache
from collections import defaultdict
inf = float('inf')
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10**6)
def input(): return sys.stdin.readline().rstrip()
def read():
  return int(readline())
def reads():
  return map(int, readline().split())
N=read()
A=list(reads())
import math
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')
    dic=defaultdict(list)
    limit = math.sqrt(n)
    data = [i + 1 for i in range(1, n)]
    while True:
        p = data[0]
        if limit <= p:
            dic[p].append(p)
            return dic
        for e in data :
            if e%p==0:
                dic[e].append(p)
        data = [e for e in data if e % p != 0]
data = get_sieve_of_eratosthenes(10**6)
#print(data)
dic=defaultdict(int)
res=[i for i in range(N)]
for i in range(N-1,-1,-1):
  ls=data[A[i]]
  for lval in ls:
      dic[lval]+=1
  if i!=N-1:
      for j in range(len(ls)):
          if dic[ls[j]]!=1: 
              res=""
              break
          if j==len(ls)-1:
              res="pairwise coprime"
if res!="":
    print(res)
    exit()
for val in dic.values():
    if val==N:
        res="not coprime"
        print(res)
        exit()
print("setwise coprime")

Submission status: Wrong Answer

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

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

from functools import reduce

import math

alls = reduce(math.gcd, A)

if alls != 1:
  print("not coprime")
  exit(0)
  
# 素因数のペアが存在するかを探す
facts = [False] * (10 ** 6)

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

for a in A:
  cur = factorization(a)
  for f in cur:
    if facts[f[0]]:
      print("setwise coprime")
      exit(0)
    else:
      facts[f[0]] = True
else:
  print("pairwise coprime")

Submission status: Wrong Answer

Solution code:
def resolve():
    import sys
    input = sys.stdin.readline
    n=int(input())
    a=sorted(list(map(int,input().split())))
    ma=a[-1]
    pn=[i for i in range(ma+1)]
    for i in range(2,ma//2+1):
      j=2
      while j*i<=ma:
        pn[j*i]=i
        j+=1
    chk=[0]*(ma+1)
    for i in a:
      if i==1:
        continue
      x=pn[i]
      chk[x]+=1
      while x!=i:
        while i%x==0:
          i//=x
        x=pn[i]
        chk[x]+=1
    ans=2
    for i in chk[2:]:
      if i==n:
        ans=0
        break
      if i>=2:
        ans=1
    if ans==2:
      print('pairwise coprime')
    elif ans==1:
      print('setwise coprime')
    else:
      print('not coprime')

if __name__ == '__main__':
    resolve()

Submission status: Wrong Answer

Solution code:
M=10**6+1
f=lambda p: exit(print(['pairwise','setwise','not'][p]+' coprime'))
n,*l=map(int,open(0).read().split())
from math import *
g,C=0,[0]*M
for x in l:
  g=gcd(g,x)
  C[x]=1
if g>1: f(2)
if all(sum(C[i::i])>1 for i in range(2,M)): f(1)
f(0)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
from bisect import bisect_right

import math
from functools import reduce

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

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

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

P = primes(10**6)

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

check = [0]*(10**6)
flag = 0
for a in A:
    if a == 1:
        continue
    temp = 0
    for i in range(bisect_right(P, int(a**0.5+10))):
        if a%P[i] == 0:
            if check[P[i]] == 1:
                flag = 1
            else:
                check[P[i]] = 1
            temp = 1
    if temp == 0 and check[a] == 1:
        flag = 1
    if not temp:
        check[a] = 1
    if flag:
        break

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

Submission status: Wrong Answer

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

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())
    A = list(map(int, readline().split()))
    used = [False] * (max(A) + 1)
    pairwise = True
    for a in A:
        for i in range(2, int(a ** 0.5) + 1):
            if a % i == 0:
                if used[i]:
                    pairwise = False
                    break
                else:
                    used[i] = True
                    while a % i == 0:
                        a //= i
        else:
            if a != 1:
                if used[a]:
                    pairwise = False
                    break
                else:
                    used[a] = True
                    continue
        break

    g = reduce(gcd, A)

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


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from math import gcd

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

def isSetwise(A):
    ret = A[0]
    for a in A:
        ret = gcd(ret, a)
    return ret == 1
from collections import Counter

def createPrimeList(N):
    isPrime = [True] * (N + 1)
    isPrime[0] = False
    isPrime[1] = False
    smallestPrime = [1] * (N + 1)
    for i in range(2, N + 1):
        if not isPrime[i]:
            continue
        for p in range(i * 2, N, i):
            if isPrime[p]:
                smallestPrime[p] = i
            isPrime[p] = False
    return smallestPrime

from collections import Counter
smallestPrime = createPrimeList(max(A) + 10)
def primeFactorization(N):
    ret = Counter()
    while N > 1:
        p = smallestPrime[N]
        if p == 1:
            break
        ret[p] += 1
        N //= p
    return ret

def isPairwise(A):
    P = Counter()
    for a in A:
        for p in primeFactorization(a):
            if P[p] >= 1:
                return False
            P[p] += 1
    return True

if not isSetwise(A):
    print('not coprime')
    exit()

if isPairwise(A):
    print('pairwise coprime')
else:
    print('setwise coprime')

Submission status: Wrong Answer

Solution code:
from math import gcd

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

def isSetwise(A):
    ret = A[0]
    for a in A:
        ret = gcd(ret, a)
    return ret == 1
from collections import Counter

def createPrimeList(N):
    isPrime = [True] * (N + 1)
    isPrime[0] = False
    isPrime[1] = False
    smallestPrime = [1] * (N + 1)
    for i in range(2, N + 1):
        if not isPrime[i]:
            continue
        for p in range(i * 2, N, i):
            if isPrime[p]:
                smallestPrime[p] = i
            isPrime[p] = False
    return smallestPrime

from collections import Counter
smallestPrime = createPrimeList(max(A) + 10)
def primeFactorization(N):
    ret = Counter()
    while N > 1:
        p = smallestPrime[N]
        if p == 1:
            break
        ret[p] += 1
        N //= p
    return ret

def isPairwise(A):
    P = Counter()
    for a in A:
        for p in primeFactorization(a):
            if P[p] > 1:
                return False
            P[p] += 1
    return True

if not isSetwise(A):
    print('not coprime')
    exit()

if isPairwise(A):
    print('pairwise coprime')
else:
    print('setwise coprime')

Submission status: Wrong Answer

Solution code:
N = int(input())

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

max_a = max(A)

set_a = set(A)
if len(set_a) == 1 and 1 in set_a:
    print('pairwise coprime')
    exit()

setFlag = False

if len(set_a) != len(A):
    setFlag = True

for i in range(2,int(max_a**0.5)+2):
    tmp_count = 0
    pairFlag = True
    for key,a in enumerate(set_a):
        if a%i == 0:
            tmp_count += 1
            if 1 == tmp_count or tmp_count == key+1:
                continue
            else:
                setFlag = True
                break
        else:
            pairFlag = False
    if pairFlag:
        print('not coprime')
        exit()

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

Submission status: Wrong Answer

Solution code:
from math import gcd

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

def isSetwise(A):
    ret = A[0]
    for a in A:
        ret = gcd(ret, a)
    return ret == 1

def isPairwise(A):
    A.sort()
    mx = max(A)
    V = set()

    for a in A:
        if a in V:
            return False
        n = a
        while n < mx:
            V.add(n)
            n += a
    return True

if not isSetwise(A):
    print('not coprime')
    exit()

if isPairwise(A):
    print('pairwise coprime')
else:
    print('setwise coprime')

Submission status: Wrong Answer

Solution code:
from math import gcd

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

def isSetwise(A):
    ret = A[0]
    for a in A:
        ret = gcd(ret, a)
    return ret == 1

def isPairwise(A):
    mx = max(A)
    V = set()

    for a in A:
        if a in V:
            return False
        n = a
        while n < mx:
            V.add(n)
            n += a
    return True

if not isSetwise(A):
    print('not coprime')
    exit()

if isPairwise(A):
    print('pairwise coprime')
else:
    print('setwise coprime')

Submission status: Wrong Answer

Solution code:
import numpy as np
from numba import njit

n = int(input())
a = list(map(int, input().split()))
MAX = 10 ** 6

nums = np.zeros(MAX + 1, np.int64)
for e in a:
    nums[e] += 1


@njit
def solve(nums):
    mx = 0
    for i in range(2, MAX + 1):
        cnt = nums[i::i].sum()
        mx = max(mx, cnt)

    return mx


mx = solve(nums)

if mx == n:
    ans = "not coprime"
elif mx == 1:
    ans = "pairwise coprime"
else:
    ans = "setwise coprime"

print(ans)

Submission status: Wrong Answer

Solution code:
from math import gcd

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

def isSetwise(A):
    ret = A[0]
    for a in A:
        ret = gcd(ret, a)
    return ret == 1

def createPrimeList(N, isTable=True):
    isPrime = [True] * (N + 1)
    isPrime[0] = False
    isPrime[1] = False
    for i in range(2, N + 1):
        if not isPrime[i]:
            continue
        for p in range(i * 2, N, i):
            isPrime[p] = False
    return isPrime if isTable else [i for i in range(2, N) if isPrime[i]]

def isPairwise(A):
    primes = createPrimeList(max(A), isTable=False)
    if len(set(A)) < N:
        return False

    for p in primes:
        cnt = 0
        for a in A:
            if a % p == 0:
                cnt += 1
            if cnt > 1:
                return False
    return True

if not isSetwise(A):
    print('not coprime')
    exit()

if isPairwise(A):
    print('pairwise coprime')
else:
    print('setwise coprime')

Submission status: Wrong Answer

Solution code:
from math import gcd

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

def isSetwise(A):
    ret = A[0]
    for a in A:
        ret = gcd(ret, a)
    return ret == 1

def createPrimeList(N, isTable=True):
    isPrime = [True] * (N + 1)
    isPrime[0] = False
    isPrime[1] = False
    for i in range(2, N + 1):
        if not isPrime[i]:
            continue
        for p in range(i * 2, N, i):
            isPrime[p] = False
    return isPrime if isTable else [i for i in range(2, N) if isPrime[i]]

def isPairwise(A):
    primes = createPrimeList(int(max(A)**0.5) + 10, isTable=False)
    if len(set(A)) < N:
        return False

    for p in primes:
        cnt = 0
        for a in A:
            if a % p == 0:
                cnt += 1
            if cnt > 1:
                return False
    return True

if not isSetwise(A):
    print('not coprime')
    exit()

if isPairwise(A):
    print('pairwise coprime')
else:
    print('setwise coprime')

Submission status: Wrong Answer

Solution code:
from math import gcd

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

def isSetwise(A):
    ret = A[0]
    for a in A:
        ret = gcd(ret, a)
    return ret == 1

def createPrimeList(N, isTable=True):
    isPrime = [True] * (N + 1)
    isPrime[0] = False
    isPrime[1] = False
    for i in range(2, N + 1):
        if not isPrime[i]:
            continue
        for p in range(i * 2, N, i):
            isPrime[p] = False
    return isPrime if isTable else [i for i in range(2, N) if isPrime[i]]

from collections import Counter
primeList = createPrimeList(10**5, False)
def primeFactorization2(N):
    primes = Counter()
    for p in primeList:
        while N % p == 0:
            N //= p
            primes[p] += 1
    return primes

def isPairwise(A):
    A = [primeFactorization2(a) for a in A]
    return True

if not isSetwise(A):
    print('not coprime')
    exit()

if isPairwise(A):
    print('pairwise coprime')
else:
    print('setwise coprime')

Submission status: Wrong Answer

Solution code:
import sys,random
from math import gcd
input=sys.stdin.readline
n=int(input())
*a,=map(int, input().split())
random.shuffle(a)
tmp=a[0]
for i in range(1,n):
    tmp=gcd(tmp,a[i])
if tmp>1:
    print('not coprime')
    exit()

# pairwize coprime なら素因数が2度現れることはない

def f(x):
    res=set()
    for i in range(2,int(x**(1/2))+3):
        if x%i==0:
            while x%i==0:
                x//=i
            res.add(i)
    if x>1:
        res.add(x)
    return res,x
tmp=set()
tmp2=set()
for ai in a:
    for p in tmp:
        if ai%p==0:
            print('setwise coprime')
            exit()
    pp,x=f(ai)
    tmp|=pp 
    if x>1 and x in tmp2:
        print('setwise coprime')
        exit()
    tmp.add(x)
    
        
print('pairwise coprime')

Submission status: Wrong Answer

Solution code:
from math import gcd

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

def isSetwise(A):
    ret = A[0]
    for a in A:
        ret = gcd(ret, a)
    return ret == 1

def isPairwise(A):
    return True

if not isSetwise(A):
    print('not coprime')
    exit()

if isPairwise(A):
    print('pairwise coprime')
else:
    print('setwise coprime')

Submission status: Wrong Answer

Solution code:
import sys,random
from math import gcd
input=sys.stdin.readline
n=int(input())
*a,=map(int, input().split())
random.shuffle(a)
tmp=a[0]
for i in range(1,n):
    tmp=gcd(tmp,a[i])
if tmp>1:
    print('not coprime')
    exit()

# pairwize coprime なら素因数が2度現れることはない

def f(x):
    res=set()
    for i in range(2,int(x**(1/2))+3):
        if x%i==0:
            while x%i==0:
                x//=i
            res.add(i)
    return res
tmp=set()
for ai in a:
    for p in tmp:
        if ai%p==0:
            print('setwise coprime')
            exit()
    pp=f(ai)
    tmp|=pp 
print('pairwise coprime')

Submission status: Wrong Answer

Solution code:
import sys,random
from math import gcd
input=sys.stdin.readline
n=int(input())
*a,=map(int, input().split())
random.shuffle(a)
tmp=a[0]
for i in range(1,n):
    tmp=gcd(tmp,a[i])
if tmp>1:
    print('not coprime')
    exit()

# pairwize coprime なら素因数が2度現れることはない

def f(x):
    res=set()
    for i in range(2,int(x**(1/2))+3):
        if x%i==0:
            while x%i==0:
                x//=i
            res.add(i)
    return res
tmp=set()
for ai in a:
    for p in tmp:
        if ai%p==0:
            print('setwize coprime')
            exit()
    pp=f(ai)
    tmp|=pp 
print('pairwize coprime')

Submission status: Wrong Answer

Solution code:
#abc177 e
import sys,math,collections,itertools
import functools
input = sys.stdin.readline


N=int(input())
A=list(map(int,input().split()))
num = [0]*(10**6+1)

fact = [0]*(10**6+1)
mn = 1
for a in A:
    if a != 1:
        temp = a
        i=2
        if mn>1:
            break
        if temp%i==0:
            while temp%i==0:
                temp //= i
            flag = 1
            fact[i]+=1
            mn = max(mn,fact[i])
            if mn>1:
                break
        
        for i in range(3, int(-(-a**0.5//1))+1,2):
            if temp%i==0:
                while temp%i==0:
                    temp //= i
                flag = 1
                fact[i]+=1
                mn = max(mn,fact[i])
                if mn>1:
                    break
        if temp!=1:
            fact[temp]+=1
            mn = max(mn,fact[i])
            if mn>1:
                break

if mn == 1:
    print('pairwise coprime')
else:
    if functools.reduce(math.gcd,A)!=1:
        print('not coprime')
    else:
        print('setwise coprime')

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
import collections

def main():
    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

    input = sys.stdin.readline
    n = int(input())
    a = list(map(int, input().split()))
    cnt = collections.defaultdict(int)
    for i in a:
        for fact in factorization(i):
            cnt[fact] += 1

    flag = False
    for i in dict(cnt).values():
        if i == n:
            print("not coprime")
            exit()
        if i != 1:
            flag = True
            break
    
    if flag:
        print("setwise coprime")
    else:
        print("pairwise coprime")


    


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#abc177 e
import sys,math,collections,itertools
input = sys.stdin.readline


N=int(input())
A=list(map(int,input().split()))
num = [0]*(10**6+1)

fact = [0]*(10**6+1)
fact[1]=1

mn = 1
for a in A:
    if a != 1:
        flag = 0
        temp = a
        i=2
        if temp%i==0:
            while temp%i==0:
                temp //= i
            flag = 1
            fact[i]+=1
            mn = max(mn,fact[i])
        
        for i in range(3, int(-(-a**0.5//1))+1,2):
            if temp%i==0:
                while temp%i==0:
                    temp //= i
                flag = 1
                fact[i]+=1
                mn = max(mn,fact[i])
        if temp!=1:
            fact[temp]+=1
            mn = max(mn,fact[i])
            flag = 1
        if flag==0:
            fact[n]+=1
            mn = max(mn,fact[i])

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

Submission status: Wrong Answer

Solution code:
#abc177 e
import sys,math,collections,itertools
input = sys.stdin.readline


N=int(input())
A=list(map(int,input().split()))
num = [0]*(10**6+1)

fact = [0]*(10**6+1)
fact[1]=1

mn = 1
for a in A:
    if a != 1:
        flag = 0
        temp = a
        for i in range(2, int(-(-a**0.5//1))+1):
            if temp%i==0:
                while temp%i==0:
                    temp //= i
                flag = 1
                fact[i]+=1
                mn = max(mn,fact[i])
        if temp!=1:
            fact[temp]+=1
            mn = max(mn,fact[i])
            flag = 1
        if flag==0:
            fact[n]+=1
            mn = max(mn,fact[i])

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

Submission status: Wrong Answer

Solution code:
from sys import stdin, stdout
from math import gcd
N=10**6+2
n = int(stdin.readline())
a = list(map(int, stdin.readline().split()))
mp=[0]*N;not_pairwise=1
for v in a:
    mp[v]=1
for i in range(2,N):
    if sum(mp[i::i])>1:
        not_pairwise=0
        break
g = a[0]
for v in a:
    g = gcd(g, v)
if not_pairwise:
    print('pairwise coprime')
elif g == 1:
    print('setwise coprime')
else:
    print('not coprime')