시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 175 | 76 | 62 | 44.604% |
You are given an array $a$ of $n$ distinct positive integers. Find the number of pairs $(i, j)$ with $1 \le i, j \le n$ for which the number $a_i^2 + a_j$ is a square of an integer.
The first line of the input contains a single integer $n$ ($1 \le n \le 10^6$), the size of the array.
The second line of the input contains $n$ distinct positive integers $a_1, \ldots, a_n$ ($1 \le a_i \le 10^6$).
Output a single integer: the answer to the problem.
5 1 2 3 4 5
2
In the example, there are two such pairs, corresponding to $1^2 + 3 = 4 = 2^2$ and $2^2 + 5 = 9 = 3^2$.