分数: 400 点
问题陈述
给你一个非负整数序列 A=(A_1,\ldots,A_N) 长度 N。查找整数对的数量 (i,j) 满足以下两个条件:
- 1\leq i < j\leq N
- A_i A_j 是一个平方数。
这里,一个非负整数 当 a 可以表示为时,称为平方数 a=d^2 使用一些非负整数 d.
约束
- 所有输入均为整数。
- 2\leq N\leq 2\times 10^5
- 0\leq A_i\leq 2\times 10^5
输入
输入由标准输入按以下格式给出:
N A_1 \ldots A_N
输出
打印答案。
示例输入 1
5 0 3 2 8 12
示例输出 1
6
六对整数, (i,j)=(1,2),(1,3),(1,4),(1,5),(2,5),(3,4),满足条件。
例如, A_2A_5=36,和 36 是一个平方数,所以这对 (i,j)=(2,5) 满足条件。
示例输入 2
8 2 2 4 6 3 100 100 25
示例输出 2
7