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. asked 23 Dec '12, 11:32

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 . en.wikipedia.org/wiki/Multiplicative_inverse 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 . answered 23 Dec '12, 12:13
3
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?
(23 Dec '12, 15:35)
1
Thanks, a lot Vineet . Really helpful notes. I learnt a lot from it .
(08 Jan '13, 23:18)

Yes you are correct regarding computing ABC . So if you have N 64bit numbers which you have to multiply , then you have to do N modulo operations initially and N1 modulo operations after each of the N1 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 . answered 23 Dec '12, 18:36
Thanks a lot.. You've been of great help..
(23 Dec '12, 21:16)
@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?
(08 Jan '13, 13:33)

@asheshvidyut : Multiplicative inverse with relative to a prime number is based on Fermat's theorem . answered 11 Jun '13, 11:49

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 . answered 08 Jan '13, 14:24
@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?
(11 Jun '13, 11:33)

This link is very useful https://codeaccepted.wordpress.com/2014/02/15/outputtheanswermodulo1097/ and also it explains in c++. answered 25 May '17, 18:19

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. answered 30 May '17, 02:19
