\(A_i,A_j\) のいずれかが \(0\) の場合は明らかに条件を満たします。以下、\(A_i,A_j\) が共に正の場合を考えましょう。

整数 \(x\) について、\(x\) を割り切る最大の平方数を \(d_x\) とします。このとき、\(A_xA_y\) が平方数であることと、\(\displaystyle \frac{A_x}{d_{A_x}}\frac{A_y}{d_{A_y}}\) が平方数であることは同値です。更に、これは \(\displaystyle \frac{A_x}{d_{A_x}}=\frac{A_y}{d_{A_y}}\) と同値であることが簡単に示せます。

つまり、各 \(A_i\) について \(d_{A_i}\) を求めればこの問題を解くことが出来ます。

\(d_{A_i}\) の候補が \(\mathrm{O}(\sqrt{A_i})\) であることから、全てを試しても、この問題を \(\mathrm{O}(N\sqrt{A_i})\) で解くことが出来ました。