시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 (추가 시간 없음) 512 MB 173 57 18 21.176%

문제

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

a = m2 - n2
b = 2mn
c = m2 + n2

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

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

입력

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

출력

정답을 출력합니다.

예제 입력 1

4

예제 출력 1

4

노트

다음과 같이 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)