leaf さんや kyopro_friends さんは 2-SAT の形を工夫することで計算量を減らしているように見受けられますが、ここでは 2-SAT 内部の SCC のやり方を工夫することで計算量を落とします。

まず始めに、愚直な 2-SAT を構築してみましょう。

ある添字の組 \((i,j)\ (i \neq j)\) について、

• \(A_i\) と \(A_j\) が互いに素でなく、かつ \(A_i\) が表を向いている場合 \(A_j\) が表を向いていてはいけない。即ち、\(B_j\) が表を向いている必要がある。
• \(A_i\) と \(B_j\) が互いに素でなく、かつ \(A_i\) が表を向いている場合 \(B_j\) が表を向いていてはいけない。即ち、\(A_j\) が表を向いている必要がある。
• \(B_i\) と \(A_j\) が互いに素でなく、かつ \(B_i\) が表を向いている場合 \(A_j\) が表を向いていてはいけない。即ち、\(B_j\) が表を向いている必要がある。
• \(B_i\) と \(B_j\) が互いに素でなく、かつ \(B_i\) が表を向いている場合 \(B_j\) が表を向いていてはいけない。即ち、\(A_j\) が表を向いている必要がある。

という構図が成り立ちます。

よって各頂点が \(A_i,B_i\) に対応した \(2N\) 頂点のグラフを用意し、

• \(A_i\) と \(A_j\) が互いに素でないなら \(A_i\) から \(B_j\) に辺を張る
• \(A_i\) と \(B_j\) が互いに素でないなら \(A_i\) から \(A_j\) に辺を張る
• \(B_i\) と \(A_j\) が互いに素でないなら \(B_i\) から \(B_j\) に辺を張る
• \(B_i\) と \(B_j\) が互いに素でないなら \(B_i\) から \(A_j\) に辺を張る

という操作を行った上で SCC を行い、全ての \(i\) について \(A_i\) と \(B_i\) が同じ強連結成分に属していないことを確認すればよいです。

愚直にグラフを構築した上で SCC をすると辺数が \(O(N^2)\) となり実行時間制限に間に合いませんが、ここで SCC がどのように行われるかに思いを馳せてみましょう。

SCC は、以下の \(2\) ステップからなります。

• ステップ1: 適当な頂点から dfs を行い、帰りがけ順に添え字を振る。
• ステップ2: 上記の操作によって振られた添字の降順に、各辺の向きを逆にしたグラフ上で bfs を行う。

この \(2\) ステップそれぞれについて、以下のことを行います。

• 任意の素数 \(p\) に対して \(\text{remain}[p]:=(p\) を素因数に持つ頂点のうち、未訪問であるものの集合\()\) をメモしながら dfs/bfs を行う。その上である頂点 \(A_x/B_x\) を初めて訪れた際、次のことを行う。
  • \(A_x/B_x\) の各素因数 \(d\) について、\(\text{remain}[d]\) に含まれていてかつ \(x \neq y\) を満たすような全ての頂点 \(A_y/B_y\) に遷移する

これをすることで訪問済みの頂点を複数回訪れることがなくなり、結果として \(O(N \log \max (A))\) や \(O(N \log \max (A) \log (N \log \max (A)))\) (後者は \(\text{remain}\) の管理に std::set 等を用いた場合の計算量) で SCC を行うことができます。

実装例 (C++)