Błąd w zadaniu

Dzień dobry

Mam problem z poniższym zadaniem. Po wrzuceniu rozwiązania do sprawdzarki "themis" otrzymuje 1 sprawdzenie pozytywne i 1 negatywne (wrong answer).

Treść zadania:

Dla danych n i m wyznacz fib(n) mod m

Wejście
W pierwszej linii wejścia podana jest liczba testów T (1 ≤ T ≤ 100). W następnych T wierszach podane są pary n, m (1 ≤ n,m ≤ 10^9).

Przykład
Dla danych wejściowych:

10
1 10
2 10
3 10
4 25
5 25
6 25
7 27
8 29
9 31
10 33

poprawną odpowiedzią jest:

1
1
2
3
5
8
13
21
3
22

Mój kod:
ps* sprawdzarka nie widzi cerr

#include <iostream>
using namespace std;

void FC1(unsigned long long F[2][2], unsigned long long M[2][2]);

void FC2(unsigned long long F[2][2], unsigned long long n);


unsigned long long fib(unsigned long long n)
    {
        unsigned long long F[2][2] = {{1,1},{1,0}};
        if (n == 0)
            return 0;

        FC2(F, n-1);
        
    return F[0][0];
    }


void FC2(unsigned long long F[2][2], unsigned long long n)
{
        if( n == 0 || n == 1)
            return;

    unsigned long long M[2][2] = {{1,1},{1,0}};

    FC2(F, n/2);
    FC1(F, F);

    if (n%2 != 0)
        FC1(F, M);
}

void FC1(unsigned long long F[2][2], unsigned long long M[2][2])
{
unsigned long long x = F[0][0]*M[0][0] + F[0][1]*M[1][0];
unsigned long long y = F[0][0]*M[0][1] + F[0][1]*M[1][1];
unsigned long long z = F[1][0]*M[0][0] + F[1][1]*M[1][0];
unsigned long long w = F[1][0]*M[0][1] + F[1][1]*M[1][1];

F[0][0] = x;
F[0][1] = y;
F[1][0] = z;
F[1][1] = w;
}


int main()
{
    unsigned long long t;
    unsigned long long n;
    unsigned long long m;
    cin>>t;
    for(int i=0; i=t; i++)
    {
        cin>>n;
        cin>>m;
        cerr<<"Wynik: ";
        cout<<fib(n)%m<<endl;
    }
return 0;
}

Przyczyna jest oczywista: integer overflow.
Teraz zastanów się, gdzie to występuje i jak można tego uniknąć.

podpowiedź: potrzebujesz funkcji int fibModulo(int n, int m)

Gdzie do liczenia Fibonacci z takimi liczbami. Zainteresuj się tym:
https://en.wikipedia.org/wiki/Pisano_period

@lion137: no ale przecież to nie ma sensu, bo wyznaczenie tego okresu wcale nie jest takie proste. Najlepszą rzeczą to faktycznie wyliczyć fibonacciego szybkim potęgowaniem modulo.

No nie wiem czy wydoli, takie zadania na Project Euler zawsze robiłem z Pisano.

Próbowałem napisać z pissanno period. Wydaje się liczyć dobrze ale przy drugim sprawdzeniu wywala błąd. Tym razem Illegal syscall.

#include <iostream>
using namespace std;

long long fibmod(long long n, long long m)
{
   long long wynik;
   long long indeks;
   long long cykl = n+1;
   long long sz = min (n+1,m*m+1);
   long long *F = new long long[sz];
    F[0] = 0;
    F[1] = 1;
    F[2] = 1;

    for (long long i = 3; i < sz; i++)
        {
            F[i] = (F[i-2] + F[i-1]) % m;
                if (F[i] == 1 && F[i-1] == 0)
                    {
                        cykl = i-1;
                        break;
                    }
        }

    indeks = n % cykl;
    wynik = F[indeks];
    delete[]F;
    return wynik;

}

int main()
{
    int t;
    long long n;
    long long m;
    cin>>t;
    for(int i=0; i<t; i++)
    {
        cin>>n;
        cin>>m;
        cout<<fibmod(n,m)<<endl;
    }
    return 0;
}

Przebudowałem trochę kod. Dzięki za pomoc teraz działa.

#include <iostream>
#include <cstring>
using namespace std;

struct Macierz
{
    long long nums[ 2 ][ 2 ];

    Macierz()
    {
        memset( nums, 0, sizeof( nums ) );
    }
};

Macierz algorytm( const Macierz & one, const Macierz & two, long long mod )
{
    Macierz result;
    for( int i = 0; i < 2; ++i )
        {
        for( int j = 0; j < 2; ++j )
        {
            for( int k = 0; k < 2; ++k )
            {
                result.nums[ i ][ j ] += one.nums[ i ][ k ] * two.nums[ k ][ j ];
            }
            result.nums[ i ][ j ] %= mod;
        }
    }

    return result;
}

Macierz Modulo( const Macierz & mat, long long power, long long mod )
{
    if( power < 2 )
         return mat;

    Macierz half = Modulo( mat, power / 2, mod );
    if( power % 2 == 0 )
         return algorytm( half, half, mod );
    else
         return algorytm( half, algorytm( half, mat, mod ), mod );

}

int main()
{
    long long n;
    long long m;
    int t;

    cin>>t;
    for(int i = 0; i<t; i++)
    {
    cin>>n;
    cin>>m;

    Macierz mat;
    mat.nums[ 0 ][ 0 ] = mat.nums[ 0 ][ 1 ] = mat.nums[ 1 ][ 0 ] = 1;
    cout << Modulo( mat, n-1, m ).nums[ 0 ][ 0 ] << '\n';
    }
}

A ta linijka w pętli, nie powinna wyglądać tak?
F[i] = (F[i-2] % m + F[i-1] % m) % m;
(8 + 7) % 3 = 0 = (8 % 3 + 7 % 3) % 3