Juan Céspedes - Programas 

Problemas resueltos del Juez Online de la UVa 

Fermat vs. Pythagoras

106.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

int relat[1000001];
int list[1000001];

int
gcd(int a, int b) {
	while (a!=b) {
		if (a>b) a-=b;
		else     b-=a;
	}
	return a;
}

void
pita(int n) {
	int s,t;
	int a,b,c;
	int i;

	memset(list, 0, sizeof(list));
	memset(relat, 0, sizeof(relat));
	for (s=1; s<sqrt(n); s++) {
		for (t=s+1; t<=sqrt(n); t++) {
			a = 2*s*t;
			b = t*t - s*s;
			c = t*t + s*s;
#if DEBUG
			printf("s=%d, t=%d\n", s, t);
			printf("%d^2 + %d^2 = %d^2\n", a, b, c);
#endif
			if (c <= n) {
				if (!list[a] || list[a]>c) list[a] = c;
				if (!list[b] || list[b]>c) list[b] = c;
				if (!list[c] || list[c]>c) list[c] = c;
				if (gcd(a,b)==1 && gcd(b,c)==1 && gcd(a,c)==1) {
					relat[c]++;
				}
			}
			for (i=2; ; i++) {
				if (c*i > n) {
					break;
				}
				if (!list[a*i] || list[a*i]>c*i) list[a*i] = c*i;
				if (!list[b*i] || list[b*i]>c*i) list[b*i] = c*i;
				if (!list[c*i] || list[c*i]>c*i) list[c*i] = c*i;
			}
		}
	}
}

int
main(void) {
	int n;

	pita(1000000);
	while (scanf("%d", &n)==1) {
		int i;
		int cer=0, rel=0;
		for (i=1; i<=n; i++) {
			if (!list[i] || list[i]>n) cer++;
			rel += relat[i];
		}
		printf("%d %d\n", rel, cer);
	}
	return 0;
}