If \(A_i\) or \(A_j\) is \(0\), then the conditions are obviously satisfied. What if \(A_i\) and \(A_j\) are both positive?

For an integer \(x\), let \(d_x\) be the maximum square number dividing \(d_x\). Then, \(A_xA_y\) is a square number if and only if \(\displaystyle \frac{A_x}{d_{A_x}}\frac{A_y}{d_{A_y}}\), which in turn is equivalent to \(\displaystyle \frac{A_x}{d_{A_x}}=\frac{A_y}{d_{A_y}}\) (this can be proved easily).

Therefore, if you obtain \(d_{A_i}\) for each \(A_i\), this problem can be solved.

Since there are \(\mathrm{O}(\sqrt{A_i})\) \(d_{A_i}\) candidates for \(d_{A_i}\), one can try all of them, and still solve it in \(\mathrm{O}(N\sqrt{A_i})\) time.