Coprime Solitaire

现在很晚了，但是这个神必题卡了我真的好久好久。。。。。(before noi until present).........

（你可以通过我被这个SB题卡发现我真是个菜B)

题意

题解

显然 naive 的连边，如果 \(\gcd(a_i,a_j)\),\(a_i \rightarrow b_j\) 那么如果选 \(a_i\) 必须不能选 \(a_j\) ,显然应该选 \(b_j\) 。剩下3种情况同理。

做 2-sat 就好。

但显然 \(n^2\) 条边，傻了。

那么你发现如果 \(\gcd(a,b)\) \(P_a\) 交 \(P_b\) 不为空集。

那就可以新建节点 \(f_p\) 表示 如果当 \(p\mid a\) 应该向prefix全连边的点。

很好更新，记录 prefix,suffix 就没了。

被这个东西卡我是真傻逼。

明天开始好好学了！！！！！！！！！！！！！！！！！！！！！！！！！！！！！