xrisk's blog

By xrisk, history, 5 years ago,

In one problem I was doing, I was getting WA because of some modulo error. In particular, I had a cumulative frequency array which I had defined as:

cf[i]=cf[i-1]+f[i];where f[i] was always positive.

Later, there was a sequence of range queries to answer, so I did:

cout << cf[r]-cf[l-1] for each query; L, R were the range boundaries (both inclusive).

However, the problem stated to report the answer modulo 1000000007, so I changed my queries to:

cout << (cf[r]-cf[l-1]%MOD)%MOD;.

But on seeing the intended solution, I saw that the correct query was :

cout<<(cf[r]-cf[l-1]+MOD)%MOD;

I am unable to understand this, because what I knew was that (a-b)%m = (a%m-b%m)%m

Can please someone explain this to me?

Thanks!! Any help is appreciated.

• +3

 » 5 years ago, # | ← Rev. 2 →   0 If (a-b) < 0 then (a-b) % m fails (in C++). (cf[r]-cf[l-1]%MOD) can fail if cf[r] < (cf[l-1]%MOD).PS: On the other hand you mentioned that the sequence is increasing (which means cf[r] > cf[l-1]). Another place why it failed can be that you need to apply MOD operation on each step, not only when printing the answer, because int overflow can occur.
 » 5 years ago, # |   -6 in maths:(a-b)%m==(a%m-b%m)%m
•  » » 5 years ago, # ^ |   0 (10 - 8)% 3 = 1 while 10%3 - 8%3 = -1 . Actually, for a >  = b and a, b, m > 0, (a-b)%m = (a%m - b%m + m)%m i think
•  » » » 5 years ago, # ^ |   +11 (10-8)%3=1, really? Lolwut?
•  » » » 5 years ago, # ^ |   0 1+1=10 isn't it :D
 » 5 years ago, # |   +3 In lots of programming languages, a negative number modulo something will be negative. For example, -1 mod 5 would return -1 in many languages. Since we are taking a modulo, we know x%m = (x+m)%m. Therefore, by adding mod, we always make x positive, and so our modulo should behave as expected.
 » 5 years ago, # |   0 For mod operation you can always do the following: (a+b) mod m = (a+b+m)%mSo this formula will work for negative and positive values, but you have to be careful about the overflow.Another way: If you know that a and b less than m you can apply this: int temp = (a+b); if(temp >= m)temp-=m; And this is even faster than the first formula.
 » 5 years ago, # |   0 First of all, I believe that your calculation of cf looked like this: cf[i] = (cf[i - 1] + f[i]) % MOD; Otherwise your solution is probably wrong, because you have integer overflow. Moreover, integer overflow in signed types (like int, but not unsigned int) is undefined behavior, that is, your program can do anything if that happen (formally, it can even wipe your hard drive). Don't worry — usually you just get strange wrong answer or runtime error.I don't get what is the reasoning behind writing (a - b % MOD) % MOD instead of (a - b) % MOD. Would you mind explaining?About the reference solution: you see, if we define reminder as a number from 0 to MOD - 1, then . However, it's not like some CPUs work and if you calculate in C++ on a typical PC, you will most likely get  - 2. It's correct in some sense, but it's not what "reminder" means in most problems. So, when you deal with negative numbers or subtractions modulo MOD, you should be careful be negative results. Say, writing (a - b) % MOD is unsafe even if both a and b are correct non-negative remainders, because a - b can be negative and the whole result would be wrong. However, if we write (a - b + MOD) % MOD then the whole expression on the left would be non-negative and we will get correct result (if there were no integer overflow, of course).
•  » » 5 years ago, # ^ |   0 Thanks for the reply.Yes, you are right, I declared cf array as cf[i]=(cf[i-1]+f[i])%MOD;However, I know for sure that cf does not overflow (there is a solution that does not take modulo to compute it).I tried both (a%m-b%m)%m and (a-b%m)%m but they did not pass.Here is the problem links: Author’s solution: https://code-snip.herokuapp.com/paste?-JxM86eirwK4RQIP2zsb One of my solutions: https://code-snip.herokuapp.com/paste?-JxU2ly2pqABhLzCcxlB
 » 5 years ago, # |   0 I've always believed that the reason a%b is negative when a is negative is that we want to maintain the invariant: a = a/b*b + a%b
•  » » 5 years ago, # ^ |   0 That is half of the reason. Other half is the way division result is rounded. Rounding towards 0 results in negative values, but rounding down would result in positive values. - 5 =  - 1·3 - 2 rounding to 0 - 5 =  - 2·3 + 1 rounding downInteresting fact, until c++11 direction of rounding (and as a result modulo value) was implementation defined, but starting with c++11 it is guaranteed to round towards zero and negative modulo for negative values.