Pracsiu Dan (dnprx) 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
24puncte,0 < N < 80 - Pentru teste în valoare de
40puncte,0 < N < 1101 - Pentru teste în valoare de
56puncte,0 < N < 50001 - Pentru teste în valoare de
100puncte,0 < N < 1.000.000 - Două fracții ireductibile
a / bșic / dsunt diferite dacăa ≠ csaub ≠ d. 0 ≤ F < 263
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