I’m new to competitive programming and I have come across the request for the “answer modulo 1000007” on many occasions. Could someone provide me the link for any resource or just explain how I’m supposed to handle the computation of large numbers by using this method?
I program in C++, so any help with respect to the usage with the long long type would be appreciated.
Hello Vikram ,
I program in Java so can’t give you C++ specific tips , I am a bit out of touch with C++ . But I can help you with regards to basics of computation of answers modulo a large ( possibly prime ) number say P .
When say you have to multiply several numbers in sequence and have the result modulo P , take each number modulo P , and after each multiplication take the result modulo P before further multiplication
Similarly while adding a sequence of numbers take modulo after each addition or frequently enough .
NOTE 1 : For this to hold , P need not be prime .
NOTE 2 : Since P is always given to fit in 32 bit number , you will never have a number which does not fit in 64 bit .
There is some difficulty that arises when division comes in like in computation of factorials .
There is concept of multiplicative inverse that you should know in this case . Its useful quite a many times . It would be too much to write it over here . So I am giving you a link . Read it there .
NOTE 1 : Here P needs to be prime.
NOTE 2 : To use the concept of multiplicative inverse effectively you need to know how to take fast exponentiation . i.e. compute x ^ p in log ( p ) steps . Let me know if you need help in this .
Yes… If you could help me out with the fast exponentiation technique too I would be grateful…
Also… When you say, " take each number modulo P , and after each multiplication take the result modulo P before further multiplication",
that means if I need to compute ABC, I should compute
((((A%P)*(B%P))%P) * (C%P))%P
Am I right?
Yes you are correct regarding computing ABC . So if you have N 64-bit numbers which you have to multiply , then you have to do N modulo operations initially and N-1 modulo operations after each of the N-1 multiplications .
Regarding Fast Exponentiation : Suppose you need to calculate x ^ 56 .
Represent the power in base 2 . So , 56 = ( 111000 ) in base 2
Now calculate values x , x^2 , x^4 , x^8 , x^16 , x^32 and so on by multiplying the previous result with itself repeatedly . The number of such values needed is log (Power)
Now to calculate x ^ 56 do ( x ^ 32 ) * ( x ^ 16 ) * ( x ^ 8 ) …
i.e. Wherever there are 1’s use those numbers in multiplication and wherever there are 0’s dont use those numbers .
Welcome aboard to competitive programming . Have a nice time with CodeChef .
Thanks a lot… You’ve been of great help…
@Vineetpaliwal This modulus tips you have given have helped me get correct answers for many problems. Can i know in computing ABC, why we are taking modulus so many times, instead of doing it just once (like ABC % P). When i initially did that it gave wrong answer, but with your tip , i got the correct answer. Can you elaborate a little as to why?
If A * B * C exceeds the 32 bit or 64 bit range of variable in which you are storing your answer , then the most significant bits of the number/answer are dropped to fit the answer within the bit size of variable . Therefore you get wrong answer .
So if in a 64 bit number A you store 2^62 and in another 64 bit number B you store 2^62 , then when you multiply A and B the system does not give a runtime error or exception , it just does some bogus computation and stores the bogus result . Even if your statement is like long64 ans = (ABC) % P , then the result of each intermediate computation of AB and ((AB)*C) should fit in the variable sizes of A , B , C . The system will not create any temporary unlimited size numbers even if your initial variables A , B , C , P and final answer “Ans” are all in the limits . The intermediate results should also be in limits .
Thanks, a lot Vineet . Really helpful notes. I learnt a lot from it .
@vineetpaliwal Sir
for example we have to calculate n!/((q!)^r) where n <=10^5 and finally result % P
so first -->i calculated the factorials till n using the MOD “which changed the value of factorial if its > P.”
now to find (q!)^r i can use fast exponentiation but how to get multiplicative inverse.
In the wikipedia link there is Newton’s Raphson Method
Do i have to implement that ? and what about the wrong factorials value?
@asheshvidyut : Multiplicative inverse with relative to a prime number is based on Fermat’s theorem .
Fermat’s theorem states that a^(p-1) = 1 ( mod p ) , where p is prime
So , a^(p-2) = 1/a ( mod p ) , where p is prime , this is the idea of multiplicative inverse
So if you have to calculate n! / (q!)^r with precomputed factorials with relative to mod p , you already have n! mod p and q! mod p . From value of q! mod p take fast exponentiation to power r . Then calculate multiplicative inverse of the result.
Multiplicative inverse = power ( a , p-2 ) mod p .
Again use fast exponentiation for calculation a ^ (p-2) .
Now use the result obtained to multiply with n! mod p and take mod again and that is your answer .
This link is very useful https://codeaccepted.wordpress.com/2014/02/15/output-the-answer-modulo-109-7/ and also it explains in c++.
The modulo operator is just like the mod operator when the number is positive, but different if the number is negative.
Many a times in the problems we are asked to give the answer modulo 10^9+7.
Let the answer(before using modulo) be denoted by ‘a’.
Simple Straightforward Rule-
if a is positive, then a modulo 10^9+7= a%(10^9+7)
if a is negative, then a modulo 10^9+7= (a%(10^9+7))+(10^9+7)
If, in such problems, we find that any step of the loop may calculate a value that is out of the integer range (if we are using integers), then we can use the modulo operator in that step itself. The final answer will be as if we have used the modulo operator only once.
This is because- (a**b)%c=((a%c)*(b%c))%c
Same goes for addition and subtraction.