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:
MAX_A = 10**6 + 1
is_prim = [True] * MAX_A
is_prim[0] = is_prim[1] = False
for i in range(2, MAX_A):
    if not is_prim[i]: continue
    for j in range(i+i, MAX_A, i): is_prim[j] = False

# 素数と個数を求める
def factorize(n):
    res = []
    for i in range(2,n):
        if i*i > n: break
        if n%i: continue
        res += [[i,0]]
        while n%i == 0:
            n //= i
            res[-1][1] += 1
    if n != 1: res += [[n,1]]
    return res

def solve():
    prim = [i for i in range(1100) if is_prim[i]]
    C = [0] * MAX_A
    for a in A:
        for p,c in factorize(a): C[p] += 1
    max_c = max(C)
    if max_c <= 1: return 'pairwise'
    elif max_c <= n-1: return 'setwise'
    return 'not'

n = int(input())
A = [*map(int, input().split())]
print(solve(), 'coprime')

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**6)
INF = 10 ** 9 + 1  # sys.maxsize # float("inf")
MOD = 10 ** 9 + 7


def debug(*x):
    print(*x, file=sys.stderr)


def precompute():
    maxAS = 1000000
    eratree = [0] * (maxAS + 10)
    for p in range(2, maxAS + 1):
        if eratree[p]:
            continue
        # p is prime
        eratree[p] = p
        x = p * p
        while x <= maxAS:
            if not eratree[x]:
                eratree[x] = p
            x += p

    import pickle
    pickle.dump(eratree, open("eratree.pickle", "wb"))


def solve(N, AS):
    import pickle
    eratree = pickle.load(open("eratree.pickle", "rb"))
    num_division = 0

    from collections import defaultdict
    count = defaultdict(int)
    for a in AS:
        factors = []
        while a > 1:
            d = eratree[a]
            factors.append(d)
            a //= d
            num_division += 1
        # debug(": ", factors)
        for f in set(factors):
            count[f] += 1

    # debug(": num_division", num_division)
    if any(x == N for x in count.values()):
        return "not coprime"
    if any(x >= 2 for x in count.values()):
        return "setwise coprime"
    return "pairwise coprime"


def main():
    # parse input
    N = int(input())
    AS = list(map(int, input().split()))
    print(solve(N, AS))


# tests
T1 = """
3
3 4 5
"""
TEST_T1 = """
>>> as_input(T1)
>>> main()
pairwise coprime
"""

T2 = """
3
6 10 15
"""
TEST_T2 = """
>>> as_input(T2)
>>> main()
setwise coprime
"""

T3 = """
3
6 10 16
"""
TEST_T3 = """
>>> as_input(T3)
>>> main()
not coprime
"""

T4 = """
3
100000 100001 100003
"""
TEST_T4 = """
>>> as_input(T4)
>>> main()
pairwise coprime
"""


def _test():
    import doctest
    doctest.testmod()
    g = globals()
    for k in sorted(g):
        if k.startswith("TEST_"):
            doctest.run_docstring_examples(g[k], g, name=k)


def as_input(s):
    "use in test, use given string as input file"
    import io
    f = io.StringIO(s.strip())
    g = globals()
    g["input"] = lambda: bytes(f.readline(), "ascii")
    g["read"] = lambda: bytes(f.read(), "ascii")


input = sys.stdin.buffer.readline
read = sys.stdin.buffer.read

if sys.argv[-1] == "-t":
    print("testing")
    _test()
    sys.exit()

if sys.argv[-1] == 'ONLINE_JUDGE':
    precompute()
else:
    main()

Submission status: Time Limit Exceeded

Solution code:
import math

def calc_spf(n):
    num = list(range(2,n+1))
    spf = [0]*n
    
    while len(num)>0:
        p = num.pop(0)
        delta = p
        spf[p-1]=p
        p *= delta
        while p<=n:
            if p in num and spf[p-1]==0:
                spf[p-1]=delta
                num.remove(p)
            p += delta
    return spf

def get_prime(n,spf):
    if n==1:
        return {1}
    ans = []
    while n > 1:
        tmp = spf[n-1]
        ans.append(tmp)
        n //= tmp
    return set(ans)

n = int(input().rstrip())
a = list(map(int,input().rstrip().split()))
b = a[:]
pgcd = True
sgcd = a[n-1]
spf = calc_spf(max(a))
b[n-1] = get_prime(a[n-1],spf)
tmp = b[n-1]
for i in range(0,n-1):
    sgcd = math.gcd(sgcd, a[i])
    b[i] = get_prime(a[i],spf)
    if pgcd and len(tmp&b[i]) >0 and tmp&b[i] !={1}:
        pgcd = False
    tmp = tmp | b[i]
if sgcd!=1:
    print('not coprime')
elif pgcd:
    print('pairwise coprime')
else:
    print('setwise coprime')

Submission status: Time Limit Exceeded

Solution code:
import sys
from math import gcd
def input(): return sys.stdin.readline().strip()


def get_sieve_of_eratosthenes(n):
    """
    エラトステネスの篩。√N以下の数に対して2から順にその数の倍数を消していく。
    計算量は「調和級数」になるのがミソ。具体的には
        N/2 + N/3 + N/5 + ... + N/(√N) = N * (1/2 + 1/3 + 1/5 + ... + 1/√N)
                                       = N * loglog(√N) (素数の逆数和の発散スピードがこれ)
                                       = N(loglogN - log2)
    """
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 2:
        return [0] * (n + 1)
    prime = [1] * (n + 1)
    prime[0] = prime[1] = 0
    for i in range(2, int(n**0.5) + 1):
        if not prime[i]: continue
        for j in range(i * 2, n + 1, i):
            prime[j] = 0
    return prime


def main():
    N = int(input())
    A = list(map(int, input().split()))
    all_gcd = A[0]
    for a in A:
        all_gcd = gcd(all_gcd, a)
    if all_gcd != 1:
        print("not coprime")
        return

    prod = A[0]
    for i, a in enumerate(A):
        if i == 0: continue
        if gcd(prod, a) != 1:
            print("setwise coprime")
            return
        prod *= a
    print("pairwise coprime")




if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
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:0 for i in range(n + 1) if is_prime[i]}

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

for i in range(n):
    for k in d.keys():
        flag = False
        while True:
            if a[i] % k == 0:
                a[i] //= k
                flag = True
            else:
                break
        if flag:
            d[k] += 1
        if a[i] == 1:
            break
flag = True
for v in d.values():
    if v == n:
        print("not coprime")
        exit()
    elif v > 1:
        flag = False

if flag:
    print("pairwise coprime")
else:
    print("setwise coprime")

Submission status: Time Limit Exceeded

Solution code:
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:0 for i in range(n + 1) if is_prime[i]}

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

for i in a:
    for k , v in d.items():
        if i % k == 0:
            d[k] += 1
flag = True  
for v in d.values():
    if v == n:
        print("not coprime")
        exit()
    elif v > 1:
        flag = False
if flag:
    print("pairwise coprime")
else:
    print("setwise coprime")

Submission status: Time Limit Exceeded

Solution code:
import os
import sys
from sys import *
from io import BytesIO, IOBase

BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self,file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd,max(os.fstat(self._fd).st_size,BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0,2),self.buffer.write(b),self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd,max(os.fstat(self._fd).st_size,BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0,2), self.buffer.write(b) , self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd,self.buffer.getvalue())
            self.buffer.truncate(0),self.buffer.seek(0)

class IOWrapper(IOBase):
    def __init__(self,file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda: self.buffer.read().decode('ascii')
        self.readline = lambda: self.buffer.readline().decode('ascii')

sys.stdin,sys.stdout = IOWrapper(sys.stdin),IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip('\r\n')



from math import *
from collections import *
from itertools import *
from functools import *
from bisect import *
from heapq import *
from operator import *
from sys import *
setrecursionlimit(100000000)


def pf(n):
    # primfac = []
    d = 2
    while d*d <= n:
        if (n % d) == 0:
            yield d
        while (n % d) == 0:
            n //= d
        d += 1
    if n > 1:
       yield n

MAX=(2*(10**6))
MIN=float('-inf')
MOD=1000000007
n = int(input())
a = list(map(int,input().split()))

cnt = [0]*MAX
loop_end = False
g = 0
pairwise_coprime = True
setwise_coprime = True
    

for ai in a:
  for p in pf(ai):
    if cnt[p]:
      pairwise_coprime = False
      loop_end = True  
    cnt[p] = 1
    if loop_end:
      break
  if loop_end:
    break

for ai in a:
  g = gcd(g,ai)
setwise_coprime = g==1

if pairwise_coprime:
  print('pairwise coprime')
elif setwise_coprime:
  print('setwise coprime')
else:
  print('not coprime')

Submission status: Time Limit Exceeded

Solution code:
from math import *
from collections import *
from itertools import *
from functools import *
from bisect import *
from heapq import *
from operator import *
from sys import *
setrecursionlimit(100000000)


def pf(n):
    # primfac = []
    d = 2
    while d*d <= n:
        if (n % d) == 0:
            yield d
        while (n % d) == 0:
            n //= d
        d += 1
    if n > 1:
       yield n

MAX=(2*(10**6))
MIN=float('-inf')
MOD=1000000007
n = int(input())
a = list(map(int,input().split()))

cnt = [0]*MAX
loop_end = False
g = 0
pairwise_coprime = True
setwise_coprime = True
    

for ai in a:
  for p in pf(ai):
    if cnt[p]:
      pairwise_coprime = False
      loop_end = True  
    cnt[p] = 1
    if loop_end:
      break
  if loop_end:
    break

for ai in a:
  g = gcd(g,ai)
setwise_coprime = g==1

if pairwise_coprime:
  print('pairwise coprime')
elif setwise_coprime:
  print('setwise coprime')
else:
  print('not coprime')

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
import math
from functools import reduce
from itertools import combinations
 
def gcd(*numbers):
    return reduce(math.gcd, numbers)

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

a = 1
b = 0
break_loop = False
n = int(stdin.readline().rstrip())
listA=list(map(int,input().split()))
for i in range(0, len(listA)):
  for k in range(i+1, len(listA)):
    if math.gcd(listA[i], listA[k]) != 1:
      a = 0
      break_loop = True
      break
    else:
      continue
  if break_loop == True:
    break
  else:
    continue
if gcd(*listA) == 1:
  b = 1
if a == 1:
  print("pairwise coprime")
elif b == 1:
  print("setwise coprime")
else:
  print("not coprime")

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict,Counter
input = sys.stdin.readline

N = int(input())
As = list(map(int,input().split()))
divisors = defaultdict(int)
def make_divisors(n):
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors[i]+=1
            if i != n // i:
                divisors[n//i]+=1

dvs = []
for i in As:
  make_divisors(i)

res=0
for k,v in divisors.items():
  if k != 1 and v == N:
    res = 2
    break
  elif k != 1 and v > 1:
    res = 1

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

Submission status: Time Limit Exceeded

Solution code:
import math
def div(s):
    i=1
    while(i<=math.sqrt(s)):
        if(s%i==0):
            if(s//i==i):
                if(i!=1):
                    if(i in d):
                        return False
                    else:
                        d[i]=1
            else:
                if(i!=1):
                    if(i in d):
                        return False
                    else:
                        d[i]=1
                if(s//i!=1):
                    if(s//i in d):
                        return False
                    else:
                        d[s//i]=1
        i+=1
    #print(d,s)
    return True
                

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

d=dict()

setwise=False
pairWise=True
pairWise&=div(l[0])
pairWise&=div(l[1])
val=math.gcd(l[0],l[1])

for i in range(2,n):
    pairWise&=div(l[i])
    val=math.gcd(val,l[i])
if(pairWise):
    print('pairwise coprime')
elif(val==1):
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Time Limit Exceeded

Solution code:
import math
def div(s):
    i=1
    while(i<=math.sqrt(s)):
        if(s%i==0):
            if(s//i==i):
                if(i!=1):
                    if(i in d):
                        return False
                    else:
                        d[i]=1
            else:
                if(i!=1):
                    if(i in d):
                        return False
                    else:
                        d[i]=1
                if(s//i!=1):
                    if(s//i in d):
                        return False
                    else:
                        d[s//i]=1
        i+=1
    #print(d,s)
    return True
                

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

d=dict()

setwise=False
pairWise=True

for i in range(n):
    pairWise&=div(l[i])
val=math.gcd(l[0],l[1])
for i in range(2,n):
    val=math.gcd(val,l[i])
if(pairWise):
    print('pairwise coprime')
elif(val==1):
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Time Limit Exceeded

Solution code:
import math

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

a=max(A)
def era(n):
  prime=[]
  furui=list(range(2,n+1))
  while furui[0]<math.sqrt(n):
    prime.append(furui[0])
    furui=[i for i in furui if i%furui[0]!=0]
  return prime+furui

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

if b!=1:
  print("not coprime")
  exit()

furui=era(10**6+7)
dummy=[False]*(10**6+7)
for i in range(N):
  k=A[i]
  while k!=1:
    for j in furui:
      if k%j==0 and dummy[j-1]==True:
        print("setwise coprime")
        exit()
      elif k%j==0 and dummy[j-1]==False:
        dummy[j-1]=True
      while k%j==0:
        k//=j
print("pairwise coprime")

Submission status: Time Limit Exceeded

Solution code:
import math
n=int(input())
a=list(map(int,input().split()))
g=a[0]
for m in a:
  g=math.gcd(g,m)
  if g==1:break
else:
  print("not coprime")
  exit()

j=2
l=[0]*2+[1]*(10**6-1)
while j<10*6+1:
  k=1
  if l[j]==1:
    while k*j<10**6:
      l[k*j]==0
      k+=1
  j+=1
d=[]
for i in range(len(l)):
  if l[i]==1: d.append(i)
              
e=set()
for i in range(n):
  z=a[i]
  for m in d:
    if z%m==0:
      if m in e:
        print("setwise coprime")
        exit()
      e.add(m)
print("pairwise coprime")

Submission status: Time Limit Exceeded

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


def facs(n):
    """試し割り法における割る数を生成する。"""
    yield 2
    for x in range(3, n, 2):
        yield x


def main():
    input()  # N
    array = [int(x) for x in input().split()]
    MAX_A = 10 ** 6 + 1
    histogram = defaultdict(int)
    for x in array:
        histogram[x] += 1

    for potential_prime in facs(MAX_A):
        count = sum(
            histogram[divider]
            for divider in range(potential_prime, MAX_A, potential_prime))
        if count > 1:
            break
    else:
        return 'pairwise coprime'

    gcd_total = reduce(gcd, array)
    if gcd_total == 1:
        return 'setwise coprime'
    else:
        return 'not coprime'


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

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce
import fractions
import sys
sys.setrecursionlimit(10**9)

class Osak:
    def __init__(self,maxim): #O(Nlog(log N))
        spf = [0] * (maxim+1)
        for i in range(maxim):
            spf[i] = i
        
        i = 2
        while i*i <= maxim:
            if spf[i] != i: i += 1; continue
            j = i*i
            while j <= maxim:
                if spf[j] != j: j += i; continue
                spf[j] = i
                j += i
            
            i += 1

        self.spf = spf

    def get(self,n): # O(log n)
        m  = set()
        while n > 1:
            m.add(self.spf[n])
            n //= self.spf[n]

        return m



def get_gcm(X):
    return reduce(lambda x,y: fractions.gcd(x, y), X[1:], X[0])


INF=10**20
def solve(N: int, A: "List[int]"):
    osak = Osak(10**6+10)

    pairwise = True
    allP = set()
    for a in A:
        P = osak.get(a)
        no_collapse = len(allP) + len(P)
        for p in P:
            allP.add(p)
        
        res = len(allP)
        if no_collapse != res:
            pairwise = False
            break




    if pairwise:
        print("pairwise coprime")
    else:
        gcm = get_gcm(A)
        if gcm == 1:
            print("setwise coprime")
        else:
            print("not coprime")

    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)



if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N=int(input())
A=list(map(int,input().split()))
# cnt=[0]*(10**6+1)
cnt=np.zeros(10**6+1, dtype=np.int32)
for a in A:cnt[a]+=1
 
if np.gcd.reduce(A)!=1:
  print("not coprime")
elif np.all([sum(cnt[i::i])<=1 for i in range(2,10**6+1)]):
  print("pairwise coprime")
else:
  print("setwise coprime")

Submission status: Time Limit Exceeded

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

# O(A+NloglogN)解
MAX_A = 1000000
lowerst_prime = [10**9] * (MAX_A + 1) # 最小の素因数をいれる(2以上をみていけばいい)
count = [0] * (MAX_A + 1) # 約数として出てくる回数を数える

for i in range(2, MAX_A + 1): # エラトステネスの篩
    if lowerst_prime[i] != 10**9:
        continue
    lowerst_prime[i] = i
    for j in range(i * i, MAX_A + 1, i): # i * iスタートでいいのは、i * bはbの約数でもあるため
        if lowerst_prime[j] == 10**9:
            lowerst_prime[j] = i
# 入力
N = int(input())
A = [*map(int, input().split())]

if reduce(gcd, A) != 1:
    print("not coprime")
    exit(0)

for i in range(N):
    while A[i] > 1:
        divide = lowerst_prime[A[i]]
        count[divide] += 1
        while A[i] % divide == 0: # 割れるだけ割る
            A[i] //= divide

for i in range(MAX_A + 1):
    if count[i] >= 2:
        print("setwise coprime")
        exit(0)
print("pairwise coprime")

Submission status: Time Limit Exceeded

Solution code:
from math import gcd
import numpy as np

def setwise_coprime_check_fun(A_list, N):
    gcd_all = A_list[0]
    for i in range(N - 1):
        gcd_all = gcd(gcd_all, A_list[i + 1])
        if gcd_all == 1:
            break
    return gcd_all

def preprocess_fun(A_max):
    p_flg = [True] * (A_max + 1)
    D = [0] * (A_max + 1)
    p_flg[0] = False
    p_flg[1] = False
    for i in range(2, A_max + 1, 1):
        if p_flg[i]:
            for j in range(i, A_max + 1, i):
                p_flg[j] = False
                D[j] = i
    return D

def pairwise_coprime_check(A_list, D):
    p_count = [0] * (max(A_list) + 1)
    p_count_temp = [0] * (max(A_list) + 1)
    for A in A_list:
        temp = A
        while temp != 1:
            if p_count[D[temp]] == 1:
                return 0
            else:
                p_count_temp[D[temp]] = 1
            temp = temp // D[temp]
        p_count = list(np.array(p_count) + np.array(p_count_temp))
        p_count_temp = [0] * (max(A_list) + 1)
    return 1

# 標準入力
N = int(input())
A_list = list(map(int, input().split(" ")))

# 整数の最大値を取得
A_max = max(A_list)

# 本体
if(setwise_coprime_check_fun(A_list, N) != 1):
    print("not coprime")
else:
    D = preprocess_fun(A_max)
    if pairwise_coprime_check(A_list, D) == 1:
        print("pairwise coprime")
    else:
        print("setwise coprime")

Submission status: Time Limit Exceeded

Solution code:
def gcd(a, b):
    return gcd(b, a%b) if a%b else b

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

numlist = [0] * (max(a) + 5)
g = 0
for i in range(n):
    numlist[a[i]] += 1
    g = gcd(g, a[i])

pairwise = True
for i in range(2, 1000005):
    ctr = 0
    for j in range(i, max(a), i):
        ctr += numlist[j]
    if ctr > 1:
        pairwise = False

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

Submission status: Time Limit Exceeded

Solution code:
# Python template 
from collections import defaultdict 
import sys
import math 

def get_array(): return list(map(int , sys.stdin.readline().strip().split()))
def get_ints(): return map(int, sys.stdin.readline().strip().split())
def input(): return sys.stdin.readline().strip()

sys.setrecursionlimit(10**6) 

# Python3 program to find the number of pairs 
# such that gcd equals to 1 
N = 1000005

lpf = [0 for i in range(N)] 
mobius = [0 for i in range(N)] 

# Function to calculate least 
# prime factor of each number 
def least_prime_factor(): 

	for i in range(2, N): 

		# If it is a prime number 
		if (lpf[i] == 0): 

			for j in range(i, N, i): 

				# For all multiples which are not 
				# visited yet. 
				if (lpf[j] == 0): 
					lpf[j] = i 

# Function to find the value of Mobius function 
# for all the numbers from 1 to n 
def Mobius(): 

	for i in range(1, N): 

		# If number is one 
		if (i == 1): 
			mobius[i] = 1
		else: 

			# If number has a squared prime factor 
			if (lpf[ (i // lpf[i]) ] == lpf[i]): 
				mobius[i] = 0

			# Multiply -1 with the previous number 
			else: 
				mobius[i] = -1 * mobius[i // lpf[i]] 

# Function to find the number of pairs 
# such that gcd equals to 1 
def gcd_pairs(a, n): 

	# To store maximum number 
	maxi = 0

	# To store frequency of each number 
	fre = [0 for i in range(N)] 

	# Find frequency and maximum number 
	for i in range(n): 
		fre[a[i]] += 1
		maxi = max(a[i], maxi) 

	least_prime_factor() 
	Mobius() 

	# To store number of pairs with gcd equals to 1 
	ans = 0

	# Traverse through the all possible elements 
	for i in range(1, maxi + 1): 
		if (mobius[i] == 0): 
			continue

		temp = 0
		for j in range(i, maxi + 1, i): 
			temp += fre[j] 

		ans += temp * (temp - 1) // 2 * mobius[i] 

	# Return the number of pairs 
	return ans 

# Driver code 

n = int(input())

a = get_array() 
if gcd_pairs(a,n) == (n*(n-1))//2:
    print("pairwise coprime")
else:
    gs = a[0]
    for i in range(1,n):
        gs = math.gcd(gs,a[i])
    if gs == 1:
        print("setwise coprime")
    else:
        print("not coprime")

Submission status: Time Limit Exceeded

Solution code:
from math import gcd
import numpy as np

def setwise_coprime_check_fun(A_list):
    gcd_all = A_list[0]
    for i in range(N - 1):
        gcd_all = gcd(gcd_all, A_list[i + 1])
        if gcd_all == 1:
            break
    return gcd_all

def preprocess_fun(A_max):
    p_flg = [True] * (A_max + 1)
    D = [0] * (A_max + 1)
    p_flg[0] = 0
    p_flg[1] = 0
    for i in range(2, A_max + 1, 1):
        if p_flg[i]:
            for j in range(i, A_max + 1, i):
                p_flg[j] = False
                D[j] = i
    return D

def pairwise_coprime_check(A_list, D):
    p_count = [0] * (max(A_list) + 1)
    p_count_temp = [0] * (max(A_list) + 1)
    for A in A_list:
        temp = A
        while temp != 1:
            if p_count[D[temp]] == 1:
                return 0
            else:
                p_count_temp[D[temp]] = 1
            temp = temp // D[temp]
        p_count = list(np.array(p_count) + np.array(p_count_temp))
        p_count_temp = [0] * (max(A_list) + 1)
    return 1

# 標準入力
N = int(input())
A_list = list(map(int, input().split(" ")))

# 整数の最大値を取得
A_max = max(A_list)

# 本体
if(setwise_coprime_check_fun(A_list) != 1):
    print("not coprime")
else:
    D = preprocess_fun(A_max)
    if pairwise_coprime_check(A_list, D) == 1:
        print("pairwise coprime")
    else:
        print("setwise coprime")

Submission status: Time Limit Exceeded

Solution code:
from math import gcd
import numpy as np

def setwise_coprime_check_fun(A_list):
    gcd_all = A_list[0]
    for i in range(N - 1):
        gcd_all = gcd(gcd_all, A_list[i + 1])
        if gcd_all == 1:
            break
    return gcd_all

def preprocess_fun(A_max):
    p_flg = [1] * (A_max + 1)
    D = [0] * (A_max + 1)
    p_flg[0] = 0
    p_flg[1] = 0
    for i in range(2, A_max + 1, 1):
        if p_flg[i]:
            for j in range(i, A_max + 1, i):
                p_flg[j] = 0
                D[j] = i
    return D

def pairwise_coprime_check(A_list, D):
    p_count = [0] * (max(A_list) + 1)
    p_count_temp = [0] * (max(A_list) + 1)
    for A in A_list:
        temp = A
        while temp != 1:
            if p_count[D[temp]] == 1:
                return 0
            else:
                p_count_temp[D[temp]] = 1
            temp = temp // D[temp]
        p_count = list(np.array(p_count) + np.array(p_count_temp))
        p_count_temp = [0] * (max(A_list) + 1)
    return 1

# 標準入力
N = int(input())
A_list = list(map(int, input().split(" ")))

# 整数の最大値を取得
A_max = max(A_list)

# 本体
if(setwise_coprime_check_fun(A_list) != 1):
    print("not coprime")
else:
    D = preprocess_fun(A_max)
    if pairwise_coprime_check(A_list, D) == 1:
        print("pairwise coprime")
    else:
        print("setwise coprime")

Submission status: Time Limit Exceeded

Solution code:
from math import sqrt
from math import gcd

def fact(n):
    P = set()
    for i in range(2,int(sqrt(n))+1):
        if n % i == 0:
            P.add(i)
            while n % i != 0:
                n //= i
    if n != 1:
        P.add(n)
    return P

def GCD(A,N):
    g = A[0]
    for i in range(N):
        g = gcd(g,A[i])
        if g == 1:
            return 1
    return g

def solve(A,N):
    ans = ["pairwise coprime","setwise coprime","not coprime"]
    ans_id = 0
    max_A = max(A)
    T = [0 for _ in range(max_A+1)]
    pc_flag = True
    for i in range(N):
        for j in range(1,A[i]):
            if A[i] % j == 0:
                T[A[i]//j] += 1

    for i in range(len(T)):
        if T[i] >= 2:
            pc_flag = False
            ans_id += 1
            break

    if pc_flag:
        return ans[ans_id]
    else:
        if GCD(A,N) == 1:
            return ans[ans_id]
        else:
            ans_id += 1
            return ans[ans_id]

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

    print(solve(A,N))

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from math import gcd
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().rstrip().split()
def S(): return sys.stdin.readline().rstrip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]

mod=10**9+7




pair_flg=1
n=I()
A=LI()
t_set=set()
D=defaultdict(set)
ret=A[0]

for j in range(n):
    a=A[j]
    ret = gcd(ret,a)
    prime_set = D[A[j]]
    flg=0
    if not prime_set:
        for i in range(2, int(a ** 0.5) + 1):
            while a % i == 0:
                a //= i
                prime_set.add(i)
                if D[a]:
                    prime_set|=D[a]
                    flg=1
                    break
            if a == 1 or flg:
                break
        if a != 1:
            prime_set.add(a)
        D[A[j]]=prime_set
    if prime_set&t_set:
        pair_flg=0
    t_set|=prime_set


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

Submission status: Time Limit Exceeded

Solution code:
from math import gcd
import numpy as np

def setwise_coprime_check_fun(A_list):
    gcd_all = A_list[0]
    for i in range(N - 1):
        gcd_all = gcd(gcd_all, A_list[i + 1])
    return gcd_all

def preprocess_fun(A_max):
    p_flg = [1] * (A_max + 1)
    D = [0] * (A_max + 1)
    p_flg[0] = 0
    p_flg[1] = 0
    for i in range(2, A_max + 1, 1):
        if p_flg[i]:
            for j in range(i, A_max + 1, i):
                p_flg[j] = 0
                D[j] = i
    return D

def pairwise_coprime_check(A_list, D):
    p_count = [0] * (max(A_list) + 1)
    p_count_temp = [0] * (max(A_list) + 1)
    for A in A_list:
        temp = A
        while temp != 1:
            if p_count[D[temp]] == 1:
                return 0
            else:
                p_count_temp[D[temp]] = 1
            temp = temp // D[temp]
        p_count = list(np.array(p_count) + np.array(p_count_temp))
        p_count_temp = [0] * (max(A_list) + 1)
    return 1

# 標準入力
N = int(input())
A_list = list(map(int, input().split(" ")))

# 整数の最大値を取得
A_max = max(A_list)

# 本体
if(setwise_coprime_check_fun(A_list) != 1):
    print("not coprime")
else:
    D = preprocess_fun(A_max)
    if pairwise_coprime_check(A_list, D) == 1:
        print("pairwise coprime")
    else:
        print("setwise coprime")