# PBinfo #1265 – giovanacci – Rezolvare C++

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

## Enunț

Cerința

Șirul Fibonacci este definit după regula: 

\(F_1 = 1\)
\(F_2 = 1\)
\(F_n = F_{n – 1} + F_{n – 2}\)

Comisia mafioților îl supune pe Giovanni la T teste. Pentru fiecare test se dau n și apoi n numere naturale \({pos}_1, {pos}_2, …, {pos}_n\) reprezentând poziții în șirul Fibonacci. Se cere să se găsească cel mai mare număr g care divide \(F_{{pos}_1}, F_{{pos}_2}, …, F_{{pos}_n}\). Comisia a înțeles că Giovanni nu poate reține numere mari, așa că îi cere să afișeze restul împărțirii lui g la numărul p. Fiind depășit de cerință, mafiotul are opțiunea să sune publicul și vă contactează pe voi. Ajutați-l pe Giovanni să-și mențină demnitatea și el vă va răsplăti cu un punctaj pe măsură. 

Date de intrare
Fișierul de intrare giovanacci.in conține pe prima linie numerele T și p, iar pe următoarele T linii n, urmat de n numere naturale. 

Date de ieșire
Fișierul de ieșire giovanacci.out va conține cele T răspunsuri, câte unul pe linie. 

Restricții și precizări

\(1 ≤ T ≤ 10^3\)
\(2 ≤ p ≤ 10^5\)
\(1 ≤ n ≤ 10^3\)
\(1 ≤ pos_i ≤ 10^{17}\)

Exemplu:
giovanacci.in

2 2
3 6 9 12
2 5 10
giovanacci.out

0
1
Explicație
Sunt 2 teste. Pentru primul test, 2 este cel mai mare număr care divide 8, 34, 144. Pentru al doilea test, 5 este cel mai mare număr care divide 5 și 55. Răspunsurile s-au afișat modulo 2.

## Cod sursă C++

```cpp
#include <fstream>
const char IN [ ] = "giovanacci.in";
const char OUT[ ] = "giovanacci.out";
const int MAX_MOD = 100000;
using namespace std;
ifstream cin ( IN );
ofstream cout( OUT );
int fib [ 4 * MAX_MOD + 1 ];
long long gcd ( long long a, long long b )
{
    return b ? gcd ( b, a % b ) : a;
}
int getPeriod ( int mod )
{
    fib [ 0 ] = 0;
    fib [ 1 ] = 1;
    int i = 2;
    do
    {
        fib [ i ] = ( fib [ i - 1 ] + fib [ i - 2 ] ) % mod;
        i ++;
    } while ( fib [ i - 1 ] != 1 || fib [ i - 2 ] != 0 );
    return i - 2;
}
int main ( void )
{
    int T, mod;
    int n;
    long long x, q;
    int period;
    cin >> T >> mod;
    period = getPeriod ( mod );
    while ( T -- )
    {
        cin >> n >> q;
        for ( int i = 1; i < n; i ++ )
        {
            cin >> x;
            q = gcd ( q, x );
        }
        cout << fib [ q % period ] << '\n';
    }
    return 0;
}
```

## Resurse

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