16123번 - 피타고라스 쌍

문제

피타고라스 쌍은 m > n인 1 이상의 자연수 m, n에 대해

a = m² - n²
b = 2mn
c = m² + n²

인 (a, b, c)를 말합니다. 이때 (a, b, c)는 (m, n)으로부터 생성되었다고 얘기합니다.

원시 피타고라스 쌍 (a, b, c)는 피타고라스 쌍이면서 gcd(a, b, c) = 1인 것입니다. 당신은 L이 주어졌을 때, n < m ≤ L인 (m, n)으로부터 생성된 원시 피타고라스 쌍의 개수를 구해야 합니다.

입력

첫째 줄에 5,000,000,000보다 작거나 같은 양의 정수 L이 주어집니다.

출력

정답을 출력합니다.

제한

노트

다음과 같이 4개 있습니다:

• (m, n) = (2, 1)인 경우 (a, b, c) = (3, 4, 5)
• (m, n) = (3, 2)인 경우 (a, b, c) = (5, 12, 13)
• (m, n) = (4, 3)인 경우 (a, b, c) = (7, 24, 25)
• (m, n) = (4, 1)인 경우 (a, b, c) = (15, 8, 17)