Uva 106 - Fermat vs. Pythagoras

Problem: 106 - Fermat vs. Pythagoras
Problem Definition:

1. Fermat's Last Theorem: that there are no integer solutions of for n >2.
2. Given a positive integer N, you are to write a program that computes two quantities regarding the solution of
   
   where x, y, and z are constrained to be positive integers less than or equal to N. You are to compute the number of triples (x,y,z) such that x<y< z, and they are relatively prime, i.e., have no common divisor larger than 1.
3. You are also to compute the number of values such that p is not part of any triple (not just relatively prime triples).

You have to focus on 2 and 3.



Pythagorean triple:
A Pythagorean triple consists of three positive integers a, b, and c, such that a² + b² = c². Such a triple is commonly written (a, b, c), and a well-known example is (3, 4, 5). If (a, b, c) is a Pythagorean triple, then so is (ka, kb, kc) for any positive integer k. A primitive Pythagorean triple is one in which a, b and c are co-prime [Wiki].

There are 16 primitive Pythagorean triples with c ≤ 100:

(3, 4, 5)	(5, 12, 13)	(8, 15, 17)	(7, 24, 25)
(20, 21, 29)	(12, 35, 37)	(9, 40, 41)	(28, 45, 53)
(11, 60, 61)	(16, 63, 65)	(33, 56, 65)	(48, 55, 73)
(13, 84, 85)	(36, 77, 85)	(39, 80, 89)	(65, 72, 97)

Note, for example, that (6, 8, 10) is not a primitive Pythagorean triple, as it is a multiple of (3, 4, 5) [Wiki].


How do we generate these triple?
Euclid's formula is a fundamental formula for generating Pythagorean triples given an arbitrary pair of positive integers m and n with m > n. The formula states that the integers

form a Pythagorean triple. The triple generated by Euclid's formula is primitive if and only if m and n are coprime and m − n is odd. If both m and n are odd, then a, b, and c will be even, and so the triple will not be primitive; however, dividing a, b, and c by 2 will yield a primitive triple if m and n are coprime [Wiki]

1. we have to calculate the total number of primitive Pythagorean triples and included number must be marked. (print just total number of primitive Pythagorean triples)
2. The Number less then N not included with  Pythagorean triple,
        T = N - ( Total Number counted those are included into primitive Pythagorean triples)

Example: 
10

1. c < 10, there is one primitive Pythagorean triples i.e ( 3 , 4 ,5). so 3,4,5, (3x2=) 6, (4x2=) 8, (5x2=10), are included to generate Pythagorean triples.
2. T = 10 - 6 = 4

Output:
1 4

Code:
----------  

#include <stdio.h>

typedef long long INT;

/*Recursively Calculate GCD*/
INT gcd(INT x, INT y) {
     return y? gcd(y,x%y):x;
}

int main()
{
    short int hash[1000010]={0};
    INT n,i,j,k,a,b,c,ma,mb,mc;
    INT count,ans;

    /*freopen("a.in","r",stdin);*/

    while (scanf("%lld", &n) == 1){
        count = 0;

        for (i = 1; i*i <= n; ++i){
            for (j = i + 1; j*j <= n; j += 2){
                if (gcd(i, j) == 1) {
                    /*Euler Formula*/
                    a = j * j - i * i;
                    b = 2 * i * j;
                    c = i * i + j * j;
                    if (c > n)
                        break;
                    /*All Number is included into P.t.*/
                    ma =a,mb=b,mc=c;
                    while (mc <= n){
                      hash[ma] = hash[mb] = hash[mc] = 1;
                      ma+=a;
                      mb+=b;
                      mc+=c;
                    }

                    /*Count increase by one, i.e. one primitive Pythagorean triples found*/
                    ++count;
                }
            }
        }

        ans = n; /*Not in triples*/
        for (i = 1; i <= n; ++i){
                   ans = ans - hash[i] ;
                   hash[i] = 0;
        }
        printf("%lld %lld\n", count, ans);
    }
    return 0;
}