Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
Newer
Older
100644 43 lines (34 sloc) 1.002 kb
7577c15 @juanplopes using comments then
authored
1 /*
3e1ee6e @juanplopes solution descriptions up to 45
authored
2 Generate all pythagorean triangles by using Euclid's formula.
3 I.e.: pick any n, m, n>m, coprime (gcd==1) and with one of them even.
4 a = n*n-m*m
5 b = 2*m*n
6 c = n*n+m*m
7
8 e.g. nm(1,2) => abc(3,4,5)
9
10 Generate all the derived triangles by multipling it by constant k, until it
11 overflows the target.
12
13 e.g. (3,4,5) => (6, 8, 10), (9, 12, 15) and so on...
7577c15 @juanplopes using comments then
authored
14 */
bed602c @juanplopes problem 75
authored
15 import System
16 import System.Linq.Enumerable
17
0f7b45a @juanplopes making impl run on linux
authored
18 L = 1.5*10**6+1
d57bcc3 @juanplopes problem 75 optimizations
authored
19 SL = cast(int, Math.Sqrt(L))
bed602c @juanplopes problem 75
authored
20 T = array(int, L)
21
22 def gcd(a as int, b as int):
198be3e @juanplopes problem 82
authored
23 while(b): a, b = (b, a%b)
24 return a;
bed602c @juanplopes problem 75
authored
25
d57bcc3 @juanplopes problem 75 optimizations
authored
26 answer = 0
bed602c @juanplopes problem 75
authored
27 for m in range(1, SL):
198be3e @juanplopes problem 82
authored
28 for n in range(m+1, SL):
29 if (n+m)%2 != 1 or gcd(m,n) != 1: continue
30 a,b,c = (n*n-m*m, 2*m*n, n*n+m*m)
31 if a+b+c >= L: break
32
33 ka,kb,kc = 0,0,0
34 for k in range(1,L):
35 ka, kb, kc = (ka+a,kb+b,kc+c)
36 if ka+kb+kc >= L: break
37 d = ++T[ka+kb+kc]
38 if d==1: answer+=1
39 elif d==2: answer-=1
bed602c @juanplopes problem 75
authored
40
198be3e @juanplopes problem 82
authored
41
bed602c @juanplopes problem 75
authored
42 print answer
43 assert answer == 161667
Something went wrong with that request. Please try again.