Problem Solutions: Fibonacci Divisibility (69) - long numbers

efesmirfis 2015-02-01 07:31:25

If I understood correctly this task It wants first modM = 0 number but inputs are giving very very huge outputs (ex = 8700 -fib(1000) = 4346655768693745643568852767504062580256466051737178040248172908953655541794905189040387984007925516929592 2593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875-)
I can use BigInteger but then I think it is becoming too complex and slow, is there any easy way or I misunderstand this task?

Rodion (admin) 2015-02-01 07:59:00

Hi! Thanks for your question!

Really this problem could be solved without long arithmetics at all because none of intermediate results needs to exceed M. You may use the property that modulo is preserved after other arithmetic operations. As a hint, please look at this discussion about similar problem.

Feel free to ask if you need more hints, though probably you will catch the idea at once.

efesmirfis 2015-02-02 17:00:01

Sorry but yet I have not find right way. I am confusing because of fib(8700) is a enormous number (maybe it equals witdh of milky way in centimeters :D) how can I reach this number and I thought most likely this huge numbers are unnecessary and I can use indices of numbers but I have not develop any correct algorithm I think I don't understand correctly this questions please give me a few more hints :)

Rodion (admin) 2015-02-02 18:06:33

Well... Here are few main ideas:

You need not calculate fib(8700) itself, only its remainder fib(8700) % M.
To calculate fib(N) you need to sum fib(N-1) and fib(N-2).
To calculate (A + B) % M you need not to know A and B themselves - it is enough to know A % M and B % M.

Try to play with small numbers (like M = 3 or M = 10) with pencil and paper. Also this short article can provide some more hints (under title of "magic property").

efesmirfis 2015-02-03 08:39:59

Thanks for your help and patience..Finally I've understood and solved this and I will improve it.

Vladimir Skvortsov 2018-10-07 11:04:37

Thank to Admin for giving this useful hint. I spent so much time creating crazy algorithms. But all it turned up so easy. Without this references and additional explanation I wouldn't solve #71 'Fibonacci Divisibility Advanced'.