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: Time Limit Exceeded

Solution code:
import collections
N = int(input())
A = list(map(int, input().split()))


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


d = [0]*10**6
a1 = collections.Counter([])
a2 = collections.Counter(prime_factorize(A[0]))
for a in A:
    tmp = prime_factorize(a)
    aa = collections.Counter(tmp)
    a1 += aa
    a2 &= aa
if a2:
    print('not coprime')

elif a1.most_common()[0][1] >= 2:
    print('setwise coprime')
else:
    print('pairwise coprime')

Submission status: Time Limit Exceeded

Solution code:
import math
import numpy as np
(_,), a  = [list(map(int, s.split())) for s in open(0)]

def fast_factorize(num):
    min_factor_list = np.asarray(list(range(num + 1)))
    for i in range(int(math.sqrt(num) + 1), 1, -1):
        min_factor_list[i: num+1: i] = i
    return min_factor_list

min_factor_list = fast_factorize(max(a))

prime_factor_sets = []
for x in a:
    prime_factor_set = set()
    while min_factor_list[x] != 1:
        prime_factor_set.add(min_factor_list[x])
        x //= min_factor_list[x]
    prime_factor_sets.append(prime_factor_set)

g = prime_factor_sets[0].copy()
l = prime_factor_sets[0].copy()
s = 0
for x in prime_factor_sets:
    g &= x
    l |= x
    s += len(x)

if len(g) != 0:
    ans = 'not coprime'
elif len(l) != s:
    ans = 'setwise coprime'
else:
    ans = 'pairwise coprime'
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from math import gcd
N=int(input())
A=list(map(int,input().split()))
for i in range(N-1):
    for j in range(i+1,N):
        g = gcd(A[i],A[j])
        if g != 1:
            break
    else:
        continue
    break
else:
    print("pairwise coprime")
    exit()
s=A.pop(0)
for i in A:
    s = gcd(s,i)
    if s == 1:
        print("setwise coprime")
        break
else:
    print("not coprime")

Submission status: Time Limit Exceeded

Solution code:
import math
(_,), a  = [list(map(int, s.split())) for s in open(0)]

def fast_factorize(num):
    min_factor_list = list(range(num + 1))
    for i in range(int(math.sqrt(num) + 1), 1, -1):
        for j in range(i, num+1, i):
            min_factor_list[j] = i
    return min_factor_list

min_factor_list = fast_factorize(max(a))

prime_factor_sets = []
for x in a:
    prime_factor_set = set()
    while min_factor_list[x] != 1:
        prime_factor_set.add(min_factor_list[x])
        x //= min_factor_list[x]
    prime_factor_sets.append(prime_factor_set)

g = prime_factor_sets[0].copy()
l = prime_factor_sets[0].copy()
s = 0
for x in prime_factor_sets:
    g &= x
    l |= x
    s += len(x)

if len(g) != 0:
    ans = 'not coprime'
elif len(l) != s:
    ans = 'setwise coprime'
else:
    ans = 'pairwise coprime'
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd

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

lst = [0]*(max(As)+1)

s = [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 a in As:
  i = 0
  if a % s[i] == 0:
    lst[s[i]] += 1
  while a % s[i] == 0:
    a //= s[i]
  i += 1
  while i < len(s):
    if s[i]**2 > a:
      break
    if a % s[i] == 0:
      lst[s[i]] += 1  
    while a % s[i] == 0:
      a //= s[i]
    i += 1
  if a > 1:
    lst[a] += 1
    
if max(lst) < 2:
  print('pairwise coprime')
  exit()
  
t = As[0]

for a in As:
  t = gcd(t,a)
  
if t == 1:
  print('setwise coprime')
else:
  print('not coprime')

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N = int(input())
A = list(map(int, input().split()))
exist = np.zeros(10**6+1, dtype=int)
for a in A:
    exist[a] += 1

if np.gcd.reduce(A) != 1:
    print('not coprime')
elif np.all([exist[i::i].sum() <= 1 for i in range(2, 10**6+1)]):
    print('pairwise coprime')
else:
    print('setwise coprime')

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N = int(input())
A = np.array(list(map(int, input().split())))
exist = np.zeros(10**6+1, dtype=int)
exist[A] = 1

if np.gcd.reduce(A) != 1:
    print('not coprime')
elif np.all([exist[i::i].sum() <= 1 for i in range(2, 10**6+1)]):
    print('pairwise coprime')
else:
    print('setwise coprime')

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import math

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

def sieve_of_eratosthenes(n):
    sieve = list(range(n+1))
    m = int(math.sqrt(n))
    for i in range(2, m + 1):
        if sieve[i] < i:
            continue
        for j in range(i * i, n + 1, i):
            if sieve[j] == j:
                sieve[j] = i
    return sieve

def factorize_by_sieve(x, sieve):
    factor = defaultdict(int)
    while sieve[x] != x:
        factor[sieve[x]] += 1
        x //= sieve[x]
    factor[x] += 1
    return factor

n = int(input())
a_list = list(map(int, input().split()))
a_list.sort()

sieve = sieve_of_eratosthenes(a_list[-1])
pairwise = True
setwise = True
primes = set()
x = a_list[0]
for a in a_list:
    x = gcd(x, a)
    if pairwise and a != 1:
        factor = factorize_by_sieve(a, sieve).keys()
        pairwise = primes.isdisjoint(factor)
        primes |= factor

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

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd

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

lst = [0]*(max(As)+1)

for a in As:
  i = 2
  if a % i == 0:
    lst[i] += 1
  while a % i == 0:
    a //= i
  i = 3
  while i**2 <= a:
    if a % i == 0:
      lst[i] += 1  
    while a % i == 0:
      a //= i
    i += 2
  if a > 1:
    lst[a] += 1
    
if max(lst) < 2:
  print('pairwise coprime')
  exit()
  
t = As[0]

for a in As:
  t = gcd(t,a)
  
if t == 1:
  print('setwise coprime')
else:
  print('not coprime')

Submission status: Time Limit Exceeded

Solution code:
class prime_factorize_by_osa_k():
    def __init__(self, max_val):
        '''
        割ることが出来る最小の値を格納したリストを返す
        :param max_val:
        :return:
        '''
        self.minFactor = [-1] * (max_val + 1)
        for i in range(2, max_val + 1):
            if self.minFactor[i] == -1:
                self.minFactor[i] = i
                # エラトステネスの篩と同様の処理を行う
                for j in range(i * i, max_val + 1, i):
                    if self.minFactor[j] == -1:
                        self.minFactor[j] = i

    def osa_k(self, n):
        '''
        preprocessをしたあと、O(logN)で素因数分解を行う。nの最大値をn_maxとする。
        :param n:
        :return:
        '''
        from collections import defaultdict
        d = defaultdict(int)
        now = n
        while now > 1:
            d[self.minFactor[now]] += 1
            now //= self.minFactor[now]
        return d
def gcd(a, b):
    while b: a, b = b, a % b
    return a

N = int(input())
A = list(map(int, input().split()))
# N = 10 ** 6
# A = [10 ** 6] * N
ob = prime_factorize_by_osa_k(10 ** 6)
pairwise = False
prime_key = set(ob.osa_k(A[-1]).keys())
for i in range(N - 2, -1, -1):
    now = set(ob.osa_k(A[i]).keys())
    if prime_key & now:
        break
    else:
        prime_key = now | prime_key
else:
    pairwise = True
if pairwise:
    print('pairwise coprime')
    exit()
work = gcd(A[0], A[1])
for i in range(2, N):
    work = gcd(work, A[i])
if work != 1:
    print('not coprime')
else:
    print('setwise coprime')

Submission status: Time Limit Exceeded

Solution code:
import math
n = int(input())
a = [int(i) for i in input().split()]

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

for i in range(n):
    #if chk[a[i]] == 1 and a[i] >= 2:
    #    print("not coprime")
    #    exit()
    chk[a[i]] += 1

flag = True

for i in range(2,10**6+1):
    #tmp = i
    kake = 1
    num = 0
    #print(i)
    while i * kake <= 10**6:
        if chk[i*kake] >= 2:
            flag = False
            break
        #print(i)
        if chk[i*kake] == 1:
            if num == 1:
                flag = False
                break
            num = 1
            #break
        kake += 1
gcd_num = math.gcd(a[0],a[1])
        
for i in range(n-2):
    gcd_num = math.gcd(gcd_num,a[i+2])
    
if flag == True:
    print("pairwise coprime")
elif gcd_num == 1:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Time Limit Exceeded

Solution code:
from math import gcd
N=int(input())
A=list(map(int, input().split()))


A=sorted(A)
gcda=A[0]
gcdais=True
gcdb=A[0]
MAX=max(A)
counts=[0]*MAX
counts[A[0]-1]+=1
for i in range(1,N):
    
    a=A[i]
    gcdb=gcd(gcdb, a)
    counts[a-1]+=1

for i in range(1,MAX):
    count=0
    now=i+1
    while now<=MAX:
        if counts[now-1]!=0:
            count+=counts[now-1]
        now+=(i+1)
    if count>=2:
        gcdais=False
    #print(count)
    
#print(counts)
if gcdais:
    print("pairwise coprime")
elif gcdb==1:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Time Limit Exceeded

Solution code:
from math import gcd

# = map(int, input().split())
N = int(input())
A = list(map(int, input().split()))
mA = max(A)
primenum = [2]
sgn = [-1 for _ in range(int(mA**0.5)+1)]
k = 3
while k**2 <= mA:
  if sgn[k] == -1:
    primenum.append(k)
    add = k*k
    ok = k
    while ok**2 <= mA:
      sgn[ok] = 1
      ok += add
  k += 2
#prime_num が用意されているとき
primecounter = [0 for _ in range(len(primenum))]
biggerprime = [0 for _ in range(mA+1)]
def factorization(n):
  M = n
  for k in range(len(primenum)):
    p = primenum[k]
    if p**2 > M:
      break
    else:
      if M%p == 0:
        if primecounter[k] == 0:
          primecounter[k] = 1
        else:
          return False
        while M%p == 0:
          M //= p

  if M > 1:
    if biggerprime[M] == 0:
      biggerprime[M] = 1
    else:
      return False
  return True



g = A[0]
flag = True
for k in range(N):
  a = A[k]
  g = gcd(g, a)
  if flag:
    flag = factorization(a)
  if flag == False:
    if g == 1:
      break


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

Submission status: Time Limit Exceeded

Solution code:
import functools
from math import gcd
N = int(input())
A = list(map(int, input().split()))


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[i] = cnt
    if temp!=1:
        arr[temp] = 1
    if arr==[]:
        arr[n] = 1
    return arr


B = []
for a in A:
    B += factorization(a).keys()

if len(set(B)) == len(B):
    print("pairwise coprime")
elif functools.reduce(gcd, A) == 1:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Time Limit Exceeded

Solution code:
from math import gcd
from bisect import insort

N = int(input())
A = list(map(int, input().split()))
mA = max(A)
primenum = [2]
sgn = [-1 for _ in range(int(mA**0.5)+1)]
k = 3
while k**2 <= mA:
  if sgn[k] == -1:
    primenum.append(k)
    add = k*k
    ok = k
    while ok**2 <= mA:
      sgn[ok] = 1
      ok += add
  k += 2
#prime_num が用意されているとき

def binary_search(list, item):
    low = 0
    high = len(list) - 1

    while low <= high:
        mid = (low + high) //2
        guess = list[mid]
        if guess == item:
            #return mid
            return True
        if guess > item:
            high = mid -1
        else:
            low = mid + 1

    #return None
    return False

primecounter = [0 for _ in range(len(primenum))]
biggerprime = []
def factorization(n):
  M = n
  for k in range(len(primenum)):
    p = primenum[k]
    if p**2 > M:
      break
    else:
      if M%p == 0:
        if primecounter[k] == 0:
          primecounter[k] = 1
        else:
          return False
        while M%p == 0:
          M //= p

  if M > 1:
    if binary_search(biggerprime, M):
      return False
    else:
      insort(biggerprime, M)
  return True



g = A[0]
flag = True
for k in range(N):
  a = A[k]
  g = gcd(g, a)
  if flag:
    flag = factorization(a)
  if flag == False:
    if g == 1:
      break


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

Submission status: Time Limit Exceeded

Solution code:
from math import gcd


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


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

# setwise
tmp = 0
for a in A:
    tmp = gcd(tmp, a)
isSetwise = (tmp == 1)


# pairwise
M = 10 ** 6
sieve = create_sieve(M)
done = set()
isPairwise = True
for a in A:
    arr = fast_factorization(a, sieve)
    for p in arr.keys():
        if p in done:
            isPairwise = False
        else:
            done.add(p)

# check
if isPairwise:
    ans = 'pairwise coprime'
elif isSetwise:
    ans = 'setwise coprime'
else:
    ans = 'not coprime'
print(ans)

Submission status: Time Limit Exceeded

Solution code:

def main():
    N = int(input())
    A = list(map(int, input().split()))
    maxA = max(A)
    # エラトステネスの篩
    sieve = [0] * (maxA + 1)
    sieve[0] = sieve[1] = -1
    for i in range(maxA+1):
        if sieve[i] != 0:
            continue
        for j in range(i, maxA+1, i):
            if sieve[j] == 0:
                sieve[j] = i

    # 素因数分解
    primelist = []
    lenprimelist = 0
    for i in range(N):
        tmpset = set()
        j = A[i]
        for _ in range(N):
            tmp = sieve[j]
            if tmp <= 0:
                break
            tmpset.add(tmp)
            j = j//tmp
        lenprimelist += len(tmpset)
        primelist.append(tmpset)
    
    # 素因数の和集合を取ったときに, 元の素因数の配列の長さから小さくなっている 
    #   => ある i, j で共通する素因数を持つAi, Ajが存在する
    #   => pairwise coprime ではない
    # 全ての素因数の配列に対して共通部分を取ったときに, 空集合となる
    #   => A全体での公約数は 1 
    #   => setwise coprime である

    primeset = set()
    primeintersection = set(range(2, maxA+1))
    for s in primelist:
        primeset.update(s)
        primeintersection.intersection_update(s)
    if len(primeset) == lenprimelist:
        print('pairwise coprime')
        return
    if len(primeintersection) == 0:
        print('setwise coprime')
        return
    print('not coprime')
    return

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd

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

lst = [0]*(max(As)+1)

for a in As:
  i = 2
  if a % i == 0:
    lst[i] += 1
  while a % i == 0:
    a //= i
  i = 3
  while i**2 <= N:
    if a % i == 0:
      lst[i] += 1  
    while a % i == 0:
      a //= i
    i += 2
  if a > 1:
    lst[a] += 1
    
if max(lst) < 2:
  print('pairwise coprime')
  exit()
  
t = As[0]

for a in As:
  t = gcd(t,a)
  
if t == 1:
  print('setwise coprime')
else:
  print('not coprime')

Submission status: Time Limit Exceeded

Solution code:
def gcd(a, b):
    while b: a, b = b, a % b
    return a
def isPrimeMR(n):
    d = n - 1
    d = d // (d & -d)
    L = [2]
    for a in L:
        t = d
        y = pow(a, t, n)
        if y == 1: continue
        while y != n - 1:
            y = (y * y) % n
            if y == 1 or t == n - 1: return 0
            t <<= 1
    return 1
def findFactorRho(n):
    m = 1 << n.bit_length() // 8
    for c in range(1, 99):
        f = lambda x: (x * x + c) % n
        y, r, q, g = 2, 1, 1, 1
        while g == 1:
            x = y
            for i in range(r):
                y = f(y)
            k = 0
            while k < r and g == 1:
                ys = y
                for i in range(min(m, r - k)):
                    y = f(y)
                    q = q * abs(x - y) % n
                g = gcd(q, n)
                k += m
            r <<= 1
        if g == n:
            g = 1
            while g == 1:
                ys = f(ys)
                g = gcd(abs(x - ys), n)
        if g < n:
            if isPrimeMR(g): return g
            elif isPrimeMR(n // g): return n // g
            return findFactorRho(g)
def primeFactor(n):
    i = 2
    ret = {}
    rhoFlg = 0
    while i*i <= n:
        k = 0
        while n % i == 0:
            n //= i
            k += 1
        if k: ret[i] = k
        i += 1 + i % 2
        if i == 101 and n >= 2 ** 20:
            while n > 1:
                if isPrimeMR(n):
                    ret[n], n = 1, 1
                else:
                    rhoFlg = 1
                    j = findFactorRho(n)
                    k = 0
                    while n % j == 0:
                        n //= j
                        k += 1
                    ret[j] = k

    if n > 1: ret[n] = 1
    if rhoFlg: ret = {x: ret[x] for x in sorted(ret)}
    return ret


def gcd(a, b):
    while b: a, b = b, a % b
    return a


N = int(input())
A = list(map(int, input().split()))
# N = 10 ** 6
# A = [10 ** 6] * N
pairwise = False
prime_key = set(primeFactor(A[-1]))
for i in range(N - 2, -1, -1):
    now = set(primeFactor(A[i]))
    if prime_key & now:
        break
    else:
        prime_key = now | prime_key
else:
    pairwise = True
if pairwise:
    print('pairwise coprime')
    exit()
work = gcd(A[0], A[1])
for i in range(2, N):
    work = gcd(work, A[i])
if work != 1:
    print('not coprime')
else:
    print('setwise coprime')

Submission status: Time Limit Exceeded

Solution code:
import math
from functools import reduce

def gcd(num_list):
    return reduce(math.gcd, num_list)

n = int(input())
a = list(map(int, input().split()))
pc = True
cnt = 0

while pc:
    if cnt == n:
        break
    i = a.pop()
    for j in a:
        if math.gcd(i, j) == 1:
            pc = True
        else:
            pc = False
            break
    a.append(i)
    cnt += 1

if pc:
    print("pairwise coprime")
    exit()

if gcd(a) == 1:
    print("setwise coprime")
    exit()

else:
    print("not coprime")

Submission status: Time Limit Exceeded

Solution code:
import sys
from math import sqrt
def SimpleSieve(prime,n):
    arr=[1]*(n+1)
    if len(arr)>0:
        arr[0]=0
    else:
        return
    if len(arr)>1:
        arr[1]=0
    else:
        return
    p=2
    while(p<=n):
        if arr[p]==1:
            prime.append(p)
            for i in range(p**2,n+1,p):
                arr[i]=0
        p+=1
    return

n=int(input())
arr=list(map(int,input().split()))
flag=0
prime=[]
SimpleSieve(prime,(max(arr)//2)+1)
for p in prime:
    val=0
    no=0
    for i in range(n):
        if arr[i]%p==0:
            val+=1
        else:
            no=1
        if val>=2 and flag==0 and no:
            flag=1
            break
        if val==n:
            print("not coprime")
            sys.exit()
if flag:
    print("setwise coprime")
else:
    print("pairwise coprime")

Submission status: Time Limit Exceeded

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7
def divisor(n): #nの約数を全て求める
    i = 1
    table = []
    while i * i <= n:
        if n%i == 0:
            table.append(i)
            table.append(n//i)
        i += 1
    table = list(set(table))
    return table
## 素因数分解
#nを素因数分解したリストを返す
def prime_decomposition(n):
    i = 2
    table = []
    while i * i <= n:
        while n % i == 0:
            n /= i
            table.append(i)
        i += 1
    if n > 1:
        table.append(n)
    return table

N = INT()
A = LIST()
flag = True
A.sort(reverse=True)

memo = defaultdict(int)
s = set()
for a in A:
    d = set(prime_decomposition(a))
    # print(d)
    s = s.union(set(d))
    for y in d:
        if y == 1:
            continue
        elif memo[y] == 0:
            memo[y] += 1
        else:
            # print(d)
            flag = False
# exit()
# print(s)
# exit()
# for a in A:
#     d = divisor(a)
#     set(d)
#     diff = s - set(d)
# for i in range(len(A) - 1):
# A[i]
# cnt = 0
# for a in A:
#     d = divisor(a)
#     # print(d)
#     for y in d:
#         if y == 1:
#             continue
#         if memo[y] == 1:
#             continue
#         else:
#             # print("d:", d)
#             cnt += 1
# if cnt == 0:
#     flag = True
    
if flag == True:
    print("pairwise coprime")
elif reduce(gcd, A) == 1:
        print("setwise coprime")
else:
    print("not coprime")
    

    # A.sort()

Submission status: Time Limit Exceeded

Solution code:
import sys
# sys.setrecursionlimit(100000)
from collections import defaultdict
from functools import lru_cache


@lru_cache(None)
def gcd(x: int, y: int) -> int:
    if x < y:
        x, y = y, x
    while y > 0:
        r = x % y
        x, y = y, r
    return x


def merge_dict(d1, d2):
    for k, v in d2.items():
        d1[k] += v
    return d1


def input():
    return sys.stdin.readline().strip()


def gen_prime_table(last: int, first=2) -> list:
    if last < 1:
        return [False]
    elif last < 2:
        return [False, False]
    primes = []
    table = [True] * (last + 1)
    table[0] = False
    table[1] = False

    for i in range(first, last + 1):
        if table[i]:
            primes.append(i)
            for j in range(i * 2, last + 1, i):
                table[j] = False
    return primes


def prime_factorization(N: int, prime_list: list) -> dict:
    if N < 2:
        return {1: 1}
    primes = dict()
    primes[1] = 1
    i = 2
    for i in prime_list:
        while N % i == 0:
            if i in primes.keys():
                primes[i] += 1
            else:
                primes[i] = 1
            N = N // i
        if N == 1:
            break
    if N != 1:
        primes[N] = 1
    return primes


def main():
    n = int(input())
    A = [int(i) for i in input().split()]
    primes = defaultdict(int)
    is_pair_gcd = True
    set_gcd = A[0]
    prime_list = gen_prime_table(max(A))
    for i in range(n):
        set_gcd = gcd(set_gcd, A[i])
        if is_pair_gcd:
            p = prime_factorization(A[i], prime_list)  # この部分の計算不可が大きい (n*log_log_n)
            for k, v in p.items():
                if k == 1:
                    continue
                if k in primes.keys():
                    is_pair_gcd = False
                else:
                    primes[k] += v

    if is_pair_gcd:
        print("pairwise coprime")
        return

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

    return


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
#dt = {} for i in x: dt[i] = dt.get(i,0)+1
import sys;input = sys.stdin.readline
inp,ip = lambda :int(input()),lambda :[int(w) for w in input().split()]

from fractions import gcd
from math import sqrt
def pfact(num):
    global dt
    if num&1 == 0:
        num >>= 1
        if dt[2]:
            dt[2] = 0
        else:
            return 'setwise coprime'
    while num&1 == 0:
        num >>= 1
    for i in range(3,int(sqrt(num))+1,2):
        if num%i == 0:
            num //= i
            if dt[i]:
                dt[i] = 0
            else:
                return 'setwise coprime'
        while num%i == 0:
            num //= i
    if num>2:
        if dt[num]:
            dt[num] = 0
        else:
            return 'setwise coprime'
    return 'pairwise coprime'

n = inp()
x = ip()
t = x[0]
for i in range(1,n):
    t = gcd(t,x[i])
    if t == 1:
        break
if t != 1:
    ans = 'not coprime'
else:
    ans = 'pairwise coprime'
    dt = {i+1:1 for i in range(10**6)}
    for i in x:
        if pfact(i) == 'setwise coprime':
            ans = 'setwise coprime'
            break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#dt = {} for i in x: dt[i] = dt.get(i,0)+1
import sys;input = sys.stdin.readline
inp,ip = lambda :int(input()),lambda :[int(w) for w in input().split()]

from fractions import gcd
from math import sqrt
def pfact(num):
    global dt
    if num&1 == 0:
        num >>= 1
        if dt[2]:
            dt[2] = 0
        else:
            return 'setwise coprime'
    while num&1 == 0:
        num >>= 1
    for i in range(3,int(sqrt(num))+1,2):
        if num%i == 0:
            num //= i
            if dt[i]:
                dt[i] = 0
            else:
                return 'setwise coprime'
        while num%i == 0:
            num //= i
    if num>2:
        if dt[num]:
            dt[num] = 0
        else:
            return 'setwise coprime'
    return 'pairwise coprime'

n = inp()
x = ip()
x.sort(reverse=True)
t = x[0]
for i in range(1,n):
    t = gcd(t,x[i])
    if t == 1:
        break
if t != 1:
    ans = 'not coprime'
else:
    ans = 'pairwise coprime'
    dt = {i+1:1 for i in range(10**6)}
    for i in x:
        if pfact(i) == 'setwise coprime':
            ans = 'setwise coprime'
            break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
l=list(map(int,input().split()))
f={}
for i in range(n):
    x=l[i]
    for i in range(2,int(x**(0.5))+1):
        if x%i==0:
            f[i]=f.get(i,0)+1
            while x%i==0:
                x=x//i
    if x>1:
        f[x]=f.get(x,0)+1
m=0
for i in f:
    m=max(m,f[i])
if f=={} or m==1:
    print('pairwise coprime')
elif m>1 and m<n:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    import math
    from collections import defaultdict
    n = int(input())
    a = list(set(map(int, input().split())))

    maxa = max(a)
    e = [0]*(maxa+1)
    for i in range(2, maxa+1):
        for j in range(i, maxa+1, i):
            if e[j] == 0:
                e[j] = i

    ggcd = a[0]
    for i in range(1, len(a)):
        ggcd = math.gcd(ggcd, a[i])
        if ggcd == 1:
            break

    pair = False
    divisors = set([])
    for i in range(0, len(a)):
        test = a[i]
        divs = []
        while test > 1:
            divs.append(e[test])
            test //= e[test]
        divs = set(divs)
        if divs & divisors != set():
            pair = True
            break
        else:
            divisors = divs|divisors

    if ggcd != 1:
        print("not coprime")
    else:
        if pair:
            print("setwise coprime")
        else:
            print("pairwise coprime")

resolve()

Submission status: Time Limit Exceeded

Solution code:
import math 
from functools import reduce
N = int(input())
A = list(map(int, input().split()))
ans = ["pairwise coprime", "setwise coprime ", "not coprime"]

def gcd_list(numbers):
    return reduce(math.gcd, numbers)
  
if gcd_list(A) != 1:
  print(ans[2])
  quit()
  
def seachPrimeNum(N):
    max = int(N ** (1 / 2))
    D = [0] * N
    D[0] = 1
    seachList = [i for i in range(2,N+1)]
    primeNum = []
    while seachList[0] <= max:
        nn = seachList[0]
        D[nn - 1] = nn
        primeNum.append(nn)
        tmp = nn
        for i in seachList:
          if i != nn:
            if i % tmp == 0:
              D[i - 1] = nn
        seachList = [i for i in seachList if i % tmp != 0]
    for i in seachList:
      D[i - 1] = i
    primeNum.extend(seachList)
    
    return primeNum, D  
  
primeNum, D = seachPrimeNum(1000000)
used = [0] * len(primeNum)

for i in range(N):
  now = A[i]
  q = []
  #print(now, D[now - 1])
  if (now == D[now - 1]) and (now != 1):
    q.append(now)
  else:
    while now != D[now - 1]:
      now = int(now / D[now - 1])
      if now in primeNum:
        q.append(now)
        
  for i in q:
    if used[primeNum.index(i)] == 0:
      used[primeNum.index(i)] = 1
    else:
      print(ans[1])
      quit()  

print(ans[0])

Submission status: Time Limit Exceeded

Solution code:
def hcfnaive(a,b): 
    if(b==0): 
        return a 
    else: 
        return hcfnaive(b,a%b) 
n=int(input())
l=list(map(int,input().split()))
f={}
for i in range(n):
    x=l[i]
    for i in range(2,int(x**(0.5))+1):
        if x%i==0:
            f[i]=f.get(i,0)+1
            while x%i==0:
                x=x//i
    if x>1:
        f[x]=f.get(x,0)+1
g=l[0]
for i in range(1,n):
    g=hcfnaive(g,l[i])
m=0
for i in f:
    m=max(m,f[i])
if g==1 and (f=={} or m==1):
    print('pairwise coprime')
elif g==1 and m>1:
    print('setwise coprime')
elif g>1:
    print('not coprime')