0
$\begingroup$

While solving problems in SPOJ, I faced cases where I need to take Modulus of Big numbers like Fibonacci with 10^9 + 7 ( say MOD ). Now, consider the following case :

(Fib(n) + Fib(6*n-1)) / x

As Fib(n) cannot be stored in 64 bit for high n, we are forced to take modulus in every loop of calculating Fibonacci number using Matrix exponentiation. But the division by 'x' later does not give the correct result. That is

(Number/x) % MOD != (Number%MOD)/x generally.

So, in the above cases, is there any way to get correct result? That is Modulus have to be done before division and with that is it possible to get correct result?

$\endgroup$
  • $\begingroup$ What size is $x$ appoximately? Is it guaranteed to be a proper divisor? Should you reply with $\lfloor N/x \rfloor \% MOD$, actually? $\endgroup$ – Hagen von Eitzen Sep 5 '12 at 12:09
  • $\begingroup$ @HagenvonEitzen Yes, x is proper divisor of N. And yeah, required is (N/x)%MOD. $\endgroup$ – sabari Sep 5 '12 at 12:38
  • $\begingroup$ Actually I wanted to calculate the value of the function given in math.stackexchange.com/questions/190443/…. In that result there is division operation. And Modulus operation has to be performed before division in calculation the Lucas number and Fibonacci number. $\endgroup$ – sabari Sep 5 '12 at 13:09
0
$\begingroup$

This can be done using the Modular Inverse trick. The concept and the way to find that and also the usage is described with examples here.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.