Rezolvare PBinfo #3176

Se consideră şirul Fibonacci, definit astfel: \( f_{1} =1 \) , \( f_{2} =1 \), \( f_n = f_{n-1} + f_{n-2}\) , dacă n>2.

Cerința

Se dau perechi de numere a și b cu a ≤ b. Să se calculeze pentru câte perechi \(f_{b}\) este multiplu de \(f_{a}\) .

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 și 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

Explicație

\( f_{4} =3 \), iar \( f_{9} =34 \) care NU este multiplu de 3

\( f_{4} =3 \), iar \( f_{8} =21 \) care este multiplu de 3

\( f_{10} =55 \), iar \( f_{12} =144 \) care NU este multiplu de 55

\( f_{7} =13 \), iar \( f_{21} =10946 \) care este multiplu de 13