Many times I have seen contest sites asking for not the actual answer but a modulo of the answer with something weird like (10^9 + 7). But why do they do that? And why only this number?
The reason is obvious, "Integer Overflow Error" !!! The next obvious question is why this number only?
Isn't it ok to get the last few digits of the final answer(say ans)? Its ok but the chances of clashes are too high. So we will take the modulo with 2^32 or 2^64 depending upon our range(int or long). However there is a serious problem here.
Suppose we are asked to find the value of (5000!), now this means that there will be atleast 500 zeros at the end of the answer. And when we take (ans mod 2^32) we will get 0 as the final answer. And that is where people can cheat. So the solution to that is to use a prime number for doing the modulo.
No comments:
Post a Comment