E - Coprime Editorial by kyopro_friends


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)$ でできるようになります。

posted:
last update: