We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Now, let's keep it super simple and say, we put the Numerator in a variable 'Nr' and the Denominator in a variable 'Dr'. Now, we are supposed to calculate,
(Nr / Dr) % P, where 'P' is the given prime (109 + 7)
We could write the above expression as,
(Nr * Dr-1 ) % P,
Now we can apply the principle of modular arithematic,
(a * b) % p = ((a % p) * (b % p)) % p,
So, Applying the above principle, we get,
(Nr * Dr -1 ) % P = ((Nr % P) * (Dr -1 % P)) % P,
Now, using Fermat's Little Theorem, we can replace the 'Dr -1' term and the equation becomes,
(Nr * Dr -1 ) % P = ((Nr % P) * (Dr (P - 2) % P)) % P,
Now, calculating (Nr % P) is simple, we use the above used modular arithematic principle, and the term (Dr (P - 2) % P) can be calculated by using the technique stated in the link provided by the editorial.
But the problem is, that 'Dr' over there, itself can be very big. We have techniques to calculate 'x y % P', but in our case this 'x' is itself damn big. That is, our variable 'Dr' itself can be something like, '(499! * 500!)' which we cannot calculate.
Then, my question is, what value will we insert in place of 'Dr' in the term (Dr (P - 2) % P) .....?? How can that be calculated...?? I've been trying to find that out since several weeks. This is my confusion in many problems, please please clarify...... Thanks in advance...! :-)
Sherlock and Permutations
You are viewing a single comment's thread. Return to all comments →
The given problem is simple and reduces to -
(N + M - 1)!
--------------
(M - 1)! (N)!
Now, let's keep it super simple and say, we put the Numerator in a variable 'Nr' and the Denominator in a variable 'Dr'. Now, we are supposed to calculate,
(Nr / Dr) % P, where 'P' is the given prime (109 + 7)
We could write the above expression as,
(Nr * Dr-1 ) % P,
Now we can apply the principle of modular arithematic,
(a * b) % p = ((a % p) * (b % p)) % p,
So, Applying the above principle, we get,
(Nr * Dr -1 ) % P = ((Nr % P) * (Dr -1 % P)) % P,
Now, using Fermat's Little Theorem, we can replace the 'Dr -1' term and the equation becomes,
(Nr * Dr -1 ) % P = ((Nr % P) * (Dr (P - 2) % P)) % P,
Now, calculating (Nr % P) is simple, we use the above used modular arithematic principle, and the term (Dr (P - 2) % P) can be calculated by using the technique stated in the link provided by the editorial.
But the problem is, that 'Dr' over there, itself can be very big. We have techniques to calculate 'x y % P', but in our case this 'x' is itself damn big. That is, our variable 'Dr' itself can be something like, '(499! * 500!)' which we cannot calculate.
Then, my question is, what value will we insert in place of 'Dr' in the term (Dr (P - 2) % P) .....?? How can that be calculated...?? I've been trying to find that out since several weeks. This is my confusion in many problems, please please clarify...... Thanks in advance...! :-)