2

Estou resolvendo este problema do URI que pede, basicamente, que se encontre o máximo divisor comum entre dois valores.

Resolvi originalmente com o math.gcd em meia dúzia de linhas, porém, o código não foi aceito já que o URI utiliza uma versão do Python 3 anterior à inclusão do gcd. Pois bem, assim resolvi o problema de uma outra maneira:

N = int(input())
monte, maior = [], 0

for x in range(N):
    A, B = input().split(' ')
    A, B = int(A), int(B)
    for x in range(A, 1, -1):
        if A % x == 0:
            monte.append(x)
    for x in range(len(monte)):
        if B % monte[x] == 0:
            maior = monte[x]
            break
    print(maior)

As saídas estão todas corretas, mas problema é que meu código está sendo recusado por exceder o tempo limite.

Pergunto: Como posso melhorar o mesmo? Já enxuguei tudo o que consegui, mas continua excedendo o tempo limite. Alguma sugestão?

1

2 Respostas 2

5

Consegui resolver implementando recursividade graças à dica do @Anderson Carlos Woss no comentário acima.

A quem interessar possa, segue o algoritmo.

def mdc(A, B):
return A if not B else mdc(B, A % B)

N = int(input())

for x in range(N):
    A, B = input().split(' ')
    A, B = int(A), int(B)
    print(mdc(A, B))
1
0

Esta questão se refere ao problema de número "1028", cujo título é "Figurinhas", disponibilizado por "Uri Online Judge" (maratona online de programação).

Veja aqui a íntegra do enunciado.

Uma das formas para se resolver esta questão é a seguinte...

def mdc(a, b):
    if a % b == 0:
        return b
    else:
        return mdc(b, a % b)


quant_de_testes = int(input())
for c in range(quant_de_testes):
    a = input().split(" ")
    numero1 = int(a[0])
    numero2 = int(a[1])
    print(mdc(numero1, numero2))

Veja aqui o funcionamento do algoritmo.

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .