I would like to know how to comprehend a Overflow error. This month long challenge had a question Floori4 ,I was not able to do that question partially due to overflow errors and understanding of modular arithmatic. Example : link text My this solution gave WA. While my link text solution gave AC .If you notice the difference is in brackets in ans=(ans*((3nn+3*n+M-1)%M))%M so how can I comprehend it.
And can you please give some pointers on how to deal with it in future.
Thank You.
As the value of n is big the term => 3 * n * n+3 * n+M-1, gets very big.
case 1> wrong answer "ans=(ans * (3 * n * n+3*n+M-1)%M ) %M;"
Here the at first the term in bracket is solved which reduce the original term to “ans=(ans*X%M) %M”.
next operation will be ans*X, as the X is already very big this multiplication may result in overflow.
this cause you WA.
case 2> Ac ans=(ans * ((3 * n * n+3 * n+M-1)%M) ) %M;
Here the at first the term in bracket is solved which reduce the original term to “ans=(ans(X%M))%M*”.
next operation will be (X%M) which reduces the big term X to [0,M-1], which avoid the earlier overflow while doing multiplication with ans.
NOTE: (a*b)%M = ((a%M) * (b%M))%M.
hence both the cases are equal as far as no overflow occurs.