题很简单，但个人感觉很有启发性。
首先令 \(f(i)=(p_1,p_2,\cdots)\) 代表将 \(i\) 质因数分解后的结果为 \(2^{p_1}+3^{p_2}+5^{p_3}+\cdots\)。
当一个数是平方数时，一定满足 \(2|p_i\)，此时它是 \((\frac{p_1}{2},\frac{p_2}{2},\cdots)\) 的平方。
我们要找到 \(i,j\) 使得 \(k=ij\) 为平方数，显然，\(f(k)=f(i)+f(j)=(p_{i,1}+p_{j,1},p_{i,2}+p_{j,2},\cdots)\)。
对于固定的 \(i\)，设 \(g(i)=(q_1,q_2,\cdots)\) 代表在 \(f(i)\) 中不满足 \(2|p_i\) 的第 \(i\) 个质数。
我们要找的 \(j\) 必须满足 \(g(i)=g(j)\)，请自证。
由于唯一分解定理，当且仅当 \(\prod q_{i,k}=\prod q_{j,k}\) 时 \(g(i)=g(j)\)。
考虑如何快速求出 \(\prod g(i,j)\)。
根据唯一分解定理，设 \(i\) 可以被整除的最大平方数为 \(d\)，则 \(\prod g(i,j)=\frac{i}{d}\)，不难理解，请自证。
预处理出所有 \(d\) 即可。
