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 math
import fractions
import functools

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

def lcm(a, b):
    return a * b // fractions.gcd(a, b)

if functools.reduce(lcm, A) == functools.reduce(int.__mul__, A):
    print('pairwise coprime')
elif functools.reduce(fractions.gcd, A) == 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()))
flag1=True
flag2=True
for i in range(N-1):
    for j in range(i+1,N):
        if np.gcd(A[i],A[j])!=1:
            flag1=False
            break
    else:
        continue
    break
if np.gcd.reduce(A)!=1:
    flag2=False
if flag1:
    print('pairwise coprime')
elif flag2:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
from collections import deque
from collections import defaultdict

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid(h, w, num): return [[int(num)] * w for _ in range(h)]


# Nの素因数分解を辞書で返す
def prime_fact(n, ela):
    if n == 1:
        return {1: 1}

    prime_dict = {}
    for i in ela:
        cnt = 0
        while n % i == 0:
            cnt += 1
            n = n // i
        if cnt:
            prime_dict[i] = cnt
        if n == 1:
            break
    if n != 1:
        prime_dict[n] = 1
    return prime_dict


def prime_eratosthenes(n):
   prime_list = []
   num_list=[]
   for i in range(2, n+1):
       if i not in num_list:
           prime_list.append(i)
           for j in range(i*i, n+1, i):
               num_list.append(j)
   return prime_list


def main():
    N = NI()
    A = NLI()
    ela = prime_eratosthenes(1000)
    if max(A) == 1:
        print("pairwise coprime")
        exit()

    p_cnt = defaultdict(int)
    PD_list = defaultdict(dict)
    for a in A:
        if a == 1:
            continue

        if PD_list[a]:
            AP = PD_list[a]
        else:
            AP = prime_fact(a, ela)
        PD_list[a] = AP
        for apk in AP.keys():
            p_cnt[apk] += 1

    max_p = max(p_cnt.values())
    if max_p == 1:
        print("pairwise coprime")
    elif max_p == N:
        print("not coprime")
    else:
        print("setwise coprime")



if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import math 
import sys
from functools import reduce

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

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

if gcd_list(A) > 1:
  print("not coprime")
  sys.exit()
  
union = set()
intersection = set()

visited = set()
A_set = set()

flag = False
MAX = 10**6
for a in A:
  #print(visited, a)
  if a in visited: 
    print("setwise coprime")
    sys.exit()
    flag = True 
    break
  b = a
  p = 2
  while p <= MAX:
    if b % p == 0:
      q = p
      for q in range(p,MAX+1,p): #pの倍数を全てvisitedへ
        visited.add(q)     
    while b % p == 0:
      b = b // p
    p += 1

print("pairwise coprime")

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
from math import gcd
l = 1
g = 0
B = True
for a in map(int, input().split()):
  if B:
    i = gcd(l, a)
    if i != 1:
      B = False
    else:
      l = l * a // i
  g = gcd(g, a)
if B:
  print('pairwise coprime')
elif g == 1:
  print('setwise coprime')
else:
  print('not coprime')

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.buffer.readline
    from math import gcd
    N = int(input())
    A = list(map(int, input().split()))
    A.sort()
    S = 1
    for x in A:
        S *= x
    flag = True
    for x in A:
        if gcd(S//x, x) == 1:
            continue
        else:
            flag = False
            break
    if flag:
        print("pairwise coprime")
    else:
        g = A[0]
        for i in range(1, N):
            g = gcd(A[i], g)
        if g == 1:
            print("setwise coprime")

        else:
            print("not coprime")


main()

Submission status: Time Limit Exceeded

Solution code:


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

def lcm(a, b):
    return abs((a // gcd(a, b)) * b)

from functools import reduce

n=int(input())
ar=[int(i) for i in input().strip().split(" ")]
l=ar[0]
t=1
for i in range(1,n):
    if gcd(l,ar[i])!=1:
        t=-1
        break
    else:
        l=lcm(l,ar[i])
if t==1:
    print("pairwise coprime")
else:
    k=reduce(gcd,ar)
    if k==1:
        print("setwise coprime")
    else:
        print("not coprime")

Submission status: Time Limit Exceeded

Solution code:


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

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

d = {}
flag = False
for i in a:
    data = list(set(prime_factorize(i)))
    for k in data:
        try:
            if d[k] >= 1:
                d[k] += 1
                flag = True
        except:
            d[k] = 1
if not flag:
    print("pairwise coprime")
else:
    flag = False
    for i in d.values():
        if i == len(a):
            print("not coprime")
            flag = True
            break
    if not flag:
        print("setwise coprime")

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
def generate_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]]

def main():  
    n = int(input())
    A = list(map(int, input().split()))
    d = defaultdict(int)
    primes = generate_primes(max(A))
    for a in A:
        for p in primes:
            if a < p: break
            if a % p == 0:
                d[p] += 1
    d[1] = 0
    m = max(d.values())
    if m == n:
        print('not coprime')
    elif m >= 2:
        print('setwise coprime')
    else:
        print('pairwise coprime')
    

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
from heapq import heapify, heappop, heappush
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

N = getN()
A = getList()

pair = True
semi = True
# not divisible
# 全部互いに素かどうか
judge = [0] * (10 ** 6 + 1)
num_list = [0] * (10 ** 6 + 1)

now = A[0]
for i in A[1:]:
    now = gcd(now, i)
if now > 1:
    semi = False

for i in A:
    judge[i] += 1

for i in range(2, 10 ** 6 + 1):
    if num_list[i] == 1:
        continue
    cnt = 0
    for j in range(i, 10 ** 6 + 1, i):
        num_list[j] = 1
        cnt += judge[j]
    if cnt > 1:
        pair = False
        break

if pair and semi:
    print('pairwise coprime')
elif semi:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Time Limit Exceeded

Solution code:
import math

n = int(input().rstrip())
a = list(map(int,input().rstrip().split()))
pgcd = True
sgcd = a[n-1]

for i in range(0,n-1):
    sgcd = math.gcd(sgcd, a[i])
if sgcd!=1:
    print('not coprime')
else:
    for i in range(0,n-1):
        sgcd = math.gcd(sgcd, a[i])    
        for j in range(i+1,n):
            if math.gcd(a[i], a[j]) != 1:
                print('setwise coprime')
                break
        else:
            continue
        break
    else:
        print('pairwise coprime')

Submission status: Time Limit Exceeded

Solution code:
import sys
mod=10**9+7 ; inf=float("inf")
from math import sqrt, ceil
from collections import deque, Counter, defaultdict #すべてのkeyが用意されてる defaultdict(int)で初期化
input=lambda: sys.stdin.readline().strip()
sys.setrecursionlimit(11451419)
from decimal import ROUND_HALF_UP,Decimal  #変換後の末尾桁を0や0.01で指定
  #Decimal((str(0.5)).quantize(Decimal('0'), rounding=ROUND_HALF_UP))
from functools import lru_cache
from bisect import bisect_left as bileft, bisect_right as biright
#メモ化再帰defの冒頭に毎回 @lru_cache(maxsize=10**10)
#引数にlistはだめ
#######ここまでテンプレ#######
#ソート、"a"+"b"、再帰ならPython3の方がいい
#######ここから天ぷら########

n=int(input())

A=list(map(int,input().split()))
from math import sqrt
def eratosu(n):
  if not isinstance(n,int):
    raise TypeError("nがint型になってねえぞ")
  if n<2:
    raise ValueError('nが2よりちっちぇえぞ')
  prime = []
  limit = sqrt(n)
  data = [i+1 for i in range(1, n)]  #2,3,4,...,n
  while True:
    p = data[0]
    if limit <= p:
        return prime + data
    prime.append(p)
    data = [e  for e in data if e % p != 0]
PRIME=eratosu(10**6)
@lru_cache(maxsize=10**10)
def bunkai(n):
    if n==1:return []
    ans=[]
    temp=n
    #そんな早くしなくてよかったり、何回もするわけじゃないなら、
    #for i in range(2,int(sqrt(n))+1): とかで
    primelist= PRIME
    for i in primelist:
        if i>sqrt(n):break
        if temp % i ==0:
            ji=0
            while temp%i==0:
                ji+=1
                temp//=i
            ans.append([i,ji])
    if ans==[]:return([[n,1]])  #素数のとき
    if temp!=1:
        ans.append([temp,1])  #4*5882353とか
    return ans

flag=1
seen=[0]*(10**6)
#print(bunkai(3))
for i in A:
    for l in bunkai(i):
        now=l[0] 
        if seen[now]!=0:
            flag=0
        seen[now]+=1
if flag:
    print("pairwise coprime")
elif max(seen)!=n:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1 << 25)
readline = sys.stdin.buffer.readline
read = sys.stdin.readline  # 文字列読み込む時はこっち
ra = range
enu = enumerate


def exit(*argv, **kwarg):
    print(*argv, **kwarg)
    sys.exit()


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))
# 受け渡されたすべての要素からsubだけ引く.リストを*をつけて展開しておくこと


def a_int(): return int(readline())


def ints(): return list(map(int, readline().split()))


def read_col(H):
    '''H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) #一列の場合'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, readline().split())))
    return tuple(map(list, zip(*ret)))


def read_tuple(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, readline().split())))
    return ret


def read_matrix(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, readline().split())))
    return ret
    # return [list(map(int, read().split())) for _ in range(H)] # 内包表記はpypyでは遅いため


def factorization(n: int):
    if n == 1:
        return []  # 1は素数ではない
    # 素因数分解
    arr = []
    temp = n
    for i in range(2, int(n**0.5) + 1):  # ここにバグがないか心配
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append((i, cnt))
            if temp == 1:
                break

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

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

    return arr


def can_factorization(n: int):
    if n == 1:
        return []  # 1は素数ではない
    # 素因数分解
    arr = []
    temp = n
    for i in range(2, int(n**0.5) + 1):  # ここにバグがないか心配
        if temp % i == 0:
            arr.append(i)

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

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

    return arr


MOD = 10**9 + 7
INF = 2**31  # 2147483648 > 10**9
# default import
from collections import defaultdict, Counter, deque
from operator import itemgetter, xor, add
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  # , insort_left, insort_right
from functools import reduce
from math import gcd


N = a_int()
A = ints()

# setかはすぐわかる
# setでなければ not coprime
# pairは互いに素かをみればいいのか
# つまり因数分解して足してったときにすべての素数のべき数が1以下であれば良い

g_set = 0
cnt = defaultdict(lambda: 0)
flg = 1  # pairwiseであるフラグ
# if N > 3 * (10**5):
#     flg = 0
#     for a in A:
#         g_set = gcd(g_set, a)
# else:
for a in A:
    g_set = gcd(g_set, a)
    for p, n in factorization(a):
        if cnt[p] != 0:
            flg = 0
        cnt[p] += n


# print(cnt)
# for v in cnt.values():
#     if v > 1:
#         flg = 0
#         break

if g_set > 1:
    print('not coprime')
elif flg:
    print('pairwise coprime')
else:
    print('setwise coprime')