#N. 完全平方数

传统题

1000ms

256MiB

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

小杨同学有一个包含 $n$ 个非负整数的序列 $A$ ，他想要知道其中有多少对下标组合 $<i,j>$ （ $1 \leq i < j \leq n$ ），使得 $A_i + A_j$ 是完全平方数。

如果 $x$ 是完全平方数，则存在非负整数 $y$ 使得 $y \times y = x$ 。

第一行一个非负整数 $n$ ，表示非负整数个数。
第二入行包含 $n$ 个非负整数 $A_1, A_2, \dots A_n$ ，表示序列 $A$ 包含的非负整数。

输出一行一个整数表示答案。

5
1 4 3 3 5

对于 $70\%$ 的数据，保证 $1 \leq n \leq 1000$ ， $0 \leq A_i \leq 10^5$ 。

对于 $100\%$ 的数据，保证 $1 \leq n \leq 10^5$ ， $0 \leq A_i \leq 10^5$ 。