[Desafio] Último Teorema de Fermat

[_Isis_ 202]

Problema

Dado um inteiro positivo N, escreva um programa que calcule duas quantidades relacionadas à solução de x² + y² = z², onde x,y e z são inteiros positivos menores ou iguais a N. Você deve calcular o número de tuplas (x,y,z) tais que x<y<z e que sejam relativamente primas. Você também deve calcular a quantidade de valores p (0 < p <= N) tais que p não faz parte de nenhuma tupla (e não somente daquelas que são relativamente primas).

 

 

 

Entrada

A entrada consiste em uma seqüência de inteiros positivos, um por linha. Cada inteiro no arquivo de entrada será menor ou igual a 1.000.000. EOF indica o término da entrada.

 

 

 

Saída

 

 

Para cada inteiro N no arquivo de entrada imprima dois inteiros separados por um espaço. O primeiro inteiro é o número de tuplas relativamente primas (tal que cada componente da tupla seja menor ou igual a N). O segundo número é o número de inteiros positivos menores ou iguais a N que não fazem parte de nenhuma tupla cujos componentes sejam menores ou iguais a N. Para cada linha de entrada deve haver uma linha de saída.

 

 

 

Exemplo de entrada

 

 

10

25

100

 

 

Exemplo de saída

 

 

1 4

4 9

16 27

 

 

 

Original do UvA: http://icpcres.ecs.baylor.edu/onlinejudge/...&problem=42

 

 

Complicadinho,mas pelo menos pode render.

[quitZAUMMM 18]

boa http://forum.imasters.com.br/public/style_emoticons/default/thumbsup.gif

 

vo fds vo tentar fazer, tomare q eu consiga :lol:

[_Isis_ 202]

Eu até me animei a aprender a pilotar Python no paradigma funcional pra fazer isso.

[_Isis_ 202]

#!/usr/bin/python

CONJUNTO = set()

def prima(A,B):
dividendo = max(A,B)
divisor = min(A,B)
while divisor and dividendo >= divisor and divisor > 1:
	dividendo,divisor = divisor,dividendo%divisor
if divisor == 1: return True
elif divisor == 0: return False


while True:
try:
	N = raw_input()
except EOFError:
	break

N = int(N)

TUPLAS = []
PRIMAS = []
for Z in xrange(1,N+1):
	for Y in xrange(1,Z+1):
		for X in xrange(1,Y+1):
			if ( pow(X,2) + pow(Y,2) == pow(Z,2)):
				if prima(X,Y) and prima(X,Z) and prima(Y,Z): PRIMAS.append((X,Y,Z))
				else: TUPLAS.append((X,Y,Z))

for el_tupla in PRIMAS:
	for elemento in el_tupla:
		CONJUNTO.add(elemento)

for el_tupla in TUPLAS:
	for elemento in el_tupla:
		CONJUNTO.add(elemento)

TOTAL = set(range(1,N+1))
print  len(PRIMAS)," ",len(TOTAL-CONJUNTO)
del PRIMAS
del TUPLAS
CONJUNTO.clear()
TOTAL.clear()

 

Só testei com os exemplos

[quitZAUMMM 18]

nossa nunca estudei python pra mim esta td grego ai :lol:

 

tem uns desafios no site do spoj mo tensos de fazer igual o demonstracao de honestidade.. lembro q fiquei + de 1 semana tentando fazer e naum consegui...

[_Isis_ 202]

Isso porque Python é mais fácil de ler...

 

Se não me engano, da pra substituir

 

try:
	N = raw_input()
except EOFError:
	break

N = int(N)

 

por

 

try:
  N = input()
except EOFError:
  break

[_Isis_ 202]

Mudei algumas coisas:

 

#!/usr/bin/python


def prima(A,B):
dividendo = max(A,B)
divisor = min(A,B)
while divisor and dividendo >= divisor and divisor > 1:
	dividendo,divisor = divisor,dividendo%divisor
if divisor == 1: return True
elif divisor == 0: return False


CONJUNTO = set()

while True:
try:
	N = input()
except EOFError:
	break

N = int(N)

TUPLAS = list()
PRIMAS = list()
for Z in xrange(1,N+1):
	for Y in xrange(1,Z+1):
		for X in xrange(1,Y+1):
			if ( pow(X,2) + pow(Y,2) == pow(Z,2)):
				if prima(X,Y) and prima(X,Z) and prima(Y,Z): PRIMAS.append((X,Y,Z))
				else: TUPLAS.append((X,Y,Z))

TMP = set(TUPLAS).union(set(PRIMAS))
for (a,b,c) in TMP:
	CONJUNTO.add(a)
	CONJUNTO.add(b)
	CONJUNTO.add(c)

print  len(PRIMAS)," ",N-len(CONJUNTO)
del PRIMAS
del TUPLAS
TMP.clear()
CONJUNTO.clear()