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 sys
import math
import collections
import bisect
import itertools
import decimal

# import numpy as np

# sys.setrecursionlimit(10 ** 6)
INF = 10 ** 20
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline().rstrip())
ns = lambda: map(int, sys.stdin.readline().rstrip().split())
na = lambda: list(map(int, sys.stdin.readline().rstrip().split()))
na1 = lambda: list(map(lambda x: int(x) - 1, sys.stdin.readline().rstrip().split()))


# ===CODE===


class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


def main():
    n = ni()
    a = na()

    # N以下の素数列挙
    def make_prime_nums(n):
        prime_nums = [2 if n >= 2 else None]
        for i in range(3, n + 1):
            for p in prime_nums:
                if p >= int(i ** (1 / 2)) + 1:
                    prime_nums.append(i)
                    break
                if i % p == 0:
                    break
        return prime_nums

    prime = make_prime_nums(10 ** 3)

    pc = True
    tc = True

    for pi in prime:
        cnt = 0
        for i in range(n):
            flg = False
            while a[i] % pi == 0:
                a[i] //= pi
                flg = True
            if flg:
                cnt += 1
        if cnt > 1:
            pc = False
        if cnt == n:
            tc = False

    ca = collections.Counter(a)
    for k, v in ca.items():
        if k>1:
            if ca[k] > 1:
                pc = False
            if ca[k] == n:
                tc = False

    if pc:
        print("pairwise coprime")
    elif tc:
        print("setwise coprime")
    else:
        print("not coprime")


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3


import collections
import functools

try:
    from math import gcd
except ImportError:
    from fractions import gcd


L = 10 ** 6 + 1


def sieve_of_eratosthenes(end):
    """Enumerates prime numbers below the given integer `end`.

    Returns (as a tuple):

    - `is_prime`: a list of bool values.
      If an integer `i` is a prime number, then `is_prime[i]` is True.
      Otherwise `is_prime[i]` is False.
    - `primes`: a list of prime numbers below `end`.
    """

    if end <= 1:
        raise ValueError("The integer `end` must be greater than one")
    is_prime = [True for _ in range(end)]
    is_prime[0] = False
    is_prime[1] = False
    primes = []
    for i in range(2, end):
        if is_prime[i]:
            primes.append(i)
            for j in range(2 * i, end, i):
                is_prime[j] = False
    return primes


PRIMES = sieve_of_eratosthenes(L)


def factorize(n):
    factors = []
    if n < 2:
        return factors
    for p in PRIMES:
        if p * p > n:
            break
        while n % p == 0:
            factors.append(p)
            n //= p
    if n > 1:
        factors.append(n)
    return factors


def is_pairwise_coprime(bs):
    lcm_fs = collections.defaultdict(int)
    all_fs = collections.Counter()
    for b in bs:
        fs = collections.Counter(factorize(b))
        all_fs.update(fs)
        for k, v in fs.items():
            lcm_fs[k] = max(lcm_fs[k], v)
    return all(lcm_fs[k] == all_fs[k] for k in lcm_fs)


def is_setwise_coprime(bs):
    return functools.reduce(gcd, bs) == 1


def main():
    n = int(input())
    bs = [int(b) for b in input().split()]
    if is_pairwise_coprime(bs):
        print("pairwise coprime")
    elif is_setwise_coprime(bs):
        print("setwise coprime")
    else:
        print("not coprime")


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import math
from math import gcd
n = int(input())
a = list(map(int, input().split()))
a.sort()
used = [False] * (10**6+1)

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

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

        if serial >= sqrt:
            return input_list

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

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

def factorization(n):
    arr = []
    temp = n
    for i in prime_list:
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append(i)
    if temp!=1:
        arr.append(temp)
    if arr==[]:
        arr.append(n)
    return arr

g = a[0]
arr = factorization(a[0])
for i in arr:
    used[i] = True

pair = True
for i in range(n-1):
    g = gcd(g, a[i+1])
    # 一度でも互いに素でない組合せが出たらpariwise coprimeではない
    arr = factorization(a[i+1])
    for i in arr:
        if i == 1: continue
        if used[i]: pair=False
        used[i] = True
if g > 1:
    print('not coprime')
    exit(0)
if not pair:
    print('setwise coprime')
    exit(0)
else:
    print('pairwise coprime')

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import collections
from decimal import Decimal # 10進数で考慮できる

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

d = collections.deque()
def LI(): return list(map(int, sys.stdin.readline().split()))

N = int(input())
A = LI()

"""
pairwise coprime 1,3,7,10
setwise coprime 2,3,4,10


coprimeかどうかで全部やる
"""

def primes(n): #試し割り法で各素因数とその指数を求める
    cnt=collections.defaultdict(int)
    for i in range(2,int(n**0.5)+1):
        if n%i==0:
            while n%i==0:
                cnt[i]+=1
                n//=i
    if n!=1:
        cnt[n]+=1
    return cnt


def solve():
    gcd = A[0]
    for a in A:
        gcd = math.gcd(gcd, a)
    if gcd != 1:
        return "not coprime"

    history = {}
    for i in range(10**6):
        history[i] = 0

    for a in A:
        d = primes(a)
        for key in d.keys():
            history[key] += 1
            if history[key] > 1:
                return "setwise coprime"
    return "pairwise coprime"
 
    
print(solve())

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=list(map(int,input().split()))
import sys
import math
def setwise_coprime(a):
  ans=a[0]
  for i in range(1,n):
    ans=math.gcd(ans,a[i])
  return ans
ruiseki=1
for i in range(n):
  ruiseki=ruiseki*a[i]

for i in range(n):
    num=math.gcd(a[i],ruiseki//a[i])
    if num!=1:
      if setwise_coprime(a)==1:
        print("setwise coprime")
        sys.exit()
      else:
        print("not coprime")
        sys.exit()
print("pairwise coprime")

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 8)
from itertools import accumulate
from itertools import permutations
from itertools import combinations
from collections import defaultdict
from collections import Counter
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
import heapq
from copy import deepcopy
from decimal import Decimal
alf = list("abcdefghijklmnopqrstuvwxyz")
ALF = list("ABCDEFGHIJKLMNOPQRSTUVWXYZ")
#import numpy as np
INF = float("inf")
#d = defaultdict(int)
#d = defaultdict(list)
N = int(input())
def primes(n):#nまでの素数を列挙0は入れちゃダメ
    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 is_prime
A = list(map(int,input().split()))
MAX = max(A)
prime = primes(MAX)
pri = [i for i in  range(2,MAX+1) if prime[i]]
n = len(pri)
cnt = [0]*(MAX+1)
def factorization(n): #2以上の整数n => [[素因数, 指数], ...]の2次元リストを返す
    arr = []
    temp = n
    for i in pri:
        if i > int(n**0.5):
            break
        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 i in range(N):
    a = A[i]
    li = factorization(a)
    for tu in li:
        b = tu[0]
        cnt[b] += 1
flag1 = 0
flag2 = 0
for i in pri:
    a = cnt[i]
    if a > 1:
        flag1 = 1
    if a == N:
        flag2 = 1
if flag1 == 0:
    print("pairwise coprime")
elif flag2 == 1:
    print("not coprime")
else:
    print("setwise 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
    d = dict()
    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:
import math
N=int(input())
A=[int(x) for x in input().split()]
gcd=A[0]
for i in range(1,N):
    gcd=math.gcd(gcd,A[i])
if gcd!=1:
    print("not coprime")
else:
    flag=1
    maxA=max(A)
    primeset=set()
    primeset.add(2)
    for h in range(3,maxA+1):
        flag=1
        for k in primeset:
            if h%k==0:
                flag=0
                break
        if flag==1:
            primeset.add(h)
    already_prime=set()
    for j in range(N):
        now=A[j]
        for k in primeset:
            if now%k==0:
                if k in already_prime:
                    flag=0
                    break
                else:
                    already_prime.add(k)

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

Submission status: Time Limit Exceeded

Solution code:
from math import gcd

N = int(input())
A_list = [int(_) for _ in input().split()]

is_pairwise = True
is_setwise = False

for i in range(len(A_list)):
    if i < N:
        for j in range(i+1, N):
            if gcd(A_list[i], A_list[j]) != 1:
                is_pairwise = False
                break
    if not is_pairwise:
        break

if is_pairwise:
    print('pairwise coprime')
else:
    ans = A_list[0]
    for i in range(1, N):
        ans = gcd(ans, A_list[i])
        if ans == 1:
            is_setwise = True
            break
    if is_setwise:
        print('setwise coprime')
    else:
        print('not coprime')

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
import sys
input = lambda : sys.stdin.readline().rstrip()

n = int(input())
As = map(int, input().split(" "))

is_set = False

first = True
A0 = As[0]
for i in range(1, n):
    if i == 1:
        g = gcd(A0, As[i])
    else:
        g = gcd(g, As[i])

    if g == 1:
        is_set = True
        break

if is_set:
    is_pair = True
    As = list(set(As))
    n = len(As)
    for i in range(n-1):
        for j in range(i+1, n):
            g = gcd(As[i], As[j])
            if g != 1:
                is_pair = False
                break
else:
    is_pair = False

if is_pair:
    print("pairwise coprime")
elif is_set:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict
from fractions import gcd
N=int(sys.stdin.readline().strip())
A=map(int, sys.stdin.readline().split())

def factorization(n):
    arr=set()
    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.add(i)

    if temp!=1:
        arr.add(temp)

    if arr==[]:
        arr.add(n)

    return arr

pairwise_coprime=True

SOINSU=defaultdict(lambda: 0)

setwise_coprime=None
for i,a in enumerate(A):
    #全ての数が互いに素か　pairwise coprime判定
    f=factorization(a)
    for x in f:
        if SOINSU[x]==1:
            pairwise_coprime=False
            break
        SOINSU[x]=1
    #GCDの累積を取る　setwise coprime判定
    if i==0:
        setwise_coprime=a
    else:
        setwise_coprime=gcd(setwise_coprime,a)

if pairwise_coprime==True:
    print "pairwise coprime"
elif setwise_coprime==1:
    print "setwise coprime"
else:
    print "not coprime"

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):
    k=gcd(l,ar[i])
    if k!=1:
        t=-1
        break
    else:
        l= (l*ar[i])//(k)
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:
N = int(input())
A = list(map(int, input().split()))

M = 1000

P = [True for i in range(M+1)]
p_set = set()
for i in range(2,M+1):
  if P[i]:
    p_set.add(i)
    for j in range(2*i, M+1, i):
      P[j] = False
#print( len(p_set) )
#N = 10 ** 6
#A = [1001 for i in range(N)]

c = 0
for p in p_set:
  c_tmp = 0
  for i in range(N):
    if A[i] % p == 0:
      c_tmp += 1
      while A[i] % p == 0:
        A[i] //= p
  c = max(c, c_tmp)

dic = {}
for a in A:
  if a > M:
    if a in dic:
      dic[a] += 1
    else:
      dic[a] = 1
for v in dic.values():
  c = max(c, v)

if c == N:
  print("not coprime")
elif c < 2:
  print("pairwise coprime")
else:
  print("setwise coprime")

Submission status: Time Limit Exceeded

Solution code:
##https://www.codechef.com/viewsolution/20131475

from math import gcd

N = (10 ** 6) + 100

sv = [i for i in range(N)]
for i in range(2 , N) :
    if i * i >= N : break
    if sv[i] < i : continue
    for j in range(i * i , N , i) :
        sv[j] = min(sv[j] , i)

def getPrimes(a) :
    pr = []
    if a == 1 : return pr
    pr.append(sv[a])
    while a > 1 :
        if sv[a] != pr[-1] :
            pr.append(sv[a])
        a //= sv[a]
    return pr

np = [0] * N
F = [0] * N

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

for a in A :
    pr = getPrimes(a)
    for i in range(1 << len(pr)) :
        prod , nb = 1 , 0
        for j in range(len(pr)) :
            if i & (1<<j) :
                prod *= pr[j]
                nb += 1
        F[prod] += 1
        np[prod] = nb

ans = 0
for i in range(N) :
    cnt = F[i]
    cnt = (cnt * (cnt-1))//2
    if np[i] & 1 : ans -= cnt
    else : ans += cnt

if ans == (n*(n-1))//2:
    print("pairwise coprime")
    exit()

A.sort()
d = A[0]

for i in A:
    d = gcd(i,d)
    if d == 1:
        break

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

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
INF = 10 ** 9


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


def is_pairwise_coprime():
    for i in range(n):
        for j in range(i + 1, n):
            if gcd(a[i], a[j]) != 1:
                return False
    return True


def is_setwise_coprime():
    g = a[0]
    for i in range(n - 1):
        g = min(g, gcd(g, a[i + 1]))
    return g == 1


if is_pairwise_coprime():
    print('pairwise coprime')
elif is_setwise_coprime():
    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()))
g = A[0]
mul = A[0]
pflag = True
for i in range(n-1):
  if pflag and gcd(mul,A[i+1]) != 1:
    pflag = False
  mul *= A[i+1]
  g = gcd(g,A[i+1])
if g != 1:
  print("not coprime")
else:
  if pflag:
    print("pairwise coprime")
  else:
    print("setwise coprime")

Submission status: Time Limit Exceeded

Solution code:
import math
n = int(input())
a = list(map(int,input().split()))
s = []
t = [0]*1010
u = []
for i in range(2,1010):
    x = 1
    for j in range(2,i):
        if(i%j == 0):
            x = 0
            break
    if(x == 1):
        u.append(i)
m = len(u)
for i in range(n):
    for j in range(m):
        if(a[i]%u[j] == 0):
            t[j] += 1
            a[i] //= u[j]
            if(a[i] == 1):
                break
    if(a[i] != 1):
        s.append(a[i])
if(max(t) == n):
    print('not coprime')
elif(max(t) <= 1):
    z = 0
    for i in range(1,len(s)):
        for j in range(i):
            if(math.gcd(s[i],s[j]) > 1):
                z = 1
                break
    if(z == 1):
        print('setwise coprime')
    else:
        print('pairwise coprime')
else:
    print('setwise coprime')

Submission status: Time Limit Exceeded

Solution code:
MOD=10**9+7
import sys
import math
N=int(input())
alist=list(map(int,input().split()))
alist.sort()

all_GCD=alist[0]
for i in range(1,N):
  all_GCD=math.gcd(all_GCD,alist[i])
  if all_GCD==1:
    break
else:
  print("not coprime")
  sys.exit(0)
  
lcm=1
prod=1
for i in range(N):
  lcm=lcm*alist[i]*math.gcd(lcm,alist[i])
  prod*=alist[i]
  if lcm!=prod:    
    print("setwise coprime")
    sys.exit(0)
    
print("pairwise coprime")

Submission status: Time Limit Exceeded

Solution code:
import sys
import resource
from collections import defaultdict

dic=set()
sys.setrecursionlimit(100000)

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

def prime_factorization(num):
    i=2
    tmp=set()
    while num >= i*i:
        while num%i==0:
            num//=i
            tmp.add(i)
        i+=1
    if num!=1: tmp.add(num)
    return tmp

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

s=a[0]
flag=0
for i in a:
    s=gcd(s,i)
    p=prime_factorization(i)
    for v in p:
        if v in dic:
            flag=1
        dic.add(v)
if not flag: print("pairwise coprime")
elif s==1: print("setwise coprime")
else: print("not coprime")

Submission status: Time Limit Exceeded

Solution code:
def PrimeFactorization(n):
    pf = set()
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            yield i
            n //= i
            while n % i == 0:
                n //= i
    if n > 1:
        yield n


def resolve():
    import copy
    n = int(input())
    a = list(map(int, input().split()))
    pairwise = True
    d = {}
    for i in a[:-1]:
        for j in PrimeFactorization(i):
            if pairwise and j in d:
                pairwise = False
            d[j] = d.get(j, 0) + 1
    for j in PrimeFactorization(a[-1]):
        if pairwise and j in d:
            pairwise = False
        if d.get(j, 0) == n - 1:
            print("not coprime")
            return
    if pairwise:
        print("pairwise coprime")
    else:
        print("setwise coprime")


if __name__ == '__main__':
    resolve()

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:
        break
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:
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

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
    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:
n=int(input())
a_list = list(map(int,input().split()))

def prime_decomposition(n):
  i = 2
  table = []
  while i * i <= n:
    while n % i == 0:   # iで割り切れれば、iはnの素因数
      n //= i
      table.append(i)
    i += 1
  if n > 1:
    table.append(n)
  return table

set_len_list = [0]*n
set_all = {1}
for i in range(n):
    set_i_tmp = set(prime_decomposition(a_list[i]))
    set_len_list[i] = len(set_i_tmp)
    set_all = set_all.union(set_i_tmp)
    if i == 0:
        set_int = set_i_tmp
    else:
        set_int = set_int.intersection(set_i_tmp)

if sum(set_len_list) == len(set_all)-1:
    print('pairwise coprime')
elif len(set_int) == 0:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations
import math
import sys
import functools

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

gcd = []
for i, j in lis:
    gcd.append(math.gcd(i, j))
if max(gcd) ==1:
    print('pairwise coprime')
    sys.exit()


ans = functools.reduce(math.gcd, A)
if ans == 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()))
g = A[0]
mul = A[0]
pflag = True
for i in range(n-1):
  if gcd(mul,A[i+1]) != 1:
    pflag = False
  mul *= A[i+1]
  g = gcd(g,A[i+1])
if g != 1:
  print("not coprime")
else:
  if pflag:
    print("pairwise coprime")
  else:
    print("setwise coprime")

Submission status: Time Limit Exceeded

Solution code:
import math 
import sys
from functools import reduce

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

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:
from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce, lru_cache
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def MAP1()  : return map(lambda x:int(x)-1,input().split())
def LIST()  : return list(MAP())
def LIST1() : return list(MAP1())

n = INT()
a = LIST()

k = 1
flag = 1
for i in range(1, n):
    k *= a[i-1]
    if gcd(k, a[i]) > 1:
        flag = 0

if flag == 1:
    print("pairwise coprime")
    exit()

else:
    g = a[0]
    for i in range(1, n):
        g = gcd(g, a[i])
    if g == 1:
        print("setwise coprime")
    else:
        print("not coprime")

Submission status: Time Limit Exceeded

Solution code:
import math 

MOD = 10 ** 9 + 7
n = int(input())
a = list(map(int, input().split()))
d = a[0]
m = a[0]
check = a[0]
def lcm(a,b):
    return a * b // math.gcd(a, b)
for i in range(1, n):
    d = math.gcd(d, a[-i])
    m = lcm(m, a[-i])
    check *= a[-i]
    check %= MOD
    if check != m % MOD:
        m = 0
if d != 1:
    print("not coprime")
elif m == 0:
    print("setwise coprime")
else:
    print("pairwise coprime")

Submission status: Time Limit Exceeded

Solution code:
# E - Coprime

n = int(input())
a = [int(x) for x in input().split()]

import math
for i in range(0,len(a)-1):
	for j in range((i+1),len(a)):
		if math.gcd(a[i],a[j]) == 1:
			if i == len(a)-2 and j == len(a)-1:
				j = 0
		else:
			break
if i == len(a)-2 and j == 0:
	print("pairwise coprime")
else:
	x = math.gcd(a[0],a[1])
	for k in range(2,len(a)):
		x = math.gcd(x,a[k])
	if x == 1:
		print("setwise coprime")
	else:
		print("not coprime")

Submission status: Time Limit Exceeded

Solution code:
import math
# 素数判定関数
def isPrime(num):
    # 2未満の数字は素数ではない
    if num < 2: return False
    # 2は素数
    elif num == 2: return True
    # 偶数は素数ではない
    elif num % 2 == 0: return False

    # 3 ~ numまでループし、途中で割り切れる数があるか検索
    # 途中で割り切れる場合は素数ではない
    for i in range(3, math.floor(math.sqrt(num))+1, 2):
        if num % i == 0:
            return False
    # 素数
    return True
# 素数判定
def callIsPrime(input_num=1000):
    numbers = []
    # ループしながら素数を検索する
    for i in range(1, input_num):
        if isPrime(i):
            numbers.append(i)

    # 素数配列を返す
    return numbers

N=int(input())
A=[int(x) for x in input().split()]
    
result="pairwise coprime"

for i in callIsPrime(min(10**6,max(A))):
  on=0
  off=0
  for a in set(A):
    if a%i==0:
      on+=1
    elif a%i!=0:
      off+=1
    if on>=2 and off>=1:
      break
  if on>=2 and off==0:
    result="not coprime"
    break
  elif on>=2:
    result="setwise coprime"
    
print(result)

Submission status: Time Limit Exceeded

Solution code:


import math
#素数列挙
def get_primes(limit):
    A = [i for i in range(2, limit+1)]
    P = []
    time = 0
    
    while True:
        prime = min(A)
        
        if prime > math.sqrt(limit):
            break
            
        P.append(prime)
            
        i = 0
        while i < len(A):
            if A[i] % prime == 0:
                A.pop(i)
                continue
            i += 1
            
    for a in A:
        P.append(a)
            
    return P


def resolve():
    N = int(input())
    A = list(map(int,input().split()))
    sosus = set(get_primes(max(A)+1))
    dvd = set()






    for i in A:
        tmp=[]
        for j in sosus:
            if i % j ==0:
                tmp.append(j)
                while i % j ==0:
                    i //=j
            if i ==1:
                break
        sosus.difference_update(tmp)
        
        if i != 1:
            break
    else:
        print('pairwise coprime')
        return

    val = A[0]
    for i in A:
        val = math.gcd(i,val)

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

resolve()

Submission status: Time Limit Exceeded

Solution code:
import math
N = int(input())
A = list(map(int, input().split()))
A.sort()
ans = 0
holdGcd = A[0]
setGcd = A[0]
pairwise = 1
setwise = 1
for i in range(N):
    cnt = 0
    for j in range(i+1,N):
        if A[i] > A[j+cnt]:
            cnt += 1
            continue
        setGcd = math.gcd(setGcd, A[j+cnt])
        holdGcd = math.gcd(A[i], A[j+cnt])
        # print(A[i], A[j+cnt], holdGcd, setGcd)
        if holdGcd != 1:
            pairwise = 0

if setGcd != 1:
    setwise = 0

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