Euler Problem 75

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...");
}
//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;
}
}
}
```