SEPT14: FLOORI4

Please anyone clear my doubt:
question link:http://www.codechef.com/problems/FLOORI4/

In setter’s solution :http://www.codechef.com/viewsolution/4921354 (correct solution),

DOUBT 1: if i remove this line:if (answer<0) answer += M;(because in solution,I don’t see any chance that ans would be negative)

      That would be a wrong solution!! why???  what is the importance of that line here(in this question).

DOUBT 2: If i break the statement:answer = (ll)(answer + (i-1)* (sumfour(y) - sumfour(x)))%M;
into two individual statements like these:
answer = (ll)(answer + (i-1)* (sumfour(y) -sumfour(x)));
if(answer>=M) answer%=M;

   That would again be a wrong answer!!why??what is the difference??
  1. That would be wrong because sumfour() returns a modded value, so sumfour(y) - sumfour(x) could become -ve.

  2. Add if (answer<0) answer %= M; within the loop as well. Reason : Overflow. In a case where answer is -ve in all loops, it might add up to a large -ve value outside the range of long long since you’re only using mod when everything’s +ve.

2 Likes

Thanks partner.