This algorithm requires the knowledge of Grundy number. If you do not know it, refer to the editorial for ABC255-G or articles on the internet.

Let us observe the operation to find the Grundy number for each \(i\). Replacing \(A_i\) with a positive divisor of \(A_i\) other than itself means reducing one or more prime factors of \(1\) including duplicates.

Let \(x_i\) be the number of prime factors of \(A_i\), counting duplicates. After all, the game in this problem is such that there are \(x_i\) stones in the \(i\)-th pile, and players take turns to pick one or more stones from a pile until the one who is unable to make a move loses. This is nothing but Nim, and the Grundy number of \(A_i\) is \(x_i\).

With Eratosthenes’s thieve, we can obtain an algorithm that runs in \(O(N + T \log \log T)\) time, where \(T\) is the maximum value of \(A\). Even the \(O(N \sqrt T)\) algorithm that does prime factorization naively is fast enough.