Modulo Operation Tricks

When you solve a problem that might result in values beyond integer limits (e.g., Wouldn't fit into a 64bit integer), you're often asked to print the value modulo a significant prime value (e.g. 10^9 + 1).

To be able to use the modulo operation correctly, you need to understand its properties.

Trick #1 Multiplication/Summation of values

For example, if you are multiplying/adding a set of numbers (a, b, c, d) then its useful to know that:

(a*b*c*d)%N = (a%N)*(b%N)(c%N)*(d%N) = ((a*b*c)%N)*d%N

The above is quite useful when you want to always keep calculations to fit into the given limits.

Trick #2 Multiplicative Inverse

For division, it's a little bit tricky though, you can't merely assume that:

(a/b)%N = (a%N/b%N)

Although that would be awesome, it's unfortunately not correct - So to solve this, you have to understand the modular multiplicative inverse of a number A.

So to calculate (a/b)%N, you can convert it to a%N*power(b, N-2) - I will not explain how or why, please refer to the wiki page above for more details.

Trick #3 Negative Numbers

Another problem one would face during programming contests is when you calculate modulo for a negative number, which doesn't really work as intended.

So -1%10 would result in -1 rather than 9 - This really depends on the programming language you use but this trick is useful for Java and C++ but not for Python which produces the right value 😊.

To overcome this, you can calculate it by adding N to the number so, -1%10 = 9%10 = 9 👍.

That's it! I will keep this post up to date with any other tricks I find in the future.