C++ ciąg Fibonacciego modulo

Witam,
Mam do napisania program poniższej treści:

Należy policzyć liczby Fibonacciego F(n) mod 70001 dla ujemnych n. Należy skorzystać z faktu, ze F(-2k) = -F(2k) i F(-2k + 1) = F(2k - 1).

Oczywiście F(0) = 0, F(1) = 1 i F(n) = F(n - 1) + F(n - 2) dla n > 1.

Przydatne moga być również zależności:
F(2n) = F(n) (F(n) + 2 F(n - 1))
F(2n + 1) = F(n + 1)2 + F(n - 1)2

Mój problem polega na tym, że dla dużych liczb przekracza zakres. Czy ktoś mógłby mi pomóc?

Tutaj jest kod:

 
int main(int argc, char *argv[])
{   
	
	int n;
	cin>> n;

   
   long long int tab[10000];
   tab[0]=0;
   tab[1]=1;
   int i;
   for (i=2;i<=n;i++)
  {
       if (i%2==0)
   tab[i]=-tab[i-1]-tab[i-2]; else
   tab[i]=tab[i-1]+tab[i-2];
  
  
   }
   cout<<tab[i-1]%70001<<"\n";
   
    system("PAUSE");
    return EXIT_SUCCESS;
}

Rób modulo po każdej operacji to nie będziesz miał przepełnienia. Ten if w pętli mi sie nie podoba.

ok to to jest poprawione:

int main(int argc, char *argv[])
{   
	
	
	
	cin>> n;
     if (n<0) n=-n;
   long long int tab[10000];
   tab[0]=0;
   tab[1]=1;
   int i;
   for (i=2;i<=n;i++)
  {
      
   tab[i]=(tab[i-1]+tab[i-2])%70001;
  
  
   }
   cout<<tab[i-1]<<"\n";
   
    system("PAUSE");
    return EXIT_SUCCESS;
}


 

Wyniki które powinny wyjść to przykładowo

-3 2
-25 5024
-187 34789
-1000 31219
-9998 10430

do 187 działa poprawnie potem daje błędne wyniki. Mam pewną wątpliwość czy to modulo jest dobrze zastosowane, bo przecież w ten sposób dodaje reszty z dzielenia a chyba powinno być w ten sposob że początkowo dodaje wyrazy a całą sumę robię modulo

Zakładając, że a,b i n są dodatnie, to a%n+b%n=(a+b)%n. Te wyniki na pewno są dobre?

Dobre są na pewno

A pamiętałeś o tym, że F(-2k) = -F(2k) i -a (mod n) = (n-a) % n (dla a dodatniego i mniejszego niż n).

int fibonacciModulo70001(int n) {
    static const int smallFib[] = { 0, 1, 1, 2, 3, 5, 8, 13, 21 };
    static const int smallFibCount = sizeof(smallFib)/sizeof(smallFib[0]);
    if (n>=0 && n<smallFibCount)
        return smallFib[n];

    if (n&1==0)
        return (fibonacciModulo70001(n/2)*(long long)(fibonacciModulo70001(n/2) + 2*fibonacciModulo70001(n/2 - 1))) % 70001;
    if (n<0)
        return fibonacciModulo70001(2 - n);
    int a = fibonacciModulo70001(n/2+1);
    int b = fibonacciModulo70001(n/2-1);
    return (a*(long long)a+b*(long long)b) % 70001;
}

70000^2>232

Małe liczby Negafibonacciego