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: Wrong Answer

Solution code:
def isPrime(x :int):
    if(x == 1):
        return False

    for i in range(2, int(x**0.5)+1):
        if(x%i == 0):
            return False
    return True

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

from math import gcd
from  functools import reduce

flag = False

for i in range(n):
    if isPrime(L[i]):
        flag = True
        #print(flag)
    elif L[i] == 1:
        flag = True
    else:
        flag = False
        #print(L[i])
        break
a = reduce(gcd,L)


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

Submission status: Wrong Answer

Solution code:
def factorization(n):
    arr = []
    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.append([i, cnt])

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

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

import math
N = int(input())
A = list(map(int, input().split()))
ans = A[0]
primes = [x for (x, y) in factorization(A[0])]
flag = True
for i in range(1, N):
    if flag:
        for (p, _) in factorization(A[i]):
            if p not in primes:
                primes.append(p)
            else:
                flag = False
                break
    ans = math.gcd(ans, A[i])
if ans == 1:
    if flag:
        print("pairwise coprime")
    else:
        print("setwise coprime")
else:
    print("not coprime")

Submission status: Wrong Answer

Solution code:
from functools import reduce

def gcd(a, b):
    while b: a, b = b, a % b
    return a
def isPrimeMR(n):
    d = n - 1
    d = d // (d & -d)
    L = [2]
    for a in L:
        t = d
        y = pow(a, t, n)
        if y == 1: continue
        while y != n - 1:
            y = (y * y) % n
            if y == 1 or t == n - 1: return 0
            t <<= 1
    return 1
def findFactorRho(n):
    m = 1 << n.bit_length() // 8
    for c in range(1, 99):
        f = lambda x: (x * x + c) % n
        y, r, q, g = 2, 1, 1, 1
        while g == 1:
            x = y
            for i in range(r):
                y = f(y)
            k = 0
            while k < r and g == 1:
                ys = y
                for i in range(min(m, r - k)):
                    y = f(y)
                    q = q * abs(x - y) % n
                g = gcd(q, n)
                k += m
            r <<= 1
        if g == n:
            g = 1
            while g == 1:
                ys = f(ys)
                g = gcd(abs(x - ys), n)
        if g < n:
            if isPrimeMR(g): return g
            elif isPrimeMR(n // g): return n // g
            return findFactorRho(g)
def primeFactor(n):
    i = 2
    ret = {}
    rhoFlg = 0
    while i*i <= n:
        k = 0
        while n % i == 0:
            n //= i
            k += 1
        if k: ret[i] = k
        i += 1 + i % 2
        if i == 101 and n >= 2 ** 20:
            while n > 1:
                if isPrimeMR(n):
                    ret[n], n = 1, 1
                else:
                    rhoFlg = 1
                    j = findFactorRho(n)
                    k = 0
                    while n % j == 0:
                        n //= j
                        k += 1
                    ret[j] = k

    if n > 1: ret[n] = 1
    if rhoFlg: ret = {x: ret[x] for x in sorted(ret)}
    return ret
  
N=int(input())
*A,=map(int,input().split())

l = 0
for i in range(N):
  f = set(primeFactor(A[i]).keys())
  if i == 0:
    fset = f
    l += len(f)
    continue
  fset |= f
  l += len(f)
  
if l == len(fset):
  print('pairwise coprime')
  exit()
  
if reduce(gcd,A)==1:
  print('setwise coprime')
else:
  print('not coprimce')

Submission status: Wrong Answer

Solution code:
from functools import reduce
from itertools import combinations
from math import gcd


def func(A):
    is_A = [False] * (10**6+1)
    for a in A:
        is_A[a] = True
    if any(x > 1 for x in is_A[2:]):
        return False
    n = 0
    for i in range(2, 10**6+1, 2):
        if is_A[i]:
            n += 1
    if n > 1:
        return False
    for i in range(3, 10**6+1, 2):
        n = 0
        for j in range(i, 10**6+1, i):
            if is_A[j]:
                n += 1
        if n > 1:
            return False
    return True


def solve():
    N = int(input())
    A = list(map(int, input().split()))
    if func(A):
        # if not all(gcd(i, j)==1 for i, j in combinations(A, 2)):
        #     raise NameError
        print('pairwise coprime')
    elif reduce(gcd, A) == 1:
        print('setwise coprime')
    else:
        print('not coprime')
    

if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
import sys
import resource
from collections import defaultdict

s=set()
sys.setrecursionlimit(100000)

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

i,k=2,10**12
pri=set()
while k>=i*i:
    while k%i==0:
        k//=i
        pri.add(i)
    i+=1
if k!=1: pri.add(k)

n=int(input())
a=list(map(int,input().split()))
visi=set()
s=a[0]
flag=1
for i in a:
    s=gcd(s,i)
    for c in pri:
        if i%c==0:
            if c in visi:
                flag=0
                break
            visi.add(c)
if flag: print("pairwise coprime")
elif s==1: print("setwise coprime")
else: print("not coprime")

Submission status: Wrong Answer

Solution code:
import functools
import math

n=int(input())
values=list(map(int,input().split()))
#setgcd = functools.reduce(math.gcd, values)
values.sort()

flag=True

sqrtn=int(values[-1]**0.5+1)
prime = {i for i in range(2,sqrtn+1)}
for i in range(2,sqrtn+1):
    if i in prime:
        for j in range(i*2,sqrtn+1,i):
            if j in prime:
                prime.remove(j)

flag=True
flag2=True
for i in prime:
  cnt=0
  for j in values:
    if j%i==0:
      cnt+=1
      if cnt==2:
        flag=False
      if cnt==n:
        flag2=False

if flag:
  print("pairwise coprime")
elif flag2:
  print("setwise coprime")
else:
  print("not coprime")

Submission status: Wrong Answer

Solution code:
from math import gcd

def primes(n,als):
    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
        cnt = 0
        for j in range(i, n + 1, i):
            is_prime[j] = False
            if als[j]: cnt += 1
        if cnt >= 2:
            return False
    else:
        return True


def main():
    n = int(input())
    al = list(map(int, input().split()))
    als = [False]*(10**6+1)
    for a in al:
        if als[a]:
            break
        als[a] = True
    else:
        ans = primes(10**6,als)
        if ans: 
            print('pairwise coprime')
            exit()

    c_gcd = al[0]
    for a in al[1:]:
        c_gcd = gcd(c_gcd,a)
    
    if c_gcd == 1:
        print('setwise coprime')
    else:
        print('not coprime')


    # no_flag = False
    # for a in al:
    #     for p in ps:
    #         if a%p == 0:
    #             if p in pset:
    #                 no_flag = True
    #                 break
    #             else:
    #                 pset.add(p)
    #     if no_flag:
    #         break
    # else:
    #     print('pairwise coprime')
    #     exit()

    # pset = set()
    # for p in ps:
    #     if al[0]%p == 0:
    #         pset.add(p)

    # for a in al[1:]:
    #     apset = set()
    #     for p in ps:
    #         if a%p == 0:
    #             apset.add(p)
    #     pset = pset&apset
    #     if len(pset) == 0:
    #         print('setwise coprime')
    #         break
    # else:
    #     print('not coprime')



if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

def gcd_list(numbers):
    return reduce(gcd, numbers)
def lcm(x, y):
    return (x * y) // gcd(x, y)

N = int(input())
A = [int(i) for i in input().split()]

left = [0] * N
for i in range(1, N):
    left[i] = lcm(A[i - 1], left[i - 1])
right = [0] * N
for i in range(N - 2, -1, -1):
    right[i] = lcm(A[i + 1], right[i + 1])

flag = True
for a, l, r in zip(A, left, right):
    if gcd(l, a) != 1 and gcd(r, a) != 1:
        flag = False
        break

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

Submission status: Wrong Answer

Solution code:
from math import gcd
def findMaxGCD(arr, n) : 
    high = 0
    for i in range(0, n) : 
        high = max(high, arr[i])  
    count = [0] * (high + 1) 
    for i in range(0, n) : 
        count[arr[i]]+=1
    counter = 0
    for i in range(high, 0, -1) : 
        j = i 
        while (j <= high) : 
            if (count[j] >0) : 
                counter+=count[j]     
            j += i 
            if (counter == 2) : 
                return i 
        counter=0

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

if findMaxGCD(s, n) == 1:
    print("pairwise coprime")
else:
    ans = 0
    for c in s:
        ans  = gcd(ans, c)
    if ans ==1:
        print("setwise coprime")
    else:
        print("not coprime")

Submission status: Wrong Answer

Solution code:
def gcd(a,b):
  if b==0:
    return a
  else:
    return gcd(b,a%b)
n=int(input())
l=list(map(int,input().split())) 
c=0
for i in range(0,n):
  t=l[i%n]
  y=l[(i+1)%n]
  s=min(t,y)
  p=max(t,y)
  f=gcd(p,s)
  if f==1:
      c=c+1
r=0
z=0
if c==3:
    print('pairwise  coprime')
    z=1
else:
    f=l[0]
    y=l[1]
    a=max(f,y)
    b=min(f,y)
    r=gcd(a,b)
    for w in range(2,len(l)):
        r=gcd(r,l[w])
        if r!=1:
            print('not coprime')
            z=1
            break
if z==0:
  print('setwise coprime')

Submission status: Wrong Answer

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

from math import gcd

def main():
    n = int(input())
    A = list(map(int , input().split()))
    N = max(A)+1

    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


    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 or d > 10**2:
            break

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