Integer overflow and modulo arithmetic

Why this matters when you build with AI

An AI tool often writes int for a sum, an area or a midpoint without checking the limits of the problem. The program still compiles, runs fast and prints a number. The number is simply wrong. The judge then returns a wrong answer verdict, shown as WA, and nothing in the output tells you why.

For example, we ran a program that adds the value 1000000000 two hundred thousand times into an int. The true total is 200000000000000. The program printed 552894464. No warning, no crash, just a wrong number. Your local tests with small values pass, so the bug shows up only on the judge's large tests.

This lesson teaches you to read the limits of a problem and decide the integer type before you write code. It also gives you a small set of modular helpers that you can paste into any solution. When an AI gives you code that does arithmetic on large numbers, you should check each multiplication against the limits. This lesson shows you how.

Examples here are in C++17. C++17 is a version of the C++ language standard, selected with -std=c++17. Python has no overflow problem, which we explain at the end.

The idea: the range of each type

An integer type holds numbers in a fixed range. Once a result goes past the top of that range, it wraps around or the behaviour becomes undefined. Here are the ranges on a typical 64-bit judge:

• int holds 32 bits. Its range is -2147483648 to 2147483647. The top value is 2^31 - 1, about 2.1 billion.
• long long holds 64 bits. Its range is about -9.2 × 10^18 to 9.2 × 10^18. The top value is 9223372036854775807.
• __int128 holds 128 bits. Its range is about -1.7 × 10^38 to 1.7 × 10^38. It is a GCC and Clang extension, not part of the standard, so check that your judge's compiler accepts it.

Two kinds of overflow matter here.

Signed overflow happens with int and long long. The C and C++ standards say that signed overflow is undefined behaviour. Undefined behaviour means the standard does not say what the program does, so the compiler may assume it never happens and optimise the code on that assumption. In practice most builds wrap the bits, but you cannot rely on that.

Unsigned overflow happens with unsigned types. It is defined: the value wraps modulo 2 to the power of the bit width. This is safe, but unsigned values cannot be negative, so using unsigned to avoid a negative value often causes new bugs.

A sanitizer can find signed overflow while your program runs. The flag -fsanitize=undefined turns on the undefined behaviour checker, and it includes the signed overflow check. Here is a real message from our run of the first broken snippet below:

bad1.cpp:7:37: runtime error: signed integer overflow: 1000000000 + 2000000000 cannot be represented in type 'int'

The sanitizer tells you the line and the two numbers that overflowed. Use it in your local tests, as the lesson on contest templates shows.

Estimate the size from the constraints

You rarely need to run the program to know whether a value fits. Multiply the largest possible inputs. For example, with n up to 200000 and values up to 10^9, a sum can reach 2 × 10^14. That is above the int range, so the sum needs long long.

Use these rules as a first check:

1. A sum of n values up to v is at most n × v. If that is above 2.1 × 10^9, use long long.
2. A product of two values up to v is at most v × v. If that is above 9.2 × 10^18, the product does not fit in long long.
3. A product of three values is at most v³. For v near 10^9, that is about 10^27, which does not fit in long long either.
4. A product of two values up to 10^18 is about 10^36. It fits in __int128 but not in long long.

Rule 3 surprises many people, so check it for any formula with three factors.

Worked example: three snippets with overflow

We now look at three short programs. Each one prints a wrong answer. The first computes a sum, the second a product, and the third a midpoint. We read each one, find the risk from the numbers, and fix it.

Snippet 1: a sum in int

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, v;
    cin >> n >> v;
    int sum = 0;
    for (int i = 0; i < n; i++) sum += v;
    cout << sum << '\n';
}

Input 200000 1000000000 should print 200000000000000. The compiler gives no warning with -Wall -Wextra -Wconversion. The program prints:

552894464

The sum goes past 2.1 × 10^9 after just three additions, so the value wraps. The fix is to make the accumulator a long long:

    long long sum = 0;

With that change the same input prints 200000000000000.

Snippet 2: a product in int

#include <bits/stdc++.h>
using namespace std;
int main() {
    int w = 100000, h = 100000;
    int area = w * h;
    cout << area << '\n';
    long long ok = (long long)w * h;
    cout << ok << '\n';
}

The first line of output is wrong and the second is right:

1410065408
10000000000

The multiplication w * h happens in int, so the result wraps before it is stored. The cast (long long)w * h converts w first, so the multiplication happens in long long. The cast must come before the multiplication. Writing (long long)(w * h) does not help, because the product is already wrong when the cast happens.

Snippet 3: a midpoint in int

Binary search often computes the middle index as (lo + hi) / 2. This formula breaks when lo + hi is above 2.1 × 10^9.

#include <bits/stdc++.h>
using namespace std;
int main() {
    int lo = 1500000000, hi = 2000000000;
    int mid = (lo + hi) / 2;
    cout << mid << '\n';
    int mid2 = lo + (hi - lo) / 2;
    cout << mid2 << '\n';
}

The output is:

-397483648
1750000000

The sum lo + hi is 3.5 × 10^9, which wraps to a negative value. The second form never computes a sum above hi, so it is safe as long as lo and hi are valid int values.

Modular arithmetic

Modular arithmetic keeps numbers small. The notation a mod m means the remainder when a is divided by m. Contest problems often ask for the answer modulo a prime such as 10^9 + 7, written 1000000007. The reason is practical: the answer stays small, so it fits in a long long.

Two facts make the reduction work. For any integers a, b and m > 0:

• (a + b) mod m equals ((a mod m) + (b mod m)) mod m.
• (a * b) mod m equals ((a mod m) * (b mod m)) mod m.

So you may reduce each part first, then combine. The reduced parts are below m, so their sum is below 2m and their product is below m². The product fits in long long when m is at most about 3 × 10^9. For larger m, use __int128.

The negative remainder trap

In C++, the % operator keeps the sign of the left operand. Our run printed:

-1
-7

The first line is -7 % 3, which gives -1, not the 2 you may expect. The second line is -7 % 1000000007, which is -7. A negative result breaks any code that assumes the answer is in [0, m). The fix is to add m when the remainder is negative:

ll norm(ll a, ll m) {
    ll r = a % m;
    return r < 0 ? r + m : r;
}

Python does this differently. In Python, -7 % 3 gives 2, because the result takes the sign of the divisor. Do not assume the two languages agree when you copy a formula between them.

Multiplication that overflows even when reduced

Reducing the inputs first is not enough when the modulus is large. Here is a check with m near 10^18:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
    const ll m = 1000000000000000003LL;
    ll a = 999999999999999999LL, b = 999999999999999999LL;
    cout << (a * b) % m << '\n';
}

Our run printed -527149226598858730. The correct value is 16, which we checked with Python's arbitrary precision integers. The product a * b is about 10^36 and wraps inside long long, and a negative value comes out of %. The fix is to multiply in __int128, which holds about 1.7 × 10^38.

Printing a __int128 needs care. The standard output stream has no operator for it. We tried:

__int128 x = 5;
cout << x << '\n';

GCC 15.2 rejected it with error: ambiguous overload for ‘operator<<’. Convert to long long before printing, once you know the value fits, or write your own digit printer.

The modular helper set

The helpers below work for any m > 0. Addition and subtraction are safe for m up to 4 × 10^18, because the reduced values are below m and their sum is below 8 × 10^18, which fits in long long. Multiplication uses __int128, so it is safe for m up to about 9 × 10^18.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using i128 = __int128;
 
// a mod m in [0, m) for any a and any m > 0.
ll norm(ll a, ll m) {
    ll r = a % m;
    return r < 0 ? r + m : r;
}
// (a + b) mod m.
ll madd(ll a, ll b, ll m) { return norm(norm(a, m) + norm(b, m), m); }
// (a - b) mod m.
ll msub(ll a, ll b, ll m) { return norm(norm(a, m) - norm(b, m), m); }
// (a * b) mod m, with the product taken in 128 bits.
ll mmul(ll a, ll b, ll m) {
    return (ll)((i128)norm(a, m) * norm(b, m) % m);
}
// a^e mod m for e >= 0, by repeated squaring.
ll mpow(ll a, ll e, ll m) {
    ll r = norm(1, m);
    a = norm(a, m);
    while (e > 0) {
        if (e & 1) r = mmul(r, a, m);
        a = mmul(a, a, m);
        e >>= 1;
    }
    return r;
}
// Inverse of a mod p, for a prime p, by Fermat's little theorem: a^(p-2) mod p.
ll minv(ll a, ll p) { return mpow(a, p - 2, p); }

Each helper does one job, and each one reduces its inputs first, so the code works with negative inputs too. The inverse only exists when a and p have no common factor, and p must be prime for Fermat's theorem to apply. Do not use minv with a modulus that is not prime.

We tested these helpers against Python's % and pow on 3500 random cases. The cases used negative inputs, moduli from 1 to about 4 × 10^18, and the modulus 998244353. The helpers matched every case. We also ran the code with -fsanitize=address,undefined, and the sanitizers reported nothing.

A worked problem: sum of pair products

Here is a problem written for this lesson.

The first line holds n, with 1 at most n at most 200000. The second line holds n integers a_1 to a_n, each from 0 to 10^9. Print the sum of a_i × a_j over all pairs i < j, modulo 1000000007.

For the input 3 and 1 2 3, the pairs are (1,2), (1,3) and (2,3). Their products are 2, 3 and 6, and the sum is 11.

The naive method checks every pair. With n up to 200000 that is about 2 × 10^10 pairs, which is far too slow. A better method adds the pairs one element at a time. When we reach element j, the sum of the products with all earlier elements is a_j times the running prefix sum. We add that to the answer, then add a_j to the prefix sum.

#include "modhelp.hpp"
// Sum of a[i] * a[j] over all pairs i < j, modulo 1e9+7.
int main() {
    const ll MOD = 1000000007LL;
    int n;
    cin >> n;
    ll prefix = 0, answer = 0;
    for (int j = 0; j < n; j++) {
        ll x;
        cin >> x;
        x = norm(x, MOD);
        answer = madd(answer, mmul(x, prefix, MOD), MOD);
        prefix = madd(prefix, x, MOD);
    }
    cout << answer << '\n';
}

Here modhelp.hpp is the helper file above. Keep the helpers in a separate file so each new problem can include them. Here is the real output of this program on three inputs:

input: 3 / 1 2 3                         output: 11
input: 4 / 1000000000 1000000000 1000000000 1000000000   output: 294
input: 2 / 1000000006 1000000006         output: 1

Check each line. The first is 11, as computed above. The second has six pairs of 10^9 each, so the true sum is 6 × 10^18. The value 6 × 10^18 mod 1000000007 is 294, which Python also gives. The third has two values equal to -1 modulo the prime, and (-1) × (-1) = 1.

We also checked the program against a brute force that adds every pair with Python integers. The test used 300 random cases with n from 0 to 12 and values up to 10^9. All 300 matched.

The complexity is O(n) time and O(1) extra memory. Each step does a fixed number of helper calls.

Common mistakes

Summing into int. The symptom is a value that is too small, sometimes negative, on large tests only. Fix it by checking the largest possible sum from the constraints.

Casting after the multiplication. The expression (long long)(w * h) does not help, because w * h has already wrapped. Cast before the multiplication: (long long)w * h.

Computing a midpoint as (lo + hi) / 2. The symptom is a negative index in a binary search when lo and hi are both large. Use lo + (hi - lo) / 2.

Forgetting the negative remainder. The symptom is a result like -1 where 2 is expected, which often shows up as a WA on a test with negative input. Use norm before you compare or output a value.

Multiplying two reduced values with a large modulus. The symptom is a negative or very wrong answer when m is near 10^18. The product of two values below m can be near 10^36. Use mmul, which computes the product in __int128.

Printing __int128 directly. The symptom is the compile error ambiguous overload for ‘operator<<’. Convert to long long after you have reduced the value, or write your own printer.

Trusting Python to behave like C++. Python integers never overflow, so a Python program can give the right answer where the C++ version fails. The reverse matters too: when you port a C++ formula to Python, the % sign rule differs, and the result changes.

Expecting a small local test to catch it. Overflow appears only when values are large. A test with n = 5 and values up to 10 will always pass. Build a large test to check the risk.

Checklist

• Read the largest value of each input from the constraints.
• Estimate each sum, product and midpoint, using the largest values.
• Use long long for any sum above 2.1 × 10^9, and for any product of two values up to 10^9.
• Use __int128 for any product of two values up to 10^18.
• Cast before a multiplication, not after.
• Compute a midpoint as lo + (hi - lo) / 2.
• Reduce modulo m with norm so negative values give a result in [0, m).
• Use mmul for products when m is larger than about 3 × 10^9.
• Compile with -fsanitize=undefined and run a large local test.
• Use minv only when the modulus is prime.

Hands-on exercise

Make a folder on your machine and save these files: modhelp.hpp with the helper set, and pairs.cpp with the pair-sum program.

Then do the three repairs.

1. Save snippet 1 as fix1.cpp, fix it, and run it on 200000 1000000000. Check that it prints 200000000000000.
2. Save snippet 3 as fix3.cpp, fix the midpoint, and print the result for lo = 1500000000 and hi = 2000000000. The result should be 1750000000.
3. Save snippet 2 as fix2.cpp and fix it so the area of a 100000 by 100000 rectangle prints 10000000000.

Compile each file with the same flags as the lesson on contest templates:

g++ -std=c++17 -O2 -Wall -Wextra -Wshadow -Wconversion -fsanitize=address,undefined -fno-sanitize-recover=all pairs.cpp -o pairs

Then test pairs against a Python brute force. The brute force sums a[i] * a[j] for i < j using Python integers and prints the result modulo 1000000007. Generate 100 random inputs with n from 0 to 12 and values up to 10^9, and compare each output. Your outputs should match the brute force. Report how many cases you ran.

Show the answer

Repair 1: declare the accumulator as long long sum = 0; and keep sum += v;. The v is still an int, but it is added into a 64-bit total.

Repair 2: write long long area = (long long)w * h;. The cast comes before the multiplication.

Repair 3: write int mid = lo + (hi - lo) / 2;. The difference hi - lo is 500000000, which fits in int, and the sum never exceeds hi.

The brute-force comparison should show no mismatches. If it does, print the first failing input and check it by hand before you change the helper set.

Practice problems

Work each problem with pencil and paper first, then test your code.

Practice 1: name the type. For each constraint, name the smallest type that holds the answer safely.

• (a) n up to 100000, each value up to 10000, print the sum.
• (b) n up to 200000, each value up to 10^9, print the sum.
• (c) x and y up to 10^9, print x * y.
• (d) x and y up to 10^12, print x * y mod 1000000007.

Hint: for (d), reduce each factor before you multiply.

Show the answer

(a) int is enough, because the sum is at most 10^9, below 2.1 × 10^9. (b) long long, because the sum is up to 2 × 10^14. (c) long long, because the product is up to 10^18. (d) long long after reduction, because x mod p and y mod p are below 1000000007, so their product is below about 10^18. The reduction is the step that matters.

Practice 2: three factors. Given a, b, c in [0, m) with m up to 1000000007, print a * b * c mod m.

Hint: mmul multiplies two numbers, so call it twice.

Show the answer

ll ans = mmul(mmul(a, b, m), c, m);

Check: for 999999999 999999999 999999999 and m = 1000000007, the program printed 999999495, and Python gave the same value.

Practice 3: large power. Print x^k mod m for x up to 10^18, k up to 10^18 and m = 1000000000000000009. Do not assume m is prime.

Hint: use mpow, which does not need a prime.

Show the answer

mpow(x, k, m). For the input 2 1000000000000000000 1000000000000000009, the program printed 777343750000000007, and Python's built-in pow(2, 10**18, 10**18+9) printed the same value.

Practice 4: normalise. Read a and m, where a may be negative and m > 0. Print the smallest non-negative x with x congruent to a modulo m.

Hint: this is norm.

Show the answer

norm(a, m). For -7 3, the answer is 2, because -7 + 9 = 2. Our run printed 2.

Practice 5: modular inverse. For a prime p and a not divisible by p, print the inverse of a modulo p.

Hint: minv does this. Check your answer by multiplying: a × inverse mod p must be 1.

Show the answer

minv(a, p). For a = 3 and p = 7, the answer is 5, since 3 × 5 = 15 and 15 mod 7 = 1. Our run printed 5.

Python notes

Python integers have no fixed size, so a * b * c gives the exact product. That removes the overflow problem but not the speed problem. A Python loop over 2 × 10^5 values is fine, but a loop over 10^8 steps is not. Use the reduction anyway, because the output must match the modulus and the numbers stay small.

In Python, the operator % returns a value with the sign of the divisor, so -7 % 3 gives 2. The norm step is not needed in Python for a positive modulus. For the modular inverse, Python's built-in pow(a, -1, p) computes the inverse directly. We ran it on Python 3.14, where pow(3, -1, 7) gives 5. Check the Python documentation for your version before you rely on it.

Summary

Read the constraints first, then choose the type. Use long long for most totals, __int128 for large modular products, and reduce with norm so negative values give a valid remainder. Test with large inputs, because small tests hide overflow.