题目描述

给定一个长度为 $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$

输出格式

请输出答案。

样例 1

输入

5
0 3 2 8 12

输出

6

样例 2

输入

8
2 2 4 6 3 100 100 25

输出

7

说明/提示

限制条件

• 输入均为整数。
• $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 翻译