Preventing Overflow with Modular Arithmetic

The Problem with Large Numbers

In competitive programming, you'll often encounter problems that ask for a count of something—combinations, permutations, paths on a grid, etc. The final answer can be astronomical. For example, calculating 100! (100 factorial) results in a number with 158 digits, far too large for any standard integer type in C++.

To test your algorithmic logic without requiring complex big integer libraries, problem setters ask for the answer "modulo some number M". A very common choice is $M=10^9+7$. This number is large enough to avoid many accidental collisions in results, small enough that the product of two numbers less than M fits into a 64-bit integer (long long), and it's a prime number, which will be important for division later on.

The famous competitive programmer Errichto provides an excellent overview of why this is necessary.

Modular Arithmetic: Thinking on a Clock

At its heart, modular arithmetic is "clock arithmetic". If it's 9 o'clock and you add 4 hours, it becomes 1 o'clock, not 13 o'clock. This is because we are working "modulo 12". The calculation is $(9+4)(\mathrm{mod}12)=13(\mathrm{mod}12)=1$.

Formally, the expression $a(\mathrm{mod}m)$ gives the remainder when $a$ is divided by $m$. This remainder is always in the range $[0,m-1]$. This "wrapping around" behavior is the key to keeping our numbers small.

The following reading from a Codeforces blog post formally introduces the terminology.

The Core Properties

The power of modular arithmetic comes from a set of properties that allow us to perform operations within the modular system without ever needing to compute the full, gigantic numbers. For any integers $a$, $b$, and modulus $m$:

1. Addition: $(a+b)(\mathrm{mod}m)=((a(\mathrm{mod}m))+(b(\mathrm{mod}m)))(\mathrm{mod}m)$
2. Multiplication: $(a\times b)(\mathrm{mod}m)=((a(\mathrm{mod}m))\times (b(\mathrm{mod}m)))(\mathrm{mod}m)$
3. Subtraction: $(a-b)(\mathrm{mod}m)=((a(\mathrm{mod}m))-(b(\mathrm{mod}m))+m)(\mathrm{mod}m)$

Notice the + m in the subtraction formula. We'll return to why that's crucial shortly.

These identities mean we can take the modulo at every intermediate step of a calculation. This ensures that the numbers we are working with never exceed the modulus, completely preventing overflow.

Let's dive into some resources that explain and prove these properties.

C++ Implementation and Pitfalls

Knowing the properties is one thing; implementing them correctly is another. There are two main pitfalls in C++.

1. Intermediate Multiplication Overflow

Consider the expression (a * b) % m. If a and b are both integers close to m (say, $10^9$), their product a * b will be around $10^{18}$. This fits within a long long. However, if your variables a and b are of type int, the multiplication a * b will be performed using 32-bit arithmetic, causing an overflow before the result is assigned to a long long and before the modulo is taken.

The safe way to compute modular multiplication is to cast one of the operands to long long first:
long long result = (1LL * a * b) % m;

Errichto demonstrates this exact point in his video.

2. Negative Results from Subtraction

This is a classic bug in C++ competitive programming code. The % operator can return negative values. For example, (5 - 8) % 10 evaluates to -3 % 10, which in C++ is -3. However, a proper modular result should be in the range $[0,m-1]$. The correct answer is 7.

To fix this, we use the property (a - b) % m = (a - b + m) % m.
By adding m before the final modulo, we guarantee the result is positive.

int result = ((a - b) % m + m) % m;

If (a - b) % m is already positive, adding m and taking another modulo doesn't change the result (e.g., (3 + 10) % 10 = 3). If it's negative, it shifts it into the correct positive range (e.g., (-3 + 10) % 10 = 7).

This crucial detail is explained in both the GeeksforGeeks article and Errichto's video.

Putting It All Together

Here are simple, robust C++ functions you can add to your programming template. They handle the casting and negative number issues correctly.

const int MOD = 1e9 + 7;

// Modular addition
long long add(long long a, long long b) {
    return (a + b) % MOD;
}

// Modular multiplication
long long mul(long long a, long long b) {
    return (1LL * a * b) % MOD;
}

// Modular subtraction
long long sub(long long a, long long b) {
    // The inner (a - b) % MOD can be negative,
    // so we add MOD and take modulo again.
    return ((a - b) % MOD + MOD) % MOD;
}

These three functions are the building blocks for almost all calculations in modular arithmetic.

Conclusion

In this lesson, we've established the "why" and "how" of basic modular arithmetic. It's not a trick to make problems harder, but an essential tool to make them solvable by managing the size of numbers.

Here are the key takeaways:

• Modular arithmetic is used in competitive programming to prevent integer overflow when dealing with very large results.
• The fundamental properties are:
  • $(a+b)(\mathrm{mod}m)=((a(\mathrm{mod}m))+(b(\mathrm{mod}m)))(\mathrm{mod}m)$
  • $(a\times b)(\mathrm{mod}m)=((a(\mathrm{mod}m))\times (b(\mathrm{mod}m)))(\mathrm{mod}m)$
  • $(a-b)(\mathrm{mod}m)=((a(\mathrm{mod}m))-(b(\mathrm{mod}m))+m)(\mathrm{mod}m)$
• The key strategy is to apply the modulo operator at every intermediate step of a calculation.
• In C++, be mindful of casting to long long for multiplications and adding the modulus in subtractions to handle potential negative results.

You now have the tools to perform chains of additions, subtractions, and multiplications without fear of overflow. But what about exponentiation, like calculating $a^b(\mathrm{mod}m)$? Doing $b$ multiplications would be too slow if $b$ is large. In our next lesson, we will tackle this exact problem by learning binary exponentiation, an efficient algorithm that computes modular powers in $O(\log b)$ time.