제곱수 만들기

면접 대비

시간 제한2초메모리 제한512 MB

요약

서로 다른 양의 정수 n개가 주어질 때, a_i^2 + a_j가 완전제곱수가 되는 순서쌍 (i, j)의 개수를 센다.

문제

서로 다른 $n$ 개의 양의 정수로 이루어진 배열 $a$ 가 주어진다. $1 \le i, j \le n$ 이고 $a_i^2 + a_j$ 가 정수의 제곱인 순서쌍 $(i, j)$ 의 개수를 구하시오.

첫째 줄에 배열의 크기 $n$ 이 주어진다 ( $1 \le n \le 10^6$ ).

둘째 줄에 서로 다른 $n$ 개의 양의 정수 $a_1, \ldots, a_n$ 이 주어진다 ( $1 \le a_i \le 10^6$ ).

문제의 답을 정수 하나로 출력한다.

예시에는 $1^2 + 3 = 4 = 2^2$ 과 $2^2 + 5 = 9 = 3^2$ 에 해당하는 두 순서쌍이 있다.