Background

This problem is an enhanced version of SPOJ PYTRIP3.

Problem Description

Given a positive integer $N$. Find the number of distinct right triangles whose hypotenuse length is at most $N$, and whose three side lengths are all integers.

Input Format

One line containing one positive integer $N$.

Output Format

One line containing one non-negative integer, representing the answer.

1000000000000

4179478903392

Hint

For all testdata, $1\le N\le 31415926535897\approx 3.14\times 10^{13}$.

The time limit is about $1.5$ times the running time of the standard solution on the slowest case.

Translated by ChatGPT 5