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: Runtime Error

Solution code:
ma = lambda :map(int,input().split())
lma = lambda :list(map(int,input().split()))
tma = lambda :tuple(map(int,input().split()))
ni = lambda:int(input())
yn = lambda fl:print("Yes") if fl else print("No")
import collections
import math
def is_primes(n):
    primes = [1]*n
    primes[0] =0
    primes[1] =0
    for i in range(2,int(n**0.5)+1):
        if primes[i] ==1:
            for j in range(2*i,n,i):
                primes[j] = 0
    return primes

def factorize(n,prms):
    idx=0
    b = prms[idx]
    fct = []
    while b * b <= n:
        cnt =0
        while n % b == 0:
            n //= b
            cnt +=1
        if cnt >=1:
            fct.append((b,cnt))
            
        idx+=1
        b = prms[idx]
    if n > 1:
        fct.append((n,1))
    return fct

n =ni()
A = lma()
if max(A)==1:
    print("pairwise coprime")
mx= 10**6+100
prms = is_primes(mx)
d=collections.Counter()
for a in A:
    fct = factorize(a,prms)
    #print(fct)
    for fc,cnt in fct:
        d[fc]+=1
        if d[fc]==n:
            break
f1=True # pp or sp
f2=True # sp or other
for num,cnt in d.items():
    if cnt==n:
        f2=False #other
        break
    else:
        if cnt==1:
            pass
        else:
            f1=False
            break
if f2==False:
    print("not coprime")
elif f1 and f2:
    print("pairwise coprime")
elif f1==False:
    print("setwise coprime")

Submission status: Runtime Error

Solution code:
import math
n=int(input())
a=list(map(int,input().split()))
mxa=max(a)

def get_sieve_of_eratosthenes(mxa):
    fact = [0]*(mxa+1)
    limit = math.sqrt(mxa)
    data = [i + 1 for i in range(1, mxa)]
    while True:
        p = data[0]
        if limit <= p:
            return fact
        fact[p]=p
        for i in data:
            if i%p==0:
                fact[i]=p
        data = [e for e in data if e % p != 0]

fact= get_sieve_of_eratosthenes(mxa)

for i,j in enumerate(fact):
    if j==0:
        fact[i]=i
lst=[0]*(len(fact))
for i in range(n):
    prm_check = [False]*(mxa+1)
    while a[i]!=1:
        if not prm_check[fact[a[i]]]:
            lst[fact[a[i]]]+=1
            prm_check[fact[a[i]]] = True
        a[i]//=fact[a[i]]


pair=True
st=True

for i in lst:
    if i>=2:
        pair=False
    if i==n:
        st=False

if pair:
    print("pairwise coprime")
elif st:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Runtime Error

Solution code:
import math

def get_sieve_of_eratosthenes(n):
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 2:
        raise ValueError('n is more than 2')
    prime = []
    limit = math.sqrt(n)
    data = [i + 1 for i in range(1, 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]

n = int(input())
a = list(map(int,input().split()))
maxval = max(a)
p = get_sieve_of_eratosthenes(maxval)
d = [-1]*1000010
m = [-1]*1000010
flag = True


for i in p[::-1]:
  tmp = i
  multi = 2
  while(tmp<=maxval):
    d[tmp] = i
    tmp = tmp*multi
    multi += 1
    
for i in a:
  while(d[i]!=i):
    if(m[d[i]]==1):
      flag = False
      break
    m[d[i]] = 1
    i = i // d[i]
  m[d[i]] = 1
  if(flag == False):
    break
  
if(flag):
  print("pairwise coprime")
else:
  ans = a[0]
  for i in range(1, n):
    ans = math.gcd(ans, a[i])
  if ans==1:
    print("setwise coprime")
  else:
    print("not coprime")

Submission status: Runtime Error

Solution code:
import math
from functools import reduce

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

           
flg=True
table=[0]*(mxa+1)
for (i,x) in zip(a,range(len(a))):
  if i==1:
    continue
  fc=[]
  tmp=i
  for j in range(2, int(-(-num**0.5//1))+1):
    if tmp%j==0:
      while tmp%j==0:
        temp//=j
      fc.append(j)
  if tmp!=1:
    arr.append(tmp)
  if fc==[]:
    arr.append(tmp)
  for j in fc:
    if table[j]==1:
      flg=False
      break
    table[j]+=1

g=a[0]
for i in a[1:]:
  g=math.gcd(g,i)
    
if flg:
  print("pairwise coprime")
elif g==1:
  print("setwise coprime")
else:
  print("not coprime")

Submission status: Runtime Error

Solution code:
import math
from collections import deque

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

ans = "not coprime"

a, b = als[1], als[0]
if a < b:
    a,b = b,a
while a % b != 0:
    a, b = b, a % b
    if n == 2 and b == 1:
        ans = "pairwise coprime"
        failed = True

for i in range(2, n):
    a = als[i]
    if a < b:
        a,b = b,a 
    while a % b != 0:
        a, b = b, a % b
if b == 1:
    ans = "setwise coprime"
    # break

existeven = False

failed = False

for i in range(n):
    if als[i] >= 2 and als[i]%2 == 0:
        if existeven:
            failed = True
            break
        else:
            existeven = True

maxa = max(als)

afterchecklist = deque([])


if not failed:
    for i in range(3, math.sqrt(maxa)+2, 2):
        existfactrial = False
        failed = False
        for j in range(n):
            if als[j] >= i and als[j]%i == 0:
                afterchecklist.append(als[j]/i)
                if existfactrial:
                    failed = True
                    break
                else:
                    existfactrial = True
        if failed:
            break
    if not failed:
        for i in list(afterchecklist):
            existfactrial = False
            failed = False
            for j in range(n):
                if als[j] >= i and als[j]%i == 0:
                    if existfactrial:
                        failed = True
                        break
                    else:
                        existfactrial = True
            if failed:
                break
        ans = "pairwise coprime"

print(ans)

Submission status: Runtime Error

Solution code:
from math import gcd

N = int(input())
A = list(map(int, input().split()))
sieve = [1] * (10**5*5+1)
for i in range(2, 10**3):
	if sieve[i] == 1:
		sieve[i] = i
		j = 2
		while(j * i <= 10**5*5):
			sieve[j * i] = i
			j += 1
sieve[1] = 0

g = A[0]
a = 0
for i in range(1, N):
	g = gcd(g, A[i])
	if A[i] == 1:
		a = 1
	
if g != 1:
	print("not coprime")
else:
	if a == 1:
		print("setwise coprime")
		exit()
	s = set()
	for i in range(N):
		st = set()
		while(A[i] > 1):
			d = sieve[A[i]]
			if not(d in st) and d in s:
				print("setwise coprime")
				exit()
			s.add(d)
			st.add(d)
			A[i] //= d
	print("pairwise coprime")

Submission status: Runtime Error

Solution code:
import math

def get_sieve_of_eratosthenes(n):
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 2:
        raise ValueError('n is more than 2')
    prime = []
    limit = math.sqrt(n)
    data = [i + 1 for i in range(1, 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]

n = int(input())
a = list(map(int,input().split()))
maxval = max(a)
p = get_sieve_of_eratosthenes(maxval)
d = [-1]*1000010
m = [-1]*1000010
flag = True


for i in p:
  tmp = i
  multi = 2
  while(tmp<=maxval):
    d[tmp] = i
    tmp = tmp*multi
    multi += 1
    
for i in a:
  while(d[i]!=i):
    if(m[d[i]]==1):
      flag = False
      break
    m[d[i]] = 1
    i = i // d[i]
  m[d[i]] = 1
  if(flag == False):
    break
  
if(flag):
  print("pairwise coprime")
else:
  ans = a[0]
  for i in range(1, n):
    ans = math.gcd(ans, a[i])
  if ans==1:
    print("setwise coprime")
  else:
    print("not coprime")

Submission status: Runtime Error

Solution code:
import math
from collections import deque

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

ans = "not coprime"

a, b = als[1], als[0]
if a < b:
    a,b = b,a
while a % b != 0:
    a, b = b, a % b
    if n == 2 and b == 1:
        ans = "pairwise coprime"
        failed = True

for i in range(2, n):
    a = als[i]
    if a < b:
        a,b = b,a 
    while a % b != 0:
        a, b = b, a % b
if b == 1:
    ans = "setwise coprime"
    # break

existeven = False

failed = False

for i in range(n):
    if als[i] >= 2 and als[i]%2 == 0:
        if existeven:
            failed = True
            break
        else:
            existeven = True

maxa = max(als)

afterchecklist = deque([])


if not failed:
    for i in range(3, math.sqrt(maxa)+2, 2):
        existfactrial = False
        failed = False
        for j in range(n):
            if als[j] >= i and als[j]%i == 0:
                afterchecklist.append(als[j]/i)
                if existfactrial:
                    failed = True
                    break
                else:
                    existfactrial = True
        if failed:
            break
    if not failed:
        for i in afterchecklist:
            existfactrial = False
            failed = False
            for j in range(n):
                if als[j] >= i and als[j]%i == 0:
                    if existfactrial:
                        failed = True
                        break
                    else:
                        existfactrial = True
            if failed:
                break
        ans = "pairwise coprime"

print(ans)

Submission status: Runtime Error

Solution code:
def arrayF(n): 
    F=[0]*(n+1) 
    i=2 
    while i*i<=n:
        if F[i] == 0: 
            k=i*i
            while k <= n:
                if F[k] == 0:
                    F[k] = i
                k += i
        i += 1 
    return F


def factorization(x, F): 
    primeFactors = []
    while F[x] > 0:
        primeFactors.append(F[x])
        x //= F[x] 
    if x != 1:
        primeFactors.append(x)
    return set(primeFactors)

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

amax = max(A)
F  = arrayF(amax)

P = Counter()
P = [0] *  (amax+1)
for a in A:
    for p in factorization(a,  F):
        P[p] += 1
p_max = max(P)
if  p_max <= 1:
    print('pairwise coprime')
elif  p_max <  n:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Runtime Error

Solution code:
import sympy
import sys
input = sys.stdin.readline

def main():
    n = int( input() )
    Primes = [ -1 for i in range( 10 ** 6 + 1 ) ]
    Primes_num = []
    I = list( map( int, input().split() ) )
    for i in range( n ):
        a = I[i]
        x = sympy.factorint( a )
        for key in x:
            if Primes[key] != -1:
                Primes_num[ Primes[key] ] += 1
            else:
                Primes_num.append( 1 )
                l = len( Primes_num )
                Primes[ key ] = l - 1
    flag = 1
    flag_ = 1
    for i in Primes_num:
        if i != 1:
            flag = 0
        if i == n:
            flag_ = 0
    if flag == 1:
        print( 'pairwise coprime' )
    elif flag_ == 1:
        print( 'setwise coprime' )
    else:
        print('not coprime')




main()

Submission status: Runtime Error

Solution code:
import math
from collections import defaultdict as dd

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

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

for a in A:
  factor_a = get_prime_factors(a)
  for f in factor_a:
    factor_dict[f] += 1

max_t = max(factor_dict.values())
if max_t == 1:
  print("pairwise coprime")
elif max_t < N:
  print("setwise coprime")
else:
  print("not coprime")

Submission status: Runtime Error

Solution code:
// lcmとか__builtin_popcountとかはg++ -std=c++17 default.cppみたいなかんじで
// -fsanitize=undefinedでオーバーフロー検出
#include <bits/stdc++.h>
#define mod 1000000007
#define INF LLONG_MAX
#define ll long long
#define ln cout<<endl
#define Yes cout<<"Yes"<<endl
#define NO cout<<"NO"<<endl
#define YES cout<<"YES"<<endl
#define No cout<<"No"<<endl
#define REP(i,m,n) for(ll i=(ll)(m);i<(ll)(n);i++)
#define rep(i,n) REP(i,0,n)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
using namespace std;
ll dx[4]={1,0,-1,0};
ll dy[4]={0,1,0,-1};
std::vector<int> Eratosthenes( const int N )
{
    std::vector<bool> is_prime( N + 1 );
    for( int i = 0; i <= N; i++ )
    {
        is_prime[ i ] = true;
    }
    std::vector<int> P;
    for( int i = 2; i <= N; i++ )
    {
        if( is_prime[ i ] )
        {
            for( int j = 2 * i; j <= N; j += i )
            {
                is_prime[ j ] = false;
            }
            P.emplace_back( i );
        }
    }
    return P;
}


int main() {
    cin.tie(0);
   	ios::sync_with_stdio(false);
    int a,b,c,d,m,n,maxi=0,f=0,mini=1000,sum=0;
    string str;
        cin>>n;
    //vector<vector<int>> v(tate,vector<int> (yoko));
    vector<int> v(n);
    rep(i,n)   cin >> v[i];
    map<int,int> mp;
    set<int> s;
    
   // rep(i,n){
        for(const auto &x:Eratosthenes(10000)){
            sum++;
          //mp[x]++;
          s.insert(x);
        }        
    //}
    //cout<<sum<<endl;
    maxi=1;
    rep(i,n){
        for(auto itr=s.begin();itr!=s.end();++itr){
        if(v[i]%*itr==0) mp[*itr]++;
        }
    }
    for(auto itr=s.begin();itr!=s.end();++itr){
      if(*itr==1) continue;
      maxi=max(mp[*itr],maxi);
    }
    if(maxi==n) cout<<"not coprime"<<endl;
    else if(maxi==1) cout<<"pairwise coprime"<<endl;
    else cout<<"setwise coprime"<<endl;


    return 0;
}

Submission status: Runtime Error

Solution code:
import math
def eratos(n):
    isprime = [0 for i in range(n+1)]
    # isprime[0] = 0
    isprime[1] = 1
    for i in range(2, int(math.sqrt(n))+1):
        if isprime[i] == 0:
            j = i
            while j <= n:
                if isprime[j] == 0:
                    isprime[j] = i
                j = j + i
    return isprime

N = int(input())
A = list(map(int, input().split()))
isprime = eratos(10**6)
count = [0 for i in range(10**6+1)]
for ai in A:
    primes = {}
    while ai != 1:
        p = isprime[ai]
        primes[p] = 1
        ai //= p
    for p in primes.keys():
        count[p] += 1
max_c = max(count)
if max_c <= 1:
    print('pairwise coprime')
elif max_c == N:
    print('not coprime')
else:
    print('setwise coprime')

Submission status: Runtime Error

Solution code:
from math import gcd
import sys

def sieve(N):
    # 昇順リストの用意
    A_list = [i for i in range(2, N+1)]
    limit = A_list[-1]

    # ふるいにかけられたかどうかを示すbooleanの辞書
    sieve = {i: True for i in A_list}

    # 順にふるいにかける
    for a in A_list:
        if not sieve[a]:
            continue
        for i in range(2*a, limit+1, a):  # 2a, 3a, 4a, ..., と調べる
            if i in sieve:
                sieve[i] = False

    # 結果をまとめる
    primes = []
    for a in A_list:
        if sieve[a]:
            primes.append(a)
    return primes


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


# 素数列挙
primes = sieve(max(A))

# 順番に素数で割っていって、同じ素数で割れるものが見つかったらpairsiwe coprimeではない
for p in primes:
    divided_times = 0
    for a in A:
        if a % p == 0:
            divided_times += 1
    if divided_times >= 2:
        break
else:
    print('pairwise coprime')
    sys.exit()

# pairwise coprimeではない場合、以下の処理に進む
# globalなGCDを求めて、1ならsetwise coprime
global_gcd = gcd(A[0], A[1])
for a in A[2:]:
    global_gcd = gcd(global_gcd, a)
    
if global_gcd == 1:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Runtime Error

Solution code:
N = int(input())
A = list(map(int, input().split()))
A.sort()
R = int(A[-1]**0.5)

is_pairwise_coprime = True
is_setwise_coprime = True
checked = [0]*(R+2)
l = 0

for i in range(2, R+2):
    if checked[i]:
        continue
    
    # 調べる範囲を狭める
    while A[l] < i:
        l += 1
    if l == N-1:
        break
    
    # iで割り切れるAiの個数を数える
    tmp = 0
    for j in range(l, N):
        if A[j]%i == 0:
            tmp += 1
    # 2個以上あればnot pairwise coprime
    # N個あれば not setwise coprime
    if tmp > 1:
        is_pairwise_coprime = False
    if tmp == N:
        is_setwise_coprime = False
    
    if is_setwise_coprime == False:
        break
    
    # iの倍数はチェック済みにする
    n = i
    while n < R+2:
        checked[n] = 1
        n += i
    # print(checked, l)
if is_pairwise_coprime:
    print('pairwise coprime')
elif is_setwise_coprime:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Runtime Error

Solution code:
import math

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

ans = "not coprime"

a, b = als[1], als[0]
if a < b:
    a,b = b,a
while a % b != 0:
    a, b = b, a % b
    if n == 2 and b == 1:
        ans = "pairwise coprime"
        failed = True

for i in range(2, n):
    a = als[i]
    if a < b:
        a,b = b,a 
    while a % b != 0:
        a, b = b, a % b
if b == 1:
    ans = "setwise coprime"
    break

existeven = False

failed = False

for i in range(n):
    if als[i] >= 2 and als[i]%2 == 0:
        if existeven:
            failed = True
            break
        else:
            existeven = True

maxa = max(als)

if not failed:
    for i in range(3, int(math.sqrt(maxa))+2, 2):
        existfactrial = False
        failed = False
        for j in range(n):
            if als[j] >= i and als[j]%i == 0:
                if existfactrial:
                    failed = True
                    break
                else:
                    existfactrial = True
        if failed:
            break
    if not failed:
        ans = "pairwise coprime"

print(ans)

Submission status: Runtime Error

Solution code:
from math import gcd
from functools import reduce
n = int(input())
a = list(map(int, input().split()))

tmp = [set() for _ in range(10**2+1)]
for i in range(2, 10**2//2+1):
    for j in range(i, 10**2+1, i):
        tmp[j].add(i)


flag = False
for i in range(n-1):
    if len(tmp[a[i]] & tmp[max(a)]) > 0:
        flag = True
        break

if flag == False:
    print("pairwise coprime")
else:
    if reduce(gcd, a) == 1:
        print("setwise coprime")
    else:
        print("not coprime")

Submission status: Runtime Error

Solution code:
 = 1000001

spf = [*range(N)]
i = 2
while i * i < N:
  if spf[i] == i:
    for j in range(i * i, N, i):
      if spf[j] == j:
        spf[j] = i
  i += 1
  
t = 'setwise', None, 'pairwise', 'not'
r = 0
input()
u = set()
i = None
for x in map(int, input().split()):
  s = set()
  while x > 1:
    p = spf[x]
    if p in u:
      r |= 1
    s.add(p)
    x //= p
  u |= s
  if i: i &= s
  else: i = s
if not i:
  r |= 2
print(t[r], 'coprime')

Submission status: Runtime Error

Solution code:
from math import gcd

# = map(int, input().split())
N = int(input())
A = list(map(int, input().split()))
mA = max(A)
counter = [0 for _ in range(mA+1)]

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

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



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


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

Submission status: Runtime Error

Solution code:
import math
from functools import reduce
def gcbd_list(numbers):
    return reduce(math.gcd, numbers)
N = int(input())
A = list(map(int, input().split()))
P = [False] * (16 + 1)
c = True
for i in range(N):
    if P[A[i]] == True:
        c = False
    P[A[i]] = True
    for j in range(2, math.floor(A[i]**0.5)+1):
        if A[i] % j == 0:
            if P[j] == True:
                c = False
            P[j] = True
if c == True:
    print('pairwise coprime')
    exit()
if gcbd_list(A) == 1:
    print('setwise coprime')
    exit()
print('not coprime')

Submission status: Runtime Error

Solution code:
n = int(input())
arr = np.array(list(map(int, input().split())))


@njit
def solve(arr):
    for i in range(arr.shape[0] - 1):
        if np.gcd(arr[i], arr[i + 1]) != 1:
            ans1 = False
            break
    else:
        ans = True
    return ans


ans1 = solve(arr)
ans2 = np.gcd.reduce(arr) == 1

if ans1 and ans2:
    print("pairwise coprime")
elif ans2:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Runtime Error

Solution code:
from math import gcd
inpl = lambda: list(map(int,input().split()))
def primes(N):
    P = []
    for i in range(2,N):
        sieve = 1
        for p in P:
            if p*p > i:
                break
            elif i % p == 0:
                sieve = 0
                break
        if sieve == 0:
            continue
        else:
            P.append(i)
    return P

N = int(input())
A = inpl()

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

P = primes(1000)
for p in P:
    n = 0
    for i in range(N):
        if A[i] % p == 0:
            n += 1
            while A[i] % p == 0:
                A[i] //= p
            if n > 1:
                print('setwise coprime')
                exit()
s = set()
for a in A:
    if a == 1:
        continue
    elif a in s:
        print('setwise coprime')
	    exit()
    else:
        s.add(a)
print('pairwise coprime')

Submission status: Runtime Error

Solution code:
from collections import defaultdict
import math

def f(n):
    yakusu = []
    for i in range(1, int(n ** 0.5) + 1):
        if n % i == 0:
            yakusu.append(i)
            if i != n // i:
                yakusu.append(n // i)
    for i in yakusu:
        if i != 1:
            d[i] += 1

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

tmp = A[0]
for i in range(1, N):
    tmp = math.gcd(tmp, A[i])
if tmp != 1:
    print('not coprime')
    exit()

for i in A:
    f(i)

d = sorted(d.values(), reverse=True)
if d[0] != 1:
    print('setwise coprime')
else:
    print('pairwise coprime')

Submission status: Runtime Error

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 = sorted(LIST())

primes = set(range(2, a[-1]+1))
for i in range(2, int(a[-1]**0.5+1)):
    primes.difference_update(range(i*2, a[-1]+1, i))
primes=list(primes)

b = defaultdict(int)
for x in a:
    for y in primes:
        if y > x:
            break
        else:
            if x % y == 0:
                b[y] += 1

if max(b.values()) == 1:
    print("pairwise coprime")
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: Runtime Error

Solution code:
ma = lambda :map(int,input().split())
lma = lambda :list(map(int,input().split()))
tma = lambda :tuple(map(int,input().split()))
ni = lambda:int(input())
yn = lambda fl:print("Yes") if fl else print("No")
import collections
import math
def is_primes(n):
    primes = [1]*n
    primes[0] =0
    primes[1] =0
    for i in range(2,int(n**0.5)+1):
        if primes[i] ==1:
            for j in range(2*i,n,i):
                primes[j] = 0
    return primes

def factorize(n,prms):

    fct = []
    idx=0
    b = prms[idx]
    while b * b <= n :
        cnt =0
        while n % b == 0:
            n //= b
            cnt +=1
        if cnt >=1:
            fct.append((b,cnt))
        idx+=1
        if idx>=len(prms):break
        b = prms[idx]
    if n > 1:
        fct.append((n,1))
    return fct

n =ni()
A = lma()
mx= max(A)
prms = is_primes(mx+1)
prms2 = [i for i in range(mx+1) if prms[i]==1]
#print(prms,prms2)
d=collections.Counter()
for a in A:
    fct = factorize(a,prms2)
    #print(fct)
    for fc,cnt in fct:
        d[fc]+=1
        if d[fc]==n:
            break
f1=True # pp or sp
f2=True # sp or other
for num,cnt in d.items():
    if cnt==n:
        f2=False #other
        break
    else:
        if cnt==1:
            pass
        else:
            f1=False
            break
if f2==False:
    print("not coprime")
elif f1 and f2:
    print("pairwise coprime")
elif f1==False:
    print("setwise coprime")

Submission status: Runtime Error

Solution code:
n = int(input())
A = tuple(map(int, input().split()))
def p(n):
    is_prime = [True if i%2 == 1 else False for i in range(0, n+1) ]
    is_prime[0] = False
    is_prime[1] = False
    is_prime[2] = True # 2は素数
    # 3からの奇数について
    for i in range(3, int(n**0.5) + 1, 2):
        # 既に素数の倍数であればスキップ
        if not is_prime[i]:
            continue
        # iの倍数は素数ではないとする
        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]]

primes = p(max(A))
fact_counts = dict()
for a in A:
    for p in primes:
        if p > a:
            continue
        if a%p == 0:
            fact_counts.setdefault(p, 0)
            fact_counts[p] += 1
pairwise = True
for c in fact_counts.values():
    if c > 1:
        pairwise = False
        break

if pairwise:
    print('pairwise coprime')
else:
    if max(fact_counts.values()) == n:
        print('not coprime')
    else:
        print('setwise coprime')

Submission status: Runtime Error

Solution code:
n=int(input())
A=set(map(int,input().split()))
ma=max(A)
data=[i for i in range(2,ma+1)]
pco=True
sco=True
while len(d)>1:
  d=data[0]
  if d>ma**0.5:break
  one=d in A
  new=[]
  if one:k=1
  else:k=0
  for e in data[1:]:
    if e%d==0:
      k+=1
      if e in A:
        if one:pco=False
        else:one=True
    else:
      new.append(e)
  if k==n:
    sco=False
    break
  data=new
if pco:
  print('pairwise coprime')
elif sco:
  print('setwise coprime')
else:
  print('not coprime')

Submission status: Runtime Error

Solution code:
ma = lambda :map(int,input().split())
lma = lambda :list(map(int,input().split()))
tma = lambda :tuple(map(int,input().split()))
ni = lambda:int(input())
yn = lambda fl:print("Yes") if fl else print("No")
import collections
import math
def is_primes(n):
    primes = [1]*n
    primes[0] =0
    primes[1] =0
    for i in range(2,int(n**0.5)+1):
        if primes[i] ==1:
            for j in range(2*i,n,i):
                primes[j] = 0
    return primes

def factorize(n,prms):

    fct = []
    idx=0
    b = prms[idx]
    while b * b <= n:
        cnt =0
        while n % b == 0:
            n //= b
            cnt +=1
        if cnt >=1:
            fct.append((b,cnt))
        idx+=1
        b = prms[idx]
    if n > 1:
        fct.append((n,1))
    return fct

n =ni()
A = lma()
mx= max(A)
prms = is_primes(mx+1)
prms2 = [i for i in range(mx+1) if prms[i]==1]
#print(prms,prms2)
d=collections.Counter()
for a in A:
    fct = factorize(a,prms2)
    #print(fct)
    for fc,cnt in fct:
        d[fc]+=1
        if d[fc]==n:
            break
f1=True # pp or sp
f2=True # sp or other
for num,cnt in d.items():
    if cnt==n:
        f2=False #other
        break
    else:
        if cnt==1:
            pass
        else:
            f1=False
            break
if f2==False:
    print("not coprime")
elif f1 and f2:
    print("pairwise coprime")
elif f1==False:
    print("setwise coprime")

Submission status: Runtime Error

Solution code:
def fast_prime_factorization_many(lst):
    # 素因数分解（ロー法、複数）
    from subprocess import Popen, PIPE
    res = Popen(["factor"] + list(map(str, lst)), stdout=PIPE).communicate()[0].split(b"\n")[:-1]
    return [set(list(map(int, r.split()[1:]))) for r in res]

def main():
    import sys
    input = sys.stdin.readline
    N = int(input())
    A = list(map(int, input().split()))

    Factors = fast_prime_factorization_many(A)
    fset = set(Factors[0])
    fcommon = set(Factors[0])
    eleflg = True
    for f in Factors[1:]:
      fcommon = fcommon & f
      if len(fset & f) == 0:
        fset = fset | f
      else:
        eleflg = False
        # 互いに素でないペアがいる
        pass
    if len(fcommon) > 0:
      print("not coprime")
    elif eleflg:
      print("pairwise coprime")
    else:
      print("setwise coprime")
    #print(fcommon)
    exit(0)

main()

Submission status: Runtime Error

Solution code:
def resolve():
    n=int(input())
    a = list(map(int, input().split()))
    seki=1
    import math
    from functools import reduce

    def gcd(*numbers):
        return math.gcd(*numbers)

    for i in a:
      seki*=i

    c=seki
    ch=0

    for i in range(n-1):
        seki=int(seki/a[i])
        gc=gcd(a[i], seki)
        if gc!=1:
            c=gcd(c,gc)
            ch+=1

    if ch==0:
        print("pairwise coprime")
    elif c==1:
        print("setwise coprime")
    else:
        print("not coprime")
resolve()

Submission status: Runtime Error

Solution code:
N = int(input())
A = [int(s) for s in input().split()]

PRIME_LENGTH = 10**6

prime_list = [[] for _ in range(PRIME_LENGTH)]

for i in range(2, PRIME_LENGTH):
    if not prime_list[i]:
        idx = i
        while (idx < PRIME_LENGTH):
            prime_list[idx].append(i)
            idx += i

vote = [0] * (PRIME_LENGTH)

for a in A:
    for v in prime_list[a]:
        vote[v] += 1

if max(vote) == len(A):
    print("not coprime")
elif sum(map(lambda x: x > 1, vote)) > 0:
    print("setwise coprime")
else:
    print("pairwise coprime")