ABC 342D

对于任意两个整数 $a,b$，有 $a^2\times b^2=(ab{)}^2$。即，两个平方数相乘仍为平方数。

拿到这道题我们很容易想到作唯一分解，一个数 $x=p_1^{{\alpha }_1}{p}_2^{{\alpha }_2}\cdots$ 不是平方数当且仅当 $\mathrm{\exists }{\alpha }_i$ 为奇数。联系到提示的内容，一个数的平方数因子是无用的，考虑令 $d_x$ 为满足 $d_x$ 为完全平方数且 $d_x\mid x$ 的最大值，则两个整数 $x$ 与 $y$ 相乘后的乘积为平方数当且仅当 ${\displaystyle \frac{x}{d_x}}={\displaystyle \frac{y}{d_y}}$，因此我们可以用 $\mathcal{O}(\sqrt{a_i})$ 的时间复杂度求出每个 $a_i$ 的 $d_{a_i}$，再使用 这道题 中的经典 trick 即可在 $\mathcal{O}(n\underset{i=1}{\overset{n}{max}}\sqrt{a_i})$ 的时间复杂度内解决问题。