Euler Problem 75: Find the number of different lengths of wire can that can form a right angle triangle in only one way.

Solution: Implementacija je generalizacija problema 5. Sa određenom analizom i implementacijom binarnog algoritma za GCD, implementacija je vrlo brza i rješava problem u nekoliko milisekundi.

namespace EulerProblem75 { class Program { static void Main(string[] args) { int max_p = 1500000; long max_c =max_p / 2; long max_m=(long)(Math.Sqrt(max_c)); long c; long p, k=0; long [] tripl = new long[max_p+1]; long count = 0; for (int i = 0; i < tripl.Length; i++) { tripl[i] = 0; } for (long m = 1; m <= max_m; m++) { for (long n = 1+m%2; n < m; n+=2) { if (GCD(m, n) != 1) continue; c = m * m + n * n; if (c > max_c) break; //Counting the perimeters //For each m,n we can calculate perimeter. If diferent m,n give //the same perimeter we can count them and exclude from counting m,n // with exactly one perimeter p =2*m*(m+n); k = 1; if (p <= max_p) { while (k * p <= max_p) { tripl[k*p]=tripl[k*p]+1; k++; } } } } //Exclude all perimeter with zero, two or greater perimeter for (k = 12; k <= max_p; k += 2) if (tripl[k] == 1) count++; Console.WriteLine(count); Console.WriteLine("Press any key to continue..."); Console.Read(); } //Fast binary GCD //The Binary GCD Algorithm as given in the //The Art of Computer Programming written by D.E.Knuth static long GCD(long u, long v) { long k = 0, t = 0, i; while ((u & 1)!=1 && (v & 1)!=1) { k++; u >>= 1; v >>= 1; } if ((u & 1)==1) t = u; else t = -v; do { while ((t & 1)!=1) t >>= 1; if (t > 0) u = t; else v = -t; t = u - v; } while (t!=0); for (i = 0; i < k; i++) u <<= 1; return u; } } }

Advertisements