← 返回题目列表

AtCoder · abc342_d

G. 方形对

中文机器翻译题面 查看原题

分数: 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