平方数对

题目描述

给定长度为 $N$ 的非负整数序列 $A=(A_1,\ldots,A_N)$。求同时满足以下两个条件的整数对 $(i,j)$ 的个数：

• $1\le i \lt j\le N$
• $A_i A_j$ 是平方数。

这里,非负整数 $a$ 称为平方数,当且仅当存在某个非负整数 $d$,使得 $a=d^2$。

输入格式

输入按以下格式从标准输入给出：

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

输出格式

输出答案。

样例

5
0 3 2 8 12

6

有 6 对整数 $(i,j)=(1,2),(1,3),(1,4),(1,5),(2,5),(3,4)$ 满足条件。

例如,$A_2A_5=36$,而 $36$ 是平方数,所以数对 $(i,j)=(2,5)$ 满足条件。

8
2 2 4 6 3 100 100 25

7

数据范围

• 所有输入值均为整数。
• $2\le N\le 2\times 10^5$
• $0\le A_i\le 2\times 10^5$