Calculating all the \(O(N^2)\) number of GCDs of pairs in accordance with the definition so as to check if they are pairwise coprime will lead to TLE.

The given numbers are pairwise coprime if and only if “for any prime \(p\), there are at most one multiple of \(p\) in \(A_i\)” ( If both \(A_i\) and \(A_j\) are multiples of \(p\), then \(GCD(A_i,A_j)\) will be a multiple of \(p\), so \(\{A_i\}\) will not be pairwise coprime. Conversely, if \(\{A_i\}\) is not pairwise coprime, then \(A_i,A_j\) such that \(GCD(A_i,A_j) > 1\) are both multiples of \(p\), a prime factor of \(GCD(A_i,A_j)\)).

Therefore, it is sufficient to factorize \(A_i\) and check if there are duplicates in their prime factors. All that left is to factorize each \(A_i\) fast, which can be achieved in a total of \(O(A\log\log A+N\log A)\) time, where \(A=\max\{A_i\}\), with the mehtod described below.

One can check with ease whether the given numbers are setwise coprime just by calculating the GCD. Therefore, this problem has been solved in a total of \(O(A\log\log A + N\log A)\) time. Note that this problem can be solved in a total of \(O(N+A)\) time with proper implementation.

Fast prime factorization

Question: You are given \(N\) integers less than or equal to \(A\). Factorize all of them into primes.

Compute Sieve of Eratosthenes as a precalculation, and record “the prime that sieved the number” to an array \(D\). Foe example, \(D[4]=D[6]=2\) and \(D[35]=5\). If \(x\) is a prime, let \(D[x]=x\). This array can be constructed in a total of \(O(A\log\log A)\), same as Sieve of Eratosthenes.

Since \(D[x]\) is the minimum prime that divides \(x\), so with this array, you no longer have to “try diving” when factorizing (instead you can just divide by \(D[x]\)), so the prime factorization of an integer can be achieved in an \(O(\log A)\) time, which is the number of prime factors.