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:
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 = {}
    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:return {n} 
    return set(ret)
def main():
    n=int(input())
    a=list(map(int,input().split()))
    g=a[0]
    for i in a[1:]:g=gcd(g,i)
    if g!=1:
        print("not coprime")
        exit()
    ans=0
    s=set()
    for i in a:
        p=primeFactor(i)
        ans+=len(p)
        s|=p
    if ans!=len(s):print("setwise coprime")
    else:print("pairwise coprime")
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import math

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

def func():
    D = [x if x % 2 != 0 else 2 for x in range(Amax+1)]
    for i in range(3, Amax+1, 2):
        if i**2 > Amax:
            break
        elif D[i] != i:
            continue
        else:
            j = i
            while j < Amax:
                if D[j] == j:
                    D[j] = i
                j += i
    return D

GCD = A[0]
for i in range(1, N):
    GCD = math.gcd(GCD, A[i])

if GCD > 1:
    print('not coprime')
else:
    D = func()
    pri = [0] * (Amax+1)
    for i in range(N):
        x, pri_set = A[i], set()
        while x != 1:
            pri_set.add(D[x])
            x //= D[x]
        for y in pri_set:
            if pri[y] > 0:
                print('setwise coprime')
                exit()
            else:
                pri[y] += 1

    print('pairwise coprime')
    while True:
        D = 1

Submission status: Time Limit Exceeded

Solution code:
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 = {}
    while i*i <= n:
        k = 0
        while n % i == 0:
            n //= i
            k += 1
        if k: ret[i] = k
        i += 1 + i % 2
    if n > 1:return {n} 
    return set(ret)
def main():
    n=int(input())
    a=list(map(int,input().split()))
    g=a[0]
    for i in a[1:]:g=gcd(g,i)
    if g!=1:
        print("not coprime")
        exit()
    ans=0
    s=set()
    for i in a:
        p=primeFactor(i)
        ans+=len(p)
        s|=p
    if ans!=len(s):print("setwise coprime")
    else:print("pairwise coprime")
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
sys = sys.stdin.buffer.readline
N = int(input())
A = np.array(list(map(int, input().split())))


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


v = A[0]
for a in A:
    v = gcd(v, a)

for d in range(2, max(A)):
    if np.count_nonzero(A % d == 0) >= 2:
        if v == 1:
            print('setwise coprime')
        else:
            print('not coprime')
        exit()
print('pairwise coprime')

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from numba import njit
def main():
    N = int(input())
    nlist = np.array(list(map(int, input().split())))

    def gdc(x, y):
        b = max(x, y)
        s = min(x, y)
        r = b % s
        if r == 0:
            return s
        else:
            return gdc(s, r)

    scp = False
    pcp = False

    sgdc = nlist[0]
    for n in nlist:
        sgdc = gdc(sgdc, n)
        if sgdc == 1:
            scp = True

    if not scp:
        print('not coprime')
        exit()

    pcheckl = np.full((10**6+1), 0)
    for n in nlist:
        pcheckl[n] = 1

    pcp = np.all([sum(pcheckl[i::i]) <= 1 for i in range(2, 10**6+1)])

    if pcp:
        print('pairwise coprime')
    elif scp:
        print('setwise coprime')

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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


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


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

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


def 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 not input_list[serial]:
            continue

        if serial >= sqrt:
            return input_list

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


def main():
    N = NI()
    A = NLI()
    ela = sieve_of_erastosthenes(1000001)
    ela2 = [i for i, b in enumerate(ela) if b]

    if max(A) == 1:
        print("pairwise coprime")
        exit()


    p_cnt = defaultdict(int)
    PD_list = defaultdict(dict)
    cnt = 0
    for a in A:
        if a == 1:
            continue
        
        cnt += 1
        if cnt >= 90000:
            print("not coprime")
            exit()

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

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



if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import math
from functools import reduce
from collections import defaultdict


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


def lcm(x, y):
    return (x * y) // math.gcd(x, y)


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

    is_pairwise_coprime = True

    D = [-1] * (A_max + 1)
    for i in range(2, A_max + 1):
        if D[i] == -1:
            D[i] = i
            p = 2
            while i * p <= A_max:
                D[i * p] = i
                p += 1

    def factorization(n):
        # assert 0 < n <= A_max
        primes_ = defaultdict(int)
        temp = n
        while temp > 1:
            primes_[D[temp]] += 1
            temp = temp // D[temp]

        return primes_
    
    P = [False]*(A_max+1)

    # primes = set({})
    for i in range(N):
        for p in factorization(A[i]).keys():
            # if p in primes:
            if P[p]:
                is_pairwise_coprime = False
                break
            else:
                # primes.add(p)
                P[p] = True

    gcd_ = reduce(math.gcd, A)

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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import math
N = int(input())
A = list(map(int, input().split()))
def factorize(n):
    i = 2
    factors = set()
    while i**2 <= n:
        if n % i != 0:
            i += 1
            continue

        while n % i == 0:
            n = n // i
            factors.add(i)
        i += 1

    if n != 1:
        factors.add(n)

    return factors

isSetWise = False
gcd = A[0]
for i in range(1, N):
    gcd = math.gcd(gcd, A[i])
if gcd == 1:
    isSetWise = True

isPairWise = True
g = factorize(A[0])
for i in range(1, N):
    f = factorize(A[i])

    if not g.isdisjoint(f):
        isPairWise = False
        break
    g = g | f

if isPairWise:
    print("pairwise coprime")
    exit()

if isSetWise:
    print("setwise coprime")
    exit()

print("not coprime")

Submission status: Time Limit Exceeded

Solution code:
import math
from functools import reduce
from collections import defaultdict


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


def lcm(x, y):
    return (x * y) // math.gcd(x, y)


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

    is_pairwise_coprime = True

    D = [-1] * (A_max + 1)
    for i in range(2, A_max + 1):
        if D[i] == -1:
            D[i] = i
            p = 2
            while i * p <= A_max:
                D[i * p] = i
                p += 1

    def factorization(n):
        # assert 0 < n <= A_max
        primes_ = defaultdict(int)
        temp = n
        while temp > 1:
            primes_[D[temp]] += 1
            temp = temp // D[temp]

        return primes_

    primes = set({})
    for i in range(N):
        for p in factorization(A[i]).keys():
            if p in primes:
                is_pairwise_coprime = False
                break
            else:
                primes.add(p)

    gcd_ = reduce(math.gcd, A)

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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import accumulate, permutations, combinations, product, groupby, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
A = LIST()

if reduce(gcd, A) != 1:
    print("not coprime")
    exit()
ma = max(A)
p = list(range(ma+1))
for x in range(2, int(ma ** 0.5) + 1):
    if p[x]:
        for i in range(x + x, ma+1, x):
            p[i] = x

s = [set() for _ in range(N)]

for i, x in enumerate(A):
    while x != 1:
        s[i].add(p[x])
        x //= p[x]

l = sum(len(x) for x in s)
merge = lambda x, y: x|y
print("pairwise coprime" if l == len(reduce(merge, s)) else "setwise coprime")

Submission status: Time Limit Exceeded

Solution code:
import math
from functools import reduce
from collections import defaultdict


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


def lcm(x, y):
    return (x * y) // math.gcd(x, y)


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

    is_pairwise_coprime = True

    D = [-1] * (A_max + 1)
    for i in range(2, A_max + 1):
        if D[i] == -1:
            D[i] = i
            p = 2
            while i * p <= A_max:
                D[i * p] = i
                p += 1

    def factorization(n):
        assert 0 < n <= A_max
        primes_ = defaultdict(int)
        temp = n
        while temp > 1:
            primes_[D[temp]] += 1
            temp = temp // D[temp]

        return primes_

    primes = set({})
    for i in range(N):
        for p in factorization(A[i]).keys():
            if p in primes:
                is_pairwise_coprime = False
                break
            else:
                primes.add(p)

    gcd_ = reduce(math.gcd, A)

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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    import math
    def primes(n):
        ass = []
        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
        for i in range(len(is_prime)):
            if is_prime[i]:
                ass.append(i)
        return ass

    def divisor(n):
        ass = []
        for i in range(1, int(n ** 0.5) + 1):
            if n % i == 0:
                if i != 1:
                    ass.append(i)
                if i ** 2 == n:
                    continue
                ass.append(n // i)
        return ass

    n = int(input())
    a = list(map(int, input().split()))
    a = list(set(a))
    pair = False
    divisors = set(divisor(a[0]))
    ggcd = a[0]
    for i in range(1, len(a)):
        divs = set(divisor(a[i]))
        if len(divs & divisors) != 0:
            pair = True
            break
        else:
            divisors = set(list(divisors) + list(divs))
    for i in range(1, len(a)):
        ggcd = math.gcd(ggcd, a[i])
        if ggcd == 1:
            break
    if ggcd != 1:
        print("not coprime")
    else:
        if pair:
            print("setwise coprime")
        else:
            print("pairwise coprime")
resolve()

Submission status: Time Limit Exceeded

Solution code:
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
        if k: ret[i] = k
        i += 1 + i % 2
    if n > 1: return {n}
    return set(ret)
def main():
  N=int(input())
  L=list(map(int,input().split()))
  gc=L[0]
  for i in L:
    gc=gcd(i,gc)
    if gc==1:
      break
  if gc!=1:
    print("not coprime")
    exit()
  ans=set()
  c=0
  for i in L:
    c+=len(primeFactor(i))
    ans|=set(primeFactor(i))
  if c==len(ans):
    print("pairwise coprime")
  else:
    print("setwise coprime")
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import math
from functools import reduce
from collections import defaultdict


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


def lcm(x, y):
    return (x * y) // math.gcd(x, y)


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

    is_pairwise_coprime = True

    D = [-1] * (A_max + 1)
    for i in range(2, A_max + 1):
        if D[i] == -1:
            D[i] = i
            p = 2
            while i * p <= A_max:
                D[i * p] = i
                p += 1

    def factorization(n):
        assert 0 < n <= A_max
        primes = defaultdict(int)
        temp = n
        while temp > 1:
            primes[D[temp]] += 1
            temp = temp // D[temp]

        return primes

    primes = set({})
    for i in range(N):
        for p in factorization(A[i]).keys():
            if p in primes:
                is_pairwise_coprime = False
                break
            else:
                primes.add(p)

    gcd_ = reduce(math.gcd, A)

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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N=int(input())
A=list(map(int,input().split()))
flag1=True
flag2=True
for i in range(N-1):
    for j in range(i+1,N):
        if np.gcd(A[i],A[j])!=1:
            flag1=False
            break
    else:
        continue
    break
if not flag1:
  if np.gcd.reduce(A)!=1:
    flag2=False
if flag1:
    print('pairwise coprime')
elif flag2:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Time Limit Exceeded

Solution code:
import 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(-(-i**0.5//1))+1):
    if tmp%j==0:
      while tmp%j==0:
        tmp//=j
      fc.append(j)
  if tmp!=1:
    fc.append(tmp)
  if fc==[]:
    fc.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")