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 numpy as np


def get_pseudo_input():
    N = 3
    A = np.array([6, 10, 16])
    return N, A


def get_input():
    N = int(input())
    A = np.array([int(x) for x in input().split()])
    return N, A


def sieve_of_eratosthenes(x: int):
    ret = np.full(x + 1, -1)
    for i in range(1, x + 1):
        ret[i] = i
    p_max = int(math.sqrt(x))
    for p in range(2, p_max + 1):
        if ret[p] < p:  # p is not a prime number
            continue
        for i in range(p, x + 1, p):
            if ret[i] > p:
                ret[i] = p
    return ret


A_max = 10 ** 6
p_table = sieve_of_eratosthenes(A_max)

N, A = get_input()
# Store a number of unique Ais using the prime number
p_nums = np.zeros(A_max + 1)
p_nums[1] = N
max_p_nums = 0
for a in A:
    # print(f"a={a}")
    while a > 1:
        p = p_table[a]
        while a % p == 0:
            a = a // p
        # print(f"  a={a}")
        p_nums[p] += 1
        if max_p_nums < p_nums[p]:
            max_p_nums = p_nums[p]
# print(max_p_nums)
if max_p_nums <= 1:
    # GCD of A is 1
    print("pairwise coprime")
elif max_p_nums == N:
    # GCD of A is not 1
    print("not coprime")
else:
    print("setwise coprime")

Submission status: Time Limit Exceeded

Solution code:
from math import gcd, sqrt
from functools import reduce
def sieve(n):
    if n <= 4:
        return list(range(2, n))
    def _sieve_of_eratosthenes(n):
        table = [1] * n
        table[0] = table[1] = 0
        for i in range(2, int(sqrt(n))+1):
            if table[i]:
                for j in range(i**2, n, i):
                    table[j] = 0
        return [i for i in range(2, n) if table[i]]
    return _sieve_of_eratosthenes(n)

n, *A = map(int, open(0).read().split())
P = sieve(max(A))

def f(A, P):
    D = set()
    for a in A:
        for p in P:
            if a % p == 0:
                if p not in D:
                    D.add(p)
                    a //= p
                else:
                    return False
    return True

if reduce(gcd, A) == 1:
    if f(A, P):
        print('pairwise coprime')
    else:
        print('setwise coprime')
else:
    print('not coprime')

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

from math import gcd

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

def eratosthenes(limit):
    import math
    if not isinstance(limit, int):
        raise TypeError('n is int type.')
    if limit < 2:
        raise ValueError('n is more than 2')
    prime = []
    sqrt_limit = math.sqrt(limit)
    prime_numbers_list = [i + 1 for i in range(1, limit)]
    while True:
        p = prime_numbers_list[0]
        if sqrt_limit <= p:
            return prime + prime_numbers_list
        prime.append(p)
        prime_numbers_list = [e for e in prime_numbers_list if e % p != 0]
    return prime_numbers_list

def main():
    a.sort()

    g = 0
    for aa in a:
        g = gcd(g,aa)
    if g > 1:
        print('not coprime')
        exit()

    if a[-1]==1:
        print('pairwise coprime')
        exit()

    prime_numbers_list = eratosthenes(a[-1])
    count = [0]*len(prime_numbers_list)

    for aa in a:
        for i, prime in enumerate(prime_numbers_list):
            if aa % prime ==0:
                count[i] += 1
                if count[i]==2:
                    print('setwise coprime')
                    exit()
                break

    print('pairwise coprime')

main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

from math import gcd


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

def eratosthenes(limit):
    import math
    if not isinstance(limit, int):
        raise TypeError('n is int type.')
    if limit < 2:
        raise ValueError('n is more than 2')
    prime = []
    sqrt_limit = math.sqrt(limit)
    prime_numbers_list = [i + 1 for i in range(1, limit)]
    while True:
        p = prime_numbers_list[0]
        if sqrt_limit <= p:
            return prime + prime_numbers_list
        prime.append(p)
        prime_numbers_list = [e for e in prime_numbers_list if e % p != 0]
    return prime_numbers_list


def main():
    a.sort()

    g = 0
    for aa in a:
        g = gcd(g,aa)
    if g > 1:
        print('not coprime')
        exit()


    if a[-1]==1:
        print('pairwise coprime')
        exit()

    prime_numbers_list = eratosthenes(n)

    count = [0]*len(prime_numbers_list)

    for aa in a:
        for i, prime in enumerate(prime_numbers_list):
            if aa % prime ==0:
                count[i] += 1
                if count[i]==2:
                    print('setwise coprime')
                    exit()
                break

    print('pairwise coprime')

main()

Submission status: Time Limit Exceeded

Solution code:

import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

from math import gcd


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

g = 0
for aa in a:
    g = gcd(g,aa)
if g > 1:
    print('not coprime')
    exit()

def eratosthenes(limit):
    import math
    if not isinstance(limit, int):
        raise TypeError('n is int type.')
    if limit < 2:
        raise ValueError('n is more than 2')
    prime = []
    sqrt_limit = math.sqrt(limit)
    prime_numbers_list = [i + 1 for i in range(1, limit)]
    while True:
        p = prime_numbers_list[0]
        if sqrt_limit <= p:
            return prime + prime_numbers_list
        prime.append(p)
        prime_numbers_list = [e for e in prime_numbers_list if e % p != 0]
    return prime_numbers_list


if a[-1]==1:
    print('pairwise coprime')
    exit()

prime_numbers_list = eratosthenes(n)

count = [0]*len(prime_numbers_list)

for aa in a:
    for i, prime in enumerate(prime_numbers_list):
        if aa % prime ==0:
            count[i] += 1
            if count[i]==2:
                print('setwise coprime')
                exit()
            break

print('pairwise coprime')

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce
from math import gcd

N=int(input())
A=list(map(int, input().split()))
c=max(A)+1
C=[0]*c
f=1
for i in A:
    C[i]+=1

for i in range(2,c):
    cnt=0
    for j in range(i,c,i):
        cnt+=C[j]
    if cnt>1:
        f=0


if f==1:
    print('pairwise coprime')

elif reduce(gcd, A) == 1:
    print('setwise coprime')

else:
    print('not coprime')

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce
from math import gcd

N=int(input())
A=list(map(int, input().split()))
c=10**6+1
C=[0]*c
f=1
for i in A:
    C[i]+=1

for i in range(2,c):
    cnt=0
    for j in range(i,c,i):
        cnt+=C[j]
    if cnt>1:
        f=0


if f==1:
    print('pairwise coprime')

elif reduce(gcd, A) == 1:
    print('setwise coprime')

else:
    print('not coprime')

Submission status: Time Limit Exceeded

Solution code:
max_num = 10**6 + 1
prime = [i for i in range(max_num)]
r2_num = int(max_num**(1/2))+1
for i in range(2, r2_num):
  if prime[i] == i:
    for j in range(i**2, max_num, i):
      if prime[j] == j:
        prime[j] = i
def gcd(a, b): # a >= b
  if a%b == 0:
    return b
  else:
    return gcd(b, a%b)

flg_pairwise = True
flg_setwise = False

n = int(input().rstrip())
a_ls = list(map(int, input().rstrip().split(" ")))
gcd_a = 0
primes_a = []
count_prime = [0 for i in range(max_num)]
for a in a_ls:
  gcd_a = gcd(gcd_a, a)
  if gcd_a == 1:
    flg_setwise = True
  tmp_prime = []
  if flg_pairwise:
    while a > 1:
      p = prime[a]
      if tmp_prime == [] or tmp_prime[-1] != p:
        tmp_prime.append(p)
        a = a//p
    for tp in tmp_prime:
      for pa in primes_a:
        if pa == tp:
          flg_pairwise = False
          break
      if flg_pairwise:
        primes_a.append(tp)
      else:
        break
  if flg_setwise and not flg_pairwise:
    break
if flg_pairwise:
  print("pairwise coprime")
elif flg_setwise:
  print("setwise coprime")
else:
  print("not coprime")

Submission status: Time Limit Exceeded

Solution code:
max_num = 10**6 + 1
prime = [i for i in range(max_num)]
r2_num = int(max_num**(1/2))+1
for i in range(2, r2_num):
  if prime[i] == i:
    for j in range(i**2, max_num, i):
      if prime[j] == j:
        prime[j] = i
def gcd(a, b): # a >= b
  if a%b == 0:
    return b
  else:
    return gcd(b, a%b)

flg_pairwise = True
flg_setwise = False

n = int(input().rstrip())
a_ls = list(map(int, input().rstrip().split(" ")))
gcd_a = a_ls[0]
count_prime = [0 for i in range(max_num)]
for a in a_ls:
  gcd_a = gcd(gcd_a, a)
  if gcd_a == 1:
    flg_setwise = True
  tmp_prime = []
  while a > 1:
    p = prime[a]
    if tmp_prime == [] or tmp_prime[-1] != p:
      tmp_prime.append(p)
    a = a//p
  for tp in tmp_prime:
    if not count_prime[tp]:
      count_prime[tp] = 1
    else:
      flg_pairwise = False
      break
  if flg_setwise and not flg_pairwise:
    break
if flg_pairwise:
  print("pairwise coprime")
elif flg_setwise:
  print("setwise coprime")
else:
  print("not coprime")

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce
from math import gcd

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

c=max(A)+1
D=[0]*c
div=[0]*c
P=[]

for i in range(2,c):
    if D[i]==0:
        P.append(i)
        D[i]=i
    for j in P:
        if i*j>=c  or j>D[i] :
           break
        D[i*j]=j

for i in A:
    if i==1:
        continue
    temp=i
    while temp!=1:
        div[D[temp]]+=1
        temp2=D[temp]
        while temp%temp2==0 and temp>=temp2:
            temp=temp//temp2


if max(div)<=1:
    print('pairwise coprime')

elif reduce(gcd, A) == 1:
    print('setwise coprime')

else:
    print('not coprime')

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce
from math import gcd

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

c=max(A)+1
D=[0]*c
div=[0]*c
P=[]

for i in range(2,c):
    if D[i]==0:
        P.append(i)
        D[i]=i
    for j in P:
        if i*j>=c  or j>D[i] :
           break
        D[i*j]=j

for i in A:
    if i==1:
        continue
    temp=i
    pt=[]
    while temp!=1:
        if D[temp] not in pt:
            div[D[temp]]+=1
        pt.append(D[temp])
        temp=temp//D[temp]

#print(div)

if max(div)<=1:
    print('pairwise coprime')

elif reduce(gcd, A) == 1:
    print('setwise coprime')

else:
    print('not coprime')

Submission status: Time Limit Exceeded

Solution code:
prime=[[] for _ in range(1000000+1)]

for i in range(2,1000000+1):
    if prime[i]==[]:
        for j in range(i,1000000+1,i):
            prime[j].append(i)
n=eval(input())
trs=list(map(int,input().split()))
check=[]
flag=True
for i in trs:
    for _ in prime[i]:
        if _ in check:
            flag=False
            break
        else:
            check.append(_)
tmp=[]
if flag==False:
    for _ in trs:
        if check!=[]:
            tmp=[]
            for i in check:
                if _%i==0:
                    tmp.append(i)
            check=tmp
    if check==[]:
        print("setwise coprime")
    else:
        print('not coprime')
else:
    print('pairwise coprime')

Submission status: Time Limit Exceeded

Solution code:
prime=[[] for _ in range(1000000+1)]

for i in range(2,1000000+1):
    if prime[i]==[]:
        for j in range(i,1000000+1,i):
            prime[j].append(i)
n=eval(input())
lis=[]
trs=list(map(int,input().split()))
for m in trs:
    lis.append(prime[m])
check=[]
flag=True
for i in range(n):
    for _ in lis[i]:
        if _ in check:
            flag=False
            break
        else:
            check.append(_)
tmp=[]
if flag==False:
    for _ in trs:
        if check!=[]:
            tmp=[]
            for i in check:
                if _%i==0:
                    tmp.append(i)
            check=tmp
    if check==[]:
        print("setwise coprime")
    else:
        print('not coprime')
else:
    print('pairwise coprime')

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import sys
i4 = np.int32
i8 = np.int64
u4 = np.uint32

if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC
    from numba import njit
    from numba.types import int64, Array, uint32
    cc = CC('my_module')

    @njit
    def factorization(N):
        p = np.zeros(N + 1, u4)
        n_max = int(np.sqrt(N)) + 1
        p[0] = 1
        p[1] = 1
        for i in range(2, n_max):
            if p[i] == 0:
                j = i
                while j <= N:
                    p[j] = i
                    j += i
        for i in range(n_max, N + 1):
            if p[i] == 0:
                p[i] = i
        return p

    @cc.export('solve', (Array(uint32, 1, 'C'),))
    def solve(A):
        a = np.sort(A)
        p_max = a[-1]
        p = factorization(p_max)
        primes_num = 0
        for i in range(p.shape[0]):
            if i == p[i]:
                primes_num += 1
        a_start = 0
        while a[a_start] == 1:
            a_start += 1
            if a_start == a.shape[0]:
                return 0
        a = a[a_start:]
        if len(a) > primes_num:
            return 1
        check = np.zeros(p_max + 1, u4)
        s = set()
        for d in a:
            while d > 1:
                x = p[d]
                s.add(x)
                d //= x

            while s:
                check[s.pop()] += 1

        if check.max() > 1:
            return 1
        else:
            return 0
    cc.compile()
    exit()


def main(in_file):
    stdin = open(in_file)
    stdin.readline()
    A = np.fromstring(stdin.readline(), u4, sep=' ')
    ans = solve(A)
    if ans:
        g = np.gcd.reduce(A)
        if g > 1:
            ans = 2
        else:
            ans = 1
    p = ['pairwise coprime', 'setwise coprime', 'not coprime']
    print(p[ans])


if __name__ == '__main__':
    from my_module import solve
    main('/dev/stdin')

Submission status: Time Limit Exceeded

Solution code:
prime=[[] for _ in range(1000000+1)]

for i in range(2,1000000+1):
    if prime[i]==[]:
        for j in range(i,1000000+1,i):
            prime[j].append(i)
n=eval(input())
lis=[]
trs=list(map(int,input().split()))
for m in trs:
    lis.append(prime[m])
check=[]
dic={}  
flag=True
for i in range(n):
    for _ in lis[i]:
        if _ in check:
            flag=False
            if _ in dic.keys():
                dic[_]+=1
            else:
                dic[_]=1
        else:
            check.append(_)
if flag==False:    
    c=max(dic.values())
    if c==n-1:
        print('not coprime')
    else:
        print('setwise coprime')
else:
    print('pairwise coprime')

Submission status: Time Limit Exceeded

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

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

#高速素因数分解

#エラストテネスのふるい
#sieveが0なら素数、0以外ならその値を割り切る素数
def create_sieve(n):
  sieve=[0]*(n+1)
  for i in range(2,n+1):
    if sieve[i]==0:
      for j in range(i*i,n+1,i):
        sieve[j]=i
  return sieve
#素因数分解
#dicではkey=素数、value=何乗か
def prime(n):
  sieve=create_sieve(n)
  dic={}
  while(1):
    if sieve[n]==0:
      dic[n]=dic.get(n,0)+1
      break
    else:
      p=sieve[n]
      dic[p]=dic.get(p,0)+1
      n=n//p
  return dic

def setwise(a):
  l=a[0]
  for i in range(len(a)):
    l=gcd(l,a[i])
  return l==1


if setwise(a):
  check=set()
  for num in a:
    if num!=1:
      dic=prime(num)
      for j in dic:
        if j in check:
          print("setwise coprime")
          exit()
        else:
          check.add(j)
  print("pairwise coprime")
  
else:
  print("not coprime")

Submission status: Time Limit Exceeded

Solution code:
from math import gcd
import numpy as np

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

c=max(A)
D=np.array([0]*(c+1))
div=np.array([0]*(c+1))
P=np.array([])

for i in range(2,c+1):
    if D[i]==0:
        P=np.append(P,i)
        D[i]=i
    for j in P:
        if i*j>c  or j>D[i] :
           break
        D[int(i*j)]=j
f=0
for i in A:
    c=gcd(c,i)
    if i==1:
        continue
    temp=i
    if temp==D[temp]:
        div[temp]+=1
    while temp!=D[temp]:
        div[D[temp]]+=1
        if div[temp]>=2:
            f=1
        temp=temp//D[temp]

if max(div)<=1:
    print('pairwise coprime')

elif c==1:
    print('setwise coprime')

else:
    print('not coprime')