== include(page="template/taskheader" task_id="fibofrac") ==

Poveste şi cerinţă...

Fie şirul Fibonacci dat prin $F{~1~} = 1,F{~2~} = 1$ şi relaţia de recurenţă $F{~k~} = F{~k-1~} + F{~k-2~}, k ≥ 3.$
Se consideră un număr natural N.
 
h2. Cerinţă
 
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.

h2. Date de intrare

Fişierul de intrare $fibofrac.in$ ...

Fişierul de intrare $fibofrac.in$ conţine pe prima linie numărul N.

h2. Date de ieşire

În fişierul de ieşire $fibofrac.out$ ...

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

h2. Restricţii

* $... ≤ ... ≤ ...$

* Pentru teste în valoare de **24** puncte, **$0 < N < 80$**
* Pentru teste în valoare de **40** puncte, **$0 < N < 1 101$**
* Pentru teste în valoare de **56** puncte, **$0 < N < 50 001$**
* 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 &le; F < 263**$

h2. Exemplu

table(example). |_. fibofrac.in |_. fibofrac.out |
| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|
 
h3. Explicaţie

table(example). |_. fibofrac.in |_. fibofrac.out |_. Explicaţie |
| 7
| 14
| $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:
<tex>
\frac{1}{2}, \frac{1}{3}, \frac{1}{5}, \frac{1}{8}, \frac{1}{13}, \frac{2}{3}, \frac{2}{5},
\frac{2}{13}, \frac{3}{5}, \frac{3}{8}, \frac{3}{13}, \frac{5}{8}, \frac{5}{13}, \frac{8}{13}
</tex>
|
| 2019
| 1547722
| Se pot forma $1547722$ fracţii diferite
ireductibile subunitare utilizând primii
$2019$ termeni ai şirului Fibonacci.
|
| 500000
| 94988288219
| Se pot forma $94988288219$ fracţii diferite
ireductibile subunitare utilizând primii
$500000$ termeni ai şirului Fibonacci.
|

...

== include(page="template/taskfooter" task_id="fibofrac") ==