\(M=\max(A)\) と置きます。

このような問題では黒板に残っている数を持つ bit DP が解法としてまず考えられますが、 \(N=2 \times 10^5\) のときなどは当然TLに間に合いません。黒板に残っている数の集合としてありうるものを全走査せずにすむ解法を考えましょう。

重要なこととして、ある \(A_i\) に対し \(1 < \gcd(A_i,\ G) < G\) が成り立つとき、\(A_i\) は必ず黒板に残っています。このため、 \(G\) を小さくするような操作のみを考える場合は、黒板に残っている数の集合のことを考える必要はありません。

こうなると問題になりそうなのは \(2\) 人とも \(G\) が変化しないような操作をするのが最適になる状況です。しかし、そのような状況では \(2\) 人は \(G\) の倍数をなくなるまで選び続けるので、初めに黒板に書かれていた \(G\) の倍数の個数の偶奇からどちらが詰むか（ \(G\) を小さくするような操作をせざるを得なくなるか）がわかります。

以上の考察から、ある状況でどちらが勝者になるかは現在の \(G\) と現在の手番にしか依存しないことが予想できます。実際これは \(G\) に関する数学的帰納法から示すことができます。

よって

\(dp[g][p]:\) 現在の \(G\) が \(g\) であり手番が \(p\) のとき、どちらが勝利するか

という dp が定義でき、これを上記の考察に従って計算すればいいです。

計算の際には \(g\) の各約数 \(d\ (d\neq g)\) に対し \(\gcd(A_i, \ g)=d\) となる \(A_i\) が存在するかを判定したり、\(A_i\) のうち \(g\) の倍数の個数の偶奇を求める必要があります。まず後者については事前に個数を \(O(M\log M)\) で計算することができます。

前者については \(\gcd(A_i,\ g)=d\) となる \(A_i\) の個数を \(f_{g,d}\) と置きます。\(A_i\) が \(d\) の倍数のとき、\(\gcd(A_i,\ g)\) は \(d\) の倍数かつ \(g\) の約数になるので、\(d\) の倍数かつ \(g\) の約数であるような整数 \(d'\) に対する \(f_{g,d'}\) の総和は \(A_i\) のうち \(d\) の倍数の個数に等しくなります。よって \(f_{g, d}\) は \(d\) が大きいものから順に計算することができます。計算量ですが、結局探索しているのは \(3\) つ組 \((a,\ b,\ c)\ (1 \leq a \leq b \leq c \leq M)\) のうち \(b\) が \(a\) の倍数であり \(c\) が \(b\) の倍数であるものなので、これの個数を評価すればいいです。 \(A\) を固定すると \(b,\ c\) として考えられるのは \(O(\frac{M}{A}\log{\frac{M}{A}})\) 個なので、\(3\) つ組の個数は \(O(M\log^2 M)\) 個と評価できます。

以上よりこの問題は \(O(N+M\log^2 M)\) の計算量で解くことができ、十分高速です。