Go to Fibonacci Number folder, you will see two files there, fibonacci number.py asks you to implement a function that returns the nth Fibonacci Number given n. A naive recursive implementation is given to you but it runs very slow when n gets large, you need to implement a better one ( an iterative ( loop ) one) to improve the efficiency. And the other file is the unit test file for your function. You can run the unit test file to compare your functions results with the naive implementation.

file:

def gcd_naive(a, b):

assert 1 <= a <= 2 * 10 ** 9 and 1 <= b <= 2 * 10 ** 9

for divisor in range(min(a, b), 0, -1):

if a % divisor == 0 and b % divisor == 0:

return divisor

assert False

def gcd(a, b):

assert 0 <= a <= 2 * 10 ** 9 and 0 <= b <= 2 * 10 ** 9

# START CODE HERE

# END CODE HERE

if __name__ == '__main__':

input_a, input_b = map(int, input().split())

print(gcd(input_a, input_b))