AT_abc368_f [ABC368F] Dividing Game

[problemUrl]: https://atcoder.jp/contests/abc368/tasks/abc368_f 各要素が $ 2 $ 以上である長さ $ N $ の正整数列 $ A\ =\ (A_1,\ A_2,\ \dots\ ,A_N) $ が与えられます。Anna と Bruno はこれらの整数を用いてゲームをします。二人は、 Anna を先手として交互に以下の操作を行います。 - 整数 $ i\ (1\ \leq\ i\ \leq\ N) $ を自由に選ぶ。$ A_i $ の正の約数であって $ A_i $ 自身でないものを自由に選び $ x $ とし、 $ A_i $ を $ x $ で置き換える。 操作が行えなくなった方が負けで、負けなかった方が勝ちです。両者が勝ちを目指して最適な行動を取るとき、どちらが勝つか判定してください。

N/A

N/A

### 制約 - $ 1\ \leq\ N\ \leq\ 10^5 $ - $ 2\ \leq\ A_i\ \leq\ 10^5 $ - 入力はすべて整数 ### Sample Explanation 1 例えば、ゲームの進行として以下のようなものが考えられます。必ずしも両者が最適な行動を取った例とは限らないことに注意してください。 - Anna が $ A_3 $ を $ 2 $ にする。 - Bruno が $ A_1 $ を $ 1 $ にする。 - Anna が $ A_2 $ を $ 1 $ にする。 - Bruno が $ A_3 $ を $ 1 $ にする。 - Anna のターンで操作ができないので Bruno の勝ちとなる。 実際には、このサンプルでは Anna が最適に行動すると常に Anna が勝つことができます。