Editing 3176 - Fibonacci perechi

Se consideră şirul Fibonacci, definit astfel: f1=1, f2=1, fn=fn−1+fn−2, dacă n>2.

==Cerință==

Se dau perechi de numere '''a''' și '''b''' cu '''a ≤ b'''. Să se calculeze pentru câte perechi fb este multiplu de fa.

==Date de intrare==

Fișierul de intrare '''fibo0.in''' conține pe fiecare linie câte două numere '''a''' și '''b''' cu semnificația din enunț .

==Date de ieșire==

Fișierul de ieșire '''fibo0.out''' va conține pe prima linie numărul '''N''', reprezentând numărul de perechi ce respectă condiția impusă .

==Restricții de precizări==

*Se vor citi până la '''1.000.000''' de perechi
*Numerele citite vor fi numere naturale strict mai mari decât '''2''' și mai mici decât '''2.000.000.002'''

==Exemplu==

'''fibo0.in'''
:4 9
:4 8
:10 12
:7 21

'''fibo0.out'''
:2

==Rezolvare==

<syntaxhighlight lang="python" line="1" start="1">

def fibonacci(n):
    fib = [0, 1]
    for i in range(2, n+1):
        fib.append(fib[i-1] + fib[i-2])
    return fib

def count_multiples(pairs):
    max_n = max(max(pair) for pair in pairs)
    fib = fibonacci(max_n)
    count = 0
    for a, b in pairs:
        if fib[b] % fib[a] == 0:
            count += 1
    return count

pairs = [(4, 9), (4, 8), (10, 12), (7, 21)]
print(count_multiples(pairs))
with open('fibo0.out', 'w') as f:
    f.write(str(count_multiples(pairs)))

</syntaxhighlight>

==Explicație==

f4=3
, iar f9=34
 care NU este multiplu de 3

f4=3
, iar f8=21
 care este multiplu de 3

f10=55
, iar f12=144
 care NU este multiplu de 55

f7=13
, iar f21=10946
 care este multiplu de 13