#G1033. [GESP202403 三级] 完全平方数

[GESP202403 三级] 完全平方数

[GESP202403 三级] 完全平方数

题目描述

小杨同学有一个包含 nn 个非负整数的序列 AA,他想要知道其中有多少对下标组合 <i,j><i, j>(1≤i,j≤n1 ≤ i, j ≤ n,i<ji < j),使得 Ai+AjA_i + A_j 是完全平方数。

如果 xx 是完全平方数,则存在非负整数 yy 使得 y×y=xy \times y = x。

输入格式

第一行一个非负整数 nn,表示非负整数个数。

第二行包含 nn 个非负整数 A1,A2,…,AnA_1, A_2, \dots, A_n,表示序列 AA 包含的非负整数。

输出格式

输出一个非负整数,表示和是完全平方数的非负整数对数。

样例 #1

样例输入 #1

5
1 4 3 3 5

样例输出 #1

3

数据范围

  • 对于全部数据,保证有 1≤n≤10001 ≤ n ≤ 1000,0≤Ai≤1050 ≤ A_i ≤ 10^5。