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$。

输入格式

输入从标准输入按以下格式给出： $N$ $A_1$ $\ldots$ $A_N$

输出格式

输出答案。

5
0 3 2 8 12

6

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$共有六个整数对 $(i,j)=(1,2),(1,3),(1,4),(1,5),(2,5),(3,4)$ 满足条件。 例如，$A_2A_5=36$，而 $36$ 是完全平方数，所以 $(i,j)=(2,5)$ 这个对满足条件。

标签: AtCoder|abc342D

来源

AtCoder|abc342D