6507 - Fibo Gcd

Cerința

Se dau două numere naturale pozitive, n și m. Să se determine cel mai mare divizor comun (GCD) al celor două numere Fibonacci F(n) si F(m).

Date de intrare

Programul citește de la tastatură două numere naturale pozitive n și m.

Date de ieșire

Pe ecran se va afișa mesajul: "Datele de intrare corespund restricțiilor impuse.". În următorul rând se va afișa pe ecran cel mai mare divizor comun GCD(F(n),F(m)), reprezentând cel mai mare divizor comun al lui F(n) si F(m).

În cazul în care datele introduse de la tastatură nu îndeplinesc cerințele enunțate, pe ecran se va afișa mesajul "Datele de intrare nu corespund restricțiilor impuse.".

Restricții și precizări

• 1 ⩽ n, m ⩽ 1000000

Exemplu 1

Intrare

10

15

Ieșire

Datele de intrare corespund restricțiilor impuse.

5

Rezolvare

def citeste_numere():
    try:
        numar_1 = int(input("Introduceți primul număr (n): "))
        numar_2 = int(input("Introduceți al doilea număr (m): "))
        return numar_1, numar_2
    except ValueError:
        return None, None


def valideaza_date(numar_1, numar_2):
    if 1 <= numar_1 <= 10 ** 9 and 1 <= numar_2 <= 10 ** 9:
        return True
    return False


def calculeaza_gcd(numar_1, numar_2):
    while numar_2:
        numar_1, numar_2 = numar_2, numar_1 % numar_2
    return numar_1


def calculeaza_fibonacci(k):
    if k == 0:
        return 0
    elif k == 1:
        return 1

    fib_0, fib_1 = 0, 1
    for _ in range(2, k + 1):
        fib_0, fib_1 = fib_1, fib_0 + fib_1
    return fib_1


def fibonacci_gcd(numar_1, numar_2):
    gcd_val = calculeaza_gcd(numar_1, numar_2)
    return calculeaza_fibonacci(gcd_val)


def main():
    numar_1, numar_2 = citeste_numere()

    if numar_1 is None or numar_2 is None:
        print("Datele de intrare nu corespund restricțiilor impuse.")
        return

    if valideaza_date(numar_1, numar_2):
        print("Datele de intrare corespund restricțiilor impuse.")
        rezultat = fibonacci_gcd(numar_1, numar_2)
        print(rezultat)
    else:
        print("Datele de intrare nu corespund restricțiilor impuse.")


if __name__ == "__main__":
    main()