本解説では、 Grundy 数についての理解を前提とします。知らない方は、 ABC255-G の解説 やインターネット検索をご利用ください。

各 \(i\) についての Grundy 数を求めるために、操作を観察します。\(A_i\) を \(A_i\) 自身でない正の約数で置き換えるという操作は、言い換えると \(A_i\) の重複を含めた素因数を \(1\) つ以上減らす操作です。

\(A_i\) の重複を含めた素因数の個数を \(x_i\) とします。このゲームは結局、 \(i\) 番目の山には \(x_i\) 個の石があり、 \(1\) つ以上の石を取り除いて取り除けなくなった方が負けのゲームと考えてよいです。これは Nim そのもので、 \(A_i\) の Grundy 数は \(x_i\) です。

\(A\) の最大値を \(T\) とすると、エラトステネスの篩を用いることで時間計算量が \(O(N + T \log \log T)\) のアルゴリズムを得られます。愚直に素因数分解を行う \(O(N \sqrt T)\) のアルゴリズムでも十分高速です。