피타고라스의 정리

시간 제한1초메모리 제한128 MB

요약

정수 n이 주어질 때 1 이상 n-1 이하이고 a≤b인 순서쌍 (a,b,c) 중 a^2+b^2≡c^2 (mod n)을 만족하는 개수를 구한다.

문제

상근이는 삼각형을, 그중에서도 직각삼각형을 매우 좋아한다.

직각삼각형은 세 변의 길이가 양의 정수 $a$ , $b$ , $c$ 이고 $a \le b$ 이며 $a^2 + b^2 = c^2$ 을 만족하는 삼각형이다.

나머지 연산을 배운 상근이는 피타고라스의 정리에 나머지 연산을 적용해 보기로 했다.

정수 $n$ 이 주어질 때, $1 \le a, b, c \le n-1$ 이고 $a \le b$ 이며

$a^2 + b^2 \equiv c^2 \pmod{n}$

을 만족하는 순서쌍 $(a, b, c)$ 의 개수를 세려고 한다.

$n$ 이 주어졌을 때, 조건을 만족하는 $(a, b, c)$ 의 개수를 구하는 프로그램을 작성하시오.

첫째 줄에 정수 $n$ 이 주어진다. ( $2 \le n \le 500{,}000$ )

첫째 줄에 조건을 만족하는 순서쌍 $(a, b, c)$ 의 개수를 출력한다.