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:
2022-08-07 14:59:26
I wanted to solve this problem one year ago,now I finally solve it.
|
|
nguyễn vãn lâm:
2016-01-12 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:
2016-01-08 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:
2014-10-19 11:06:29
What faster way there is to generate all primitive triplets than using the Tree of primitive Pythagorean triples? |
|
wisfaq:
2014-10-19 11:06:29
Nice problem!
|
|
Min_25:
2014-10-19 11:06:29
@Francky
|
|
Francky:
2014-10-19 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: | 2014-05-26 |
Time limit: | 1s-15s |
Source limit: | 5120B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 GOSU |