# PBinfo #3507 – Fibo_gcd – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: deivid

## Enunț

Cerința
Se consideră Șirul lui Fibonacci cunoscut prin relația de recurență: \(  {F}_{1} = 1 \); \(  {F}_{2} = 1 \); \(  {F}_{i} = {F}_{i – 2} + {F}_{i – 1}, i ≥ 3  \). 

Pentru n perechi de numere naturale x y să se afișeze numărul de perechi pentru care numerele \(  {F}_{x} \) și \(  {F}_{y} \) sunt prime între ele.

Date de intrare
Fișierul de intrare fibo_gcd.in conține pe prima linie numărul n, iar pe următoarele n linii n perechi de numere naturale.

Date de ieșire
Fișierul de ieșire fibo_gcd.out va conține pe prima linie numărul K, reprezentând numărul de perechi care respectă proprietatea din enunț.

Restricții și precizări

1 ≤ n ≤ 50.000
1 ≤ x, y ≤ 2.000.000.000

Exemplu:
fibo_gcd.in

5
8 7
3 4
2 1
9 6
10 5
fibo_gcd.out

3
Explicație
Primele 3 perechi satisfac condiția din enunț.

## Cod sursă C++

```cpp
#include <bits/stdc++.h>
using namespace std;
ifstream f ("fibo_gcd.in");
ofstream g ("fibo_gcd.out");
int n, x, y, cnt, D;
int main() {
    f >> n;
    while (n --) {
        f >> x >> y;
        D = __gcd (x, y);
        if (D == 1 || D == 2) cnt ++;
    }
    g << cnt << '\n';
    f.close();
    g.close();
    return 0;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/3507)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/3507/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-3507/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)