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