Witam,
Mam problem z jednym zadankiem:
"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.
Kolejne testy zawierają wartości n: do -104, do -107, do -1010"
Na wejście w kolejnych liniach podawane są n, wyjście to w kolejnych liniach obliczona przez program wartość.
Przykładowy input:
-3
-25
-187
-1000
-9998
I output:
2
5024
34789
31219
10430
Do long longa wejdzie chyba max 94 czy 93 liczba fibonacciego więc raczej nie trzeba tych liczb do końca obliczać.
Do tego limit wykonania programu to 1s.
Dodatkowo dostałem takie zależności:
F(2n) = F(n) (F(n) + 2 F(n - 1))
F(2n + 1) = F(n + 1)2 + F(n - 1)2
Proszę o rady czy sugestie.