PYTRIP3  Counting Pythagorean Triples
We define a Pythagorean triple as a set of three positive integers $a$, $b$ and $c$ which satisfy $a^2 + b^2 = c^2$.
Let $P(N)$ denote the number of Pythagorean triples whose hypotenuses ($= c$) are less than or equal to $N$ (i.e. $c \le N$).
Given $N$, find $P(N)$.
Input
The first line of input contains a positive integer $N$.
Output
Print on a single line the value of $P(N)$.
Constraints
$1 \le N \le 1234567891011$
Example
Input 1: 5 Output 1: 1
Input 2: 15 Output 2: 4
Input 3: 10000 Output 3: 12471
Input 4: 1000000000000 Output 4: 4179478903392
Explanation for Input 2
There are four Pythagorean triples: $\{3, 4, 5\}$, $\{5, 12, 13\}$, $\{6, 8, 10\}$, $\{9, 12, 15\}$
Information
There are 15 test cases.
The sum of the time limits is 93 sec. (My solution runs in 5.4 sec.)
Source Limit is 5 KB.
hide comments
cubyte:
20220807 14:59:26
I wanted to solve this problem one year ago,now I finally solve it.


nguyễn vãn lâm:
20160112 03:19:44
@francky sorry. i was wrong, the problem limited n = 10^4, and i solved it. but my solution cannot apply for above problem 

nguyễn vãn lâm:
20160108 08:57:18
oh. unbelievable, spoj world has only 2 people solve this problem. in vietnam, there are 45 people solved successfully. but i'm not in there!


Szegedi Gábor:
20141019 11:06:29
What faster way there is to generate all primitive triplets than using the Tree of primitive Pythagorean triples? 

wisfaq:
20141019 11:06:29
Nice problem!


Min_25:
20141019 11:06:29
@Francky


Francky:
20141019 11:06:29
My "brute force" program took 2h to check sample #4. I need a better approach ; I'll find it ! Thanks for that task. 
Added by:  Min_25 
Date:  20140526 
Time limit:  1s15s 
Source limit:  5120B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 GOSU 