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;
        }
    }
}