Search code examples
c++mathmodular-arithmetic

Modular arithmetic - competitive programming

I saw a lot of competitive programmers writing code with ((a + b) % d + d) % d in C++. Why don't they just use (a + b) % d? What is that + d inside parentheses good for? Does it have something to do with negative numbers?

Thanks

Solution

  • Yes you are correct. Until C++11 the behaviour of the remainder operator % for negative arguments was left to the implementation, subject to some constraints. And adding d to the left argument can help that so long as the other terms in that argument sum to greater or equal to -d, which, in general is not the case. (-a / d multiples of d for the case of negative a would have been a better additive constant in your particular case.)