3047 - Fibo Frac

Enunt

Fie șirul Fibonacci dat prin F1 = 1, F2 = 1 și relația de recurență Fk = Fk-1 + Fk-2, k ≥ 3. Se consideră un număr natural N.

Cerinţa

Să se scrie un program care determină numărul F al fracțiilor diferite ireductibile subunitare, ce se pot forma utilizând primii N termeni ai șirului Fibonacci.

Date de intrare

Fișierul de intrare fibofrac.in conține pe prima linie numărul N.

Date de ieșire

Fișierul de ieșire fibofrac.out va conține pe prima linie numărul F, cu semnificația de mai sus.

Restricţii şi precizări

• Pentru teste în valoare de 24 puncte, 0 < N < 80
• Pentru teste în valoare de 40 puncte, 0 < N < 1101
• Pentru teste în valoare de 56 puncte, 0 < N < 50001
• Pentru teste în valoare de 100 puncte, 0 < N < 1.000.000
• Două fracții ireductibile a / b și c / d sunt diferite dacă a ≠ c sau b ≠ d.
• 0 ≤ F < 2^63

Exemplul 1

fibofrac.in

 7

fibofrac.out

 14

Explicație

N = 7; Primii 7 termeni ai șirului Fibonacci sunt: 1, 1, 2, 3, 5, 8, 13. Se pot forma 14 fracții diferite ireductibile subunitare: 1/2, 1/3, 1/5, 1/8, 1/13, 2/3, 2/5, 2/13, 3/5, 3/8, 3/13, 5/8, 5/13, 8/13.

Exemplul 2

fibofrac.in

 2019

fibofrac.out

 1547722

Exemplul 3

fibofrac.in

 500000

fibofrac.out

 94988288219

Rezolvare

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

def count_fibonacci_fractions(n):
    fib = [1, 1]
    for i in range(2, n):
        fib.append(fib[i - 1] + fib[i - 2])
    
    count = 0
    for i in range(n):
        for j in range(i + 1, n):
            if gcd(fib[i], fib[j]) == 1:
                count += 1
    return count

def main():
    with open("fibofrac.in", "r") as f_in:
        n = int(f_in.readline().strip())
    
    result = count_fibonacci_fractions(n)
    
    with open("fibofrac.out", "w") as f_out:
        f_out.write(str(result))

if __name__ == "__main__":
    main()