pairwise coprimeであるかどうか判定するために、定義通りに \(O(N^2)\) 個のペアについてGCDを計算するとTLEになります。

pairwise coprimeであることの条件は「任意の素数 \(p\) について、\(\{A_i\}\) の中に \(p\) の倍数は高々1個である」と同値です （ もし \(A_i\) と \(A_j\) がともに \(p\) の倍数なら、\(GCD(A_i,A_j)\) は \(p\) の倍数となるので、\(\{A_i\}\) はpairwise coprimeではありません。逆に、\(\{A_i\}\) がpairwise coprimeでないなら、\(GCD(A_i,A_j) > 1\) となる \(A_i,A_j\) は、ともに \(GCD(A_i,A_j)\) の素因数 \(p\) の倍数です）。

したがって、\(A_i\) たちを素因数分解し、素因子に重複があるかどうかを調べればよいです。このためには各 \(A_i\) を高速に素因数分解できればよく、以下に述べる方法により、\(A=\max\{A_i\}\) として \(O(A\log\log A+N\log A)\) で行うことができます。

setwise coprimeであるかどうかの判定は、GCDを計算するだけなので容易です。以上により全体で \(O(A\log\log A + N\log A)\) で解けました。なおこの解法は適切な実装により \(O(N+A)\) になります。

高速素因数分解

問題： \(A\) 以下の数が \(N\) 個与えられる。全て素因数分解せよ。

前計算としてエラトステネスの篩を行い、「その数をふるい落とした素数」を配列 \(D\) に記録します。例えば \(D[4]=D[6]=2,D[35]=5\) です。\(x\) が素数のときは \(D[x]=x\) としておきます。この配列はエラトステネスの篩と同様 \(O(A\log\log A)\) で構築できます。

\(D[x]\) は \(x\) を割り切る最小の素数なので、この配列 \(D\) を利用すると素因数分解を行うときに「試し割り」をする必要がなくなり(\(D[x]\)で割ればよい)、1つの数の素因数分解が素因数の個数である \(O(\log A)\) でできるようになります。