How to improve common maximum divisor algorithm - URI 1028

Question

How to improve common maximum divisor algorithm - URI 1028

Navigation

#1 by (4 votes)

2

I'm solving this URI problem that basically asks for the maximum common divisor between two values.

I originally resolved with math.gcd on half a dozen lines, but the code was not accepted since 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 that my code is being refused for exceeding the timeout.

I ask: How can I improve it? I've already dried up everything I've got, but it's still going out of time. Any suggestions?

python python-3.x uri-online-judge

asked by anonymous 05.08.2018 / 15:46

1 answer

How to define a variable in the configuration of a Virtual Host, to avoid repetition? Entities classes

score 4 · Accepted Answer

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

Anyone interested can 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))