Ciąg Fibonacciego na dużych liczbach – na uczelnianej sprawdzarce nie przechodzi pomimo poprawnych wyników

Cześć,
mam do zrobienia zadanie, gdzie wiadomo, iż F0 = F1 = 1 oraz, że Fn = Fn-1 + Fn-2.
Wejście: dana jest jedna liczba naturalna n nie większa od 2dopotęgi31.
Wyjście: 4 ostatnie cyfry liczby Fn.

Zrobiłam to zadanie i otrzymuje poprawne wyniki, ale na uczelnianej sprawdzaczce nie przechodzi- część testu zaakceptowana, część oznaczona jako błąd, a kończy się przekroczenie limitu czasu. Jak mogę zoptymalizować swój kod? Rzeczywiście dla n=2147483648 chwilę trwa zanim wyrzuci wynik.
Próbowałam robić coś z tablicami, ale jestem początkująca i trochę się w tym gubię- sama nie wiem, czy to przyśpieszy działanie mojego kodu dla liczb unsigned long.

#include <iostream>

using namespace std;

void fib(unsigned long n)
{
    unsigned long long a = 1, b = 1;
    for (unsigned long i = 0; i < n; i++) {
        b = a + b; //pod zmienną b przypisujemy wyraz następny czyli a+b
        a = b - a;
    }
    cout << a % 10000;
}

int main()
{
    unsigned long n;
    cin >> n;
    fib(n);
    return 0;
}

Nie licz całej liczby, jeśli potrzebujesz tylko ostatnich czterech cyfr. Szczególnie, że dawno wyjdziesz poza zakres wartości.

Poza tym, powinien być do zaobserwowania okres, więc nie powinno być powodu aby wszystko liczyć

https://pl.wikisource.org/wiki/Ci%C4%85g_Fibonacciego

f100 juz Ci sie nie zmiesci do zmiennej a jak masz miec F2147483648 to wyobraz sobie jak glupio duza bedzie ta liczba

skoro bedzie glupio duza, to wystarczy znalezc zaleznosc miedzy liczbami i na podstawie N wypisywac ostatnie 4 cyfry

Dwie poprawki:
1) modulo to co napisał @kq
2) żeby się zgadzało z Wikipedią, trzeba poprawić zakres for

Wynik:

#include <iostream>

using namespace std;

void fib(unsigned long n)
{
    unsigned long long a = 1, b = 1;
    for (unsigned long i = 1; i < n; i++) {
        b = a + b; //pod zmienną b przypisujemy wyraz następny czyli a+b
        a = b - a;
        b = b % 10000;
        a = a % 10000;
    }
    cout << a;
}

int main()
{
    unsigned long n;
    cin >> n;
    fib(n);
    return 0;
}

https://ideone.com/Za3BIy

Podpowiedź: (a + b) % c == ((a % c) + (b % c)) % c

https://en.wikipedia.org/wiki/Pisano_period

Zanim Zaczniesz szukać Pisano Period, można spróbować Fibonaccie-go w O(logn):

#include <iostream>
#include <vector>

using namespace std;

// 2 x 2 matrices modulo multiplication
vector<vector<long> > matr_mul_mod(vector<vector<long> > A, vector<vector<long> > B, int m) {
    int a = ((A[0][0] * B[0][0]) % m +  (A[0][1] * B[1][0]) % m)  % m;
    int b = ((A[0][0] * B[0][1]) % m +  (A[0][1] * B[1][1]) % m)   % m;
    int c = ((A[0][1] * B[0][0]) % m +  (A[1][1] * B[0][1]) % m)   % m;
    int d = ((A[0][1] * B[0][1]) % m +  (A[1][1] * B[1][1]) % m)   % m;
    return { {a, b}, {c, d} };
}

// 2 x 2 matrix to power n, mod m, in O(logn)
vector<vector<long> > mod_power_matrix(vector<vector<long> > A, int n, int m) {
    if ( n == 0) return { {1L, 0L}, {0L, 1L} };
    else if (n % 2 != 0) {
        return matr_mul_mod(A, mod_power_matrix(matr_mul_mod(A, A, m), (n - 1) / 2, m), m );
    }
    else {
        return mod_power_matrix(matr_mul_mod(A, A, m), n / 2, m);
    }
}
//Fibonacci modulo
long fibo_modulo(long n, int m) {
    vector<vector<long> > A = { {1L, 1L}, {1L, 0L}};
    return mod_power_matrix(A, n, m)[0][1];
}

int main (){
        for (long i = 0; i < 20; i++) 
            cout << fibo_modulo(i, 3) << " "; // correct, according to wikipedia:
                                              // https://en.wikipedia.org/wiki/Pisano_period#Definition
        cout << "\n";
}

Tak można liczyć liczby Fibonacciego, gdyż:

Co jest szczególnym przypadkiem tego: https://en.wikipedia.org/wiki[...]on#Solving_via_linear_algebra .
long jest, żeby zapobiec overflow w mnożeniu, jakby co.

A powiedz mnie takie sztuczki:

template<int N>
constexpr int fibonacci()
{
    if constexpr (N>=2)
        return fibonacci<N-1>() + fibonacci<N-2>();
    else
        return N;
}

są akceptowalne u was?

@revcorey - Nieakceptowane.
@kq i @vpiotr - nie wiem, dlaczego błędne wynik dla większych liczb wychodzą. Sprawdzę to dla ciekawości o co chodzi. Niestety i tak za długo się wykonuje kod dla dużych liczb.
@lion137 - super, udało się!!! Dziękuję za pomoc;) Nie wpadlabym, że będzie chodzić o macierze.