AT_abc342_d.[ABC342D] Square Pair

给定一个长度为 $N$ 的非负整数序列 $A=(A_1,\ldots,A_N)$。请你计算满足以下条件的整数对 $(i,j)$ 的个数。

• $1\leq i < j \leq N$
• $A_i A_j$ 是一个平方数

这里，非负整数 $a$ 如果存在非负整数 $d$ 使得 $a=d^2$，则称 $a$ 为平方数。

输入以以下格式从标准输入读入。

$N$ $A_1$ $A_2$ $\ldots$ $A_N$

请输出答案。

限制条件

• 输入均为整数。
• $2\leq N\leq 2\times 10^5$
• $0\leq A_i\leq 2\times 10^5$

样例解释 1

满足条件的整数对为 $(i,j)=(1,2),(1,3),(1,4),(1,5),(2,5),(3,4)$，共 $6$ 个。例如，$A_2A_5=36$，$36$ 是平方数，因此 $(i,j)=(2,5)$ 满足条件。

由 ChatGPT 4.1 翻译