How to Improve Maximum Common Divisor Algorithm - URI 1028

Question

I’m solving this URI problem which basically calls for the maximum common divide between two values to be found.

I originally resolved with the math.gcd in half a dozen lines, however, the code was not accepted as the URI uses a version of Python 3 prior to the inclusion of gcd. Well, so I solved the problem in another way:

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)

The outputs are all correct, but problem is my code is being refused for exceeding the time limit.

I ask: How can I improve the same? I’ve wiped everything I can, but it still exceeds the time limit. Any suggestions?

Answer 1

I was able to solve it by implementing recursion thanks to @Anderson’s tip Carlos Woss in the comment above.

To whom it may concern, follow the algorithm.

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))

Answer 2

This question refers to the number problem "1028", whose title is "Figurines", made available by "Uri Online Judge" (online programming marathon).

See here the entirety of the statement.

One of the ways to resolve this issue is this:...

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))

See here the functioning of the algorithm.