I am beginner and I want to know what is the mod concept.In many of the problems in the codechef, answers are very large numbers so in those questions it is written that print answer mod 10^9+7.Why this gives correct answer and how it is correct?Also is it also possible that when input is very large(if there is) then we can first modulo it by 10^9+7 and then use this value to solve the problem?
The reason why you are asked to compute the mod of the answer is because in some languages like c++ etc,there is no facility for int data types to store large numbers.The largest is long long int which can also hold only upto 10^18(which would be mere 30 digit long).Hence to make life easier for the participants you are asked to compute the mod of the answer which would be well within the capacity of the data type and hence will avoid overflow.If you are asked to print the entire answer then you have to resort to methods such as storing the answer in a string or integer array and then outputting it which only further increases the difficulty.
1 Like
for your first question…
this link explains it i guess…
http://discuss.codechef.com/questions/43464/reason-for-taking-modulo
for your second question …
No, you cant always do it…
for example suppose you are required to take lcm of say 100 numbers(one question in july long required that)
ans then print the lcm modulus 1000000007 . Here you cant take the lcm of the modulus of the input and then do it. But of course for multiplication , addition , and subtraction this wont matter.
Also look into modular multiplicative inverse for tackling division operation .
1 Like
Regarding your second question,that is not needed because if the input is too large you can directly take the input as a string,the main reason why mod is applied in the output side ,it reduces the dificulty.