C++ Module 19 – C++ for DSA and competitive programming

Overflow, __int128 and modular arithmetic

Pick integer widths from contest limits, reduce modulo 1,000,000,007 without negative results, and use __int128 and a ModInt type, run on two compilers.

Intermediate
20 minutes
Examples run with Clang 21.0.0, GCC 16.2.0 and Python 3.14.8
By MySmartCoPilot

Free: Choose the width from the constraints, before the code · Reduce after every operation, and repair the sign · A 128-bit type holds the products that 64 bits cannot · 2 more sections. With a pass: 2 in-depth parts and 3 interview answers, about 13 minutes.

What you will learn

Choose integer widths for contest constraints from worked bounds
Implement modular arithmetic without sign or overflow bugs
Use __int128 where it is available, and print it
Compute inverses and binomial coefficients modulo a prime

Before you start

What you’ll learn · Before you start

What you will learn

Choose integer widths for contest constraints from worked bounds
Implement modular arithmetic without sign or overflow bugs
Use __int128 where it is available, and print it
Compute inverses and binomial coefficients modulo a prime

Before you start

On this page

Overflow is what happens when a result does not fit its integer type. In C++ an int holds values up to 2,147,483,647, about 2.1 × 10⁹, and a long long up to about 9.2 × 10¹⁸. Signed overflow is undefined behaviour: What a program does when it breaks a rule for which the C++ standard sets no requirements, such as reading past the end of an array. The compiler may assume it never happens, so the result can change with the compiler and the optimisation level. More in “Object lifetime and undefined behaviour in C++”, while unsigned arithmetic wraps round silently, so neither tells you that an answer is wrong. Choose the width from the constraints before you write the code: the product of two values up to 10⁹ needs a long long, and the product of two values up to 10¹⁸ needs 128 bits, which GCC and Clang provide as compiler extension: A feature a compiler accepts beyond the C++ standard, such as GCC's __int128 or variable-length arrays. Code that relies on one builds only with the compilers that offer it, so portable code keeps it behind a feature test. More in “Portability across compilers, platforms and judges”. When an answer would be astronomically large, a problem asks for it modulo a prime, usually 1,000,000,007. Arithmetic in which every result is replaced by its remainder after division by a fixed number m, the modulus, so that every number stays below m; sums, differences and products then agree with the exact results modulo m. then keeps every number small, as long as you reduce after every operation and repair the negative remainders that C++’s % returns.

Choose the width from the constraints, before the code

Which type each product needs, and the loop that modular arithmetic keeps

Text description of the diagram

Four boxes connected by arrows, from top to bottom.

A value up to 10⁹, which an int holds, since an int reaches about 2.1 × 10⁹.
Multiplied by another value up to 10⁹, it becomes a product up to 10¹⁸, which a long long holds, since a long long reaches about 9.2 × 10¹⁸.
From there, one arrow multiplies by a value up to 10¹⁸ and leads to a product up to 10³⁶, which needs __int128, whose largest value is about 1.7 × 10³⁸.
The other arrow takes the remainder modulo 10⁹ + 7 and leads to a residue below 10⁹ + 7, which an int holds. An arrow from the residue back to the product box shows that multiplying two residues again gives a product up to about 10¹⁸, so with a reduction after every multiplication the numbers never leave long long.

widths.cpp C++ · widths.cpp

// How far each integer type reaches, and the most common overflow in contest code: a product computed in int
// before it is stored in a long long.
#include <climits>
#include <limits>
#include <print>

int main() {
  std::println("int:                {:>40}", INT_MAX);
  std::println("long long:          {:>40}", LLONG_MAX);
  std::println("unsigned long long: {:>40}", ULLONG_MAX);
  std::println("__int128:           {:>40}", std::numeric_limits<__int128>::max());

  long long big = 1'000'000'000;
  std::println("10^9 * 10^9 in long long: {}", big * big);

  int price = 1'000'000'000;  // in paise: 1 crore rupees
  int count = 3;
  long long total = price * count;  // the multiplication happens in int, before the conversion
  long long fixed = 1LL * price * count;  // 1LL makes the first product a long long
  std::println("int * int, stored in long long: {}", total);
  std::println("1LL * int * int:                {}", fixed);
}

Type limits, and an overflow caught by UndefinedBehaviorSanitizer Python · widths_session.py

from session import run

# Both compilers, then UndefinedBehaviorSanitizer, which reports the overflow where it happens.
run("""
clang++ -std=c++23 -Wall -Wextra widths.cpp -o widths && ./widths
g++-16 -std=c++23 -Wall -Wextra widths.cpp -o widths-gcc && ./widths-gcc
clang++ -std=c++23 -g -fsanitize=undefined widths.cpp -o widths-ub && ./widths-ub
""")

Output

$ clang++ -std=c++23 -Wall -Wextra widths.cpp -o widths && ./widths
int:                                              2147483647
long long:                               9223372036854775807
unsigned long long:                     18446744073709551615
__int128:            170141183460469231731687303715884105727
10^9 * 10^9 in long long: 1000000000000000000
int * int, stored in long long: -1294967296
1LL * int * int:                3000000000
$ g++-16 -std=c++23 -Wall -Wextra widths.cpp -o widths-gcc && ./widths-gcc
int:                                              2147483647
long long:                               9223372036854775807
unsigned long long:                     18446744073709551615
__int128:            170141183460469231731687303715884105727
10^9 * 10^9 in long long: 1000000000000000000
int * int, stored in long long: -1294967296
1LL * int * int:                3000000000
$ clang++ -std=c++23 -g -fsanitize=undefined widths.cpp -o widths-ub && ./widths-ub
int:                                              2147483647
long long:                               9223372036854775807
unsigned long long:                     18446744073709551615
__int128:            170141183460469231731687303715884105727
10^9 * 10^9 in long long: 1000000000000000000
widths.cpp:18:27: runtime error: signed integer overflow: 1000000000 * 3 cannot be represented in type 'int'
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior widths.cpp:18:27
int * int, stored in long long: -1294967296
1LL * int * int:                3000000000

Recorded with Python 3.14.8 on macOS 26 arm64. To run it yourself: mise exec python@3.14.8 -- python3 widths_session.py

The limits are the same on both compilers, and so is the classic bug at the end. price * count multiplies two int values, so the product overflows in int before it is converted to long long: both builds printed -1,294,967,296, and sanitizer: A compiler option, such as -fsanitize=address or -fsanitize=undefined, that builds extra checks into a program, so that memory errors and undefined behaviour are reported, with their source line, while it runs. More in “Finding memory bugs with AddressSanitizer and UBSan” reported the overflow at that line. 1LL * price * count multiplies in long long from the start. Neither compiler warned, even with -Wall -Wextra.

Work the bound out from the constraints instead of guessing:

Constraint	Largest value	Type that holds it
One value, up to 10⁹	10⁹	`int`
A sum of 2 × 10⁵ values up to 10⁹	2 × 10¹⁴	`long long`
A product of two values up to 10⁹	10¹⁸	`long long`
A sum of 2 × 10⁵ products of two values up to 10⁹	2 × 10²³	__int128, or reduce modulo a prime
A product of two values up to 10¹⁸	10³⁶	__int128 (up to about 1.7 × 10³⁸)

Checkpoint

Check: Choosing an integer width from the constraints

Question 1 of 2 int price = 1'000'000'000, count = 3; long long total = price * count; What did both builds of widths.cpp print for total?
Choose one answer.

2,147,483,647, the largest int -1,294,967,296 3,000,000,000 Nothing, because the compilers refused the line

Show the answer: Question 1 of 2

Answer: -1,294,967,296

The type of price * count depends only on price and count, both int, so the product overflows before it is converted to long long. Write 1LL * price * count, so that the multiplication itself happens in long long.
Question 2 of 2 n is at most 2 × 10⁵ and every value is at most 10⁹. Which type should hold the sum of all values?
Choose one answer.

long long __int128 int unsigned int

Show the answer: Question 2 of 2

Answer: long long

Work the bound out first: 2 × 10⁵ values of at most 10⁹ add up to at most 2 × 10¹⁴. That is the second row of the table, and a long long holds it.

Reduce after every operation, and repair the sign

factorial_mod.cpp C++ · factorial_mod.cpp

// 25! modulo 1,000,000,007, three ways: reduce at the end in unsigned long long, reduce at the end in long long,
// and reduce after every multiplication.
#include <print>

constexpr long long MOD = 1'000'000'007;

int main() {
  unsigned long long wrapped = 1;  // unsigned arithmetic wraps round modulo 2^64: defined, and silently wrong
  for (unsigned long long i = 1; i <= 25; ++i) {
    wrapped *= i;
    if (i == 20 || i == 21) std::println("unsigned after {}!: {}", i, wrapped);
  }
  std::println("unsigned, reduced at the end: {}", wrapped % MOD);

#ifdef SIGNED_AT_END
  long long product = 1;  // signed overflow is undefined behaviour: 21! does not fit
  for (long long i = 1; i <= 25; ++i) product *= i;
  std::println("signed, reduced at the end:   {}", product % MOD);
#endif

  long long reduced = 1;  // every product stays below MOD * 25, far inside long long
  for (long long i = 1; i <= 25; ++i) {
    reduced = reduced * i % MOD;
    if (i == 20 || i == 21) std::println("reduced after {}!: {}", i, reduced);
  }
  std::println("reduced after every step:     {}", reduced);
}

25! modulo 1,000,000,007, three ways Python · factorial_mod_session.py

from session import run

# Both compilers, with the values after 20! and 21!; then the signed version switched on, with UndefinedBehaviorSanitizer
# watching.
run("""
clang++ -std=c++23 -Wall -Wextra factorial_mod.cpp -o factorial_mod && ./factorial_mod
g++-16 -std=c++23 -Wall -Wextra factorial_mod.cpp -o factorial_mod-gcc && ./factorial_mod-gcc
clang++ -std=c++23 -g -fsanitize=undefined -DSIGNED_AT_END factorial_mod.cpp -o factorial_mod-ub && ./factorial_mod-ub
""")

Output

$ clang++ -std=c++23 -Wall -Wextra factorial_mod.cpp -o factorial_mod && ./factorial_mod
unsigned after 20!: 2432902008176640000
unsigned after 21!: 14197454024290336768
unsigned, reduced at the end: 332217180
reduced after 20!: 146326063
reduced after 21!: 72847302
reduced after every step:     440732388
$ g++-16 -std=c++23 -Wall -Wextra factorial_mod.cpp -o factorial_mod-gcc && ./factorial_mod-gcc
unsigned after 20!: 2432902008176640000
unsigned after 21!: 14197454024290336768
unsigned, reduced at the end: 332217180
reduced after 20!: 146326063
reduced after 21!: 72847302
reduced after every step:     440732388
$ clang++ -std=c++23 -g -fsanitize=undefined -DSIGNED_AT_END factorial_mod.cpp -o factorial_mod-ub && ./factorial_mod-ub
unsigned after 20!: 2432902008176640000
unsigned after 21!: 14197454024290336768
unsigned, reduced at the end: 332217180
factorial_mod.cpp:17:47: runtime error: signed integer overflow: 2432902008176640000 * 21 cannot be represented in type 'long long'
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior factorial_mod.cpp:17:47
signed, reduced at the end:   332217180
reduced after 20!: 146326063
reduced after 21!: 72847302
reduced after every step:     440732388

Recorded with Python 3.14.8 on macOS 26 arm64. To run it yourself: mise exec python@3.14.8 -- python3 factorial_mod_session.py

20! is 2,432,902,008,176,640,000, the last factorial that fits in a long long; 21! is about 5.1 × 10¹⁹. Reducing only at the end therefore gives 332,217,180 instead of the right 440,732,388. The unsigned version is defined behaviour and still wrong, because it reduced the remainder of 25! modulo 2⁶⁴, not 25! itself. The signed version overflowed at 21, as the sanitizer reported. Reducing after every multiplication keeps each product below MOD × 25, so the right answer comes out on both compilers. The choice of 1,000,000,007 is deliberate: it is prime, two The remainder a number leaves modulo m, a value from 0 to m − 1 that stands for every number with the same remainder: modulo 1,000,000,007, the numbers 3 and 1,000,000,010 have the same residue, 3. add up to less than 2,147,483,647, and two residues multiply to about 10¹⁸, below the long long limit. Modular arithmetic works for sums, differences and products this way, reduced at every step. Step through both loops with the values the run printed:

Interactive · step by step 25! modulo 1,000,000,007, reduced at the end or at every step Step through both loops side by side. The left keeps the whole product and reduces once; the right reduces after every multiplication.

The drawing shows the whole scene; its 6 steps are listed below.

Every step as text

Two loops. Both loops multiply 1 × 2 × … × 25. The left keeps the whole product in an unsigned long long, which reaches about 1.8 × 10¹⁹, and reduces once at the end; the right reduces modulo 1,000,000,007 after every multiplication.
After 20!. After 20 multiplications the left holds 20! = 2,432,902,008,176,640,000, still below the limit. The right holds its remainder, 146,326,063.
21! wraps. 21! is about 5.1 × 10¹⁹, past the limit, so the unsigned product wraps round modulo 2⁶⁴ to 14,197,454,024,290,336,768. Nothing reports it: unsigned arithmetic is defined to wrap.
The residue stays small. The right multiplies its residue instead: 146,326,063 × 21 = 3,072,847,323, far inside long long, and reduces it to 72,847,302. Every product of this loop stays below MOD × 25.
One reduction, too late. After 25 the left reduces its wrapped product once and gets 332,217,180. That is the remainder of the wrapped value, not of 25!, so it is wrong, and it looks like any other answer.
The right answer. The right ends with 440,732,388, which is 25! modulo 1,000,000,007, on both compilers. Reducing after every multiplication kept every number small enough to be exact.

The remainder keeps the sign of the dividend

negative_mod.cpp C++ · negative_mod.cpp

// In C++ the remainder takes the sign of the dividend, so a difference of two residues can come out negative.
#include <print>

constexpr long long MOD = 1'000'000'007;

// Brings any long long into [0, MOD).
long long norm(long long x) {
  x %= MOD;
  return x < 0 ? x + MOD : x;
}

int main() {
  std::println("-7 / 3 = {}, -7 % 3 = {}", -7 / 3, -7 % 3);  // division truncates towards zero
  std::println("7 / -3 = {}, 7 % -3 = {}", 7 / -3, 7 % -3);

  // Two counts kept modulo MOD: the true counts are 1,000,000,010 and 5, so the true difference is 1,000,000,005.
  long long a = 1'000'000'010 % MOD;  // 3
  long long b = 5;
  std::println("(a - b) % MOD:               {}", (a - b) % MOD);
  std::println("((a - b) % MOD + MOD) % MOD: {}", ((a - b) % MOD + MOD) % MOD);
  std::println("norm(a - b):                {}", norm(a - b));
  std::println("norm(-1):                   {}", norm(-1));
}

Remainders of negative numbers, and the repair Python · negative_mod_session.py

from session import run

run("""
clang++ -std=c++23 -Wall -Wextra negative_mod.cpp -o negative_mod && ./negative_mod
g++-16 -std=c++23 -Wall -Wextra negative_mod.cpp -o negative_mod-gcc && ./negative_mod-gcc
""")

Output

$ clang++ -std=c++23 -Wall -Wextra negative_mod.cpp -o negative_mod && ./negative_mod
-7 / 3 = -2, -7 % 3 = -1
7 / -3 = -2, 7 % -3 = 1
(a - b) % MOD:               -2
((a - b) % MOD + MOD) % MOD: 1000000005
norm(a - b):                1000000005
norm(-1):                   1000000006
$ g++-16 -std=c++23 -Wall -Wextra negative_mod.cpp -o negative_mod-gcc && ./negative_mod-gcc
-7 / 3 = -2, -7 % 3 = -1
7 / -3 = -2, 7 % -3 = 1
(a - b) % MOD:               -2
((a - b) % MOD + MOD) % MOD: 1000000005
norm(a - b):                1000000005
norm(-1):                   1000000006

Recorded with Python 3.14.8 on macOS 26 arm64. To run it yourself: mise exec python@3.14.8 -- python3 negative_mod_session.py

Integer division truncates towards zero, and the remainder keeps the sign of the dividend: -7 / 3 is -2 and -7 % 3 is -1. With residues that means a difference such as (a - b) % MOD can come out negative, here -2 where the true difference of the counts, reduced, is 1,000,000,005. Adding MOD and reducing again repairs it, and a small norm function does both for any long long. Take that step after every subtraction, and once on input that may be negative.

Checkpoint

Check: Reducing at every step and repairing the sign

Question 1 of 2 Which loop computes 25! modulo 1,000,000,007 correctly with long long r = 1?
Choose one answer.

for (long long i = 1; i <= 25; ++i) r *= i; then r %= MOD; The same loop with unsigned long long r, reduced once at the end for (long long i = 1; i <= 25; ++i) r = r * (i % MOD); for (long long i = 1; i <= 25; ++i) r = r * i % MOD;

Show the answer: Question 1 of 2

Answer: for (long long i = 1; i <= 25; ++i) r = r * i % MOD;

Reduce the result of every multiplication. The residue stays below 1,000,000,007, so the next product stays far inside long long, and the remainder at the end is the remainder of the true product.
Question 2 of 2 a = 2 and b = 9 are residues modulo MOD = 1,000,000,007. What is ((a - b) % MOD + MOD) % MOD?
Type a number.
Your answer

A hint

(2 - 9) % MOD keeps the sign of the dividend.

Show the answer: Question 2 of 2

Answer: 1000000000

2 - 9 is -7, and -7 % MOD is -7, because the remainder keeps the sign of the dividend. Adding MOD gives 1,000,000,000, which is already in [0, MOD), so the last % leaves it as it is.

A 128-bit type holds the products that 64 bits cannot

int128_print.cpp C++ · int128_print.cpp

// A product of two values near 10^18 needs about 120 bits. __int128 holds it exactly; printing it needs either a
// helper or std::print, because the iostreams have no operator<< for it.
#include <algorithm>
#include <print>
#include <string>
#ifdef USE_STREAM
#include <iostream>
#endif

// Decimal digits of an unsigned 128-bit value, last digit first, then reversed.
std::string to_string128(unsigned __int128 x) {
  if (x == 0) return "0";
  std::string digits;
  for (; x > 0; x /= 10) digits += static_cast<char>('0' + static_cast<int>(x % 10));
  std::ranges::reverse(digits);
  return digits;
}

std::string to_string128(__int128 x) {
  // The magnitude, computed in unsigned arithmetic so that it works for every value.
  unsigned __int128 magnitude = x < 0 ? -static_cast<unsigned __int128>(x) : static_cast<unsigned __int128>(x);
  return (x < 0 ? "-" : "") + to_string128(magnitude);
}

int main() {
  const long long a = 999'999'999'999'999'989;  // the largest prime below 10^18
  const long long b = 999'999'999'999'999'877;
  const long long m = 1'000'000'000'000'000'003;  // the smallest prime above 10^18

  __int128 product = static_cast<__int128>(a) * b;  // widen one side first, then multiply
  std::println("a * b, helper:      {}", to_string128(product));
  std::println("a * b, std::print:  {}", product);
  std::println("a * b mod m:        {}", static_cast<long long>(product % m));
  std::println("a * b in 64 bits:   {}", static_cast<unsigned long long>(a) * static_cast<unsigned long long>(b));
#ifdef USE_STREAM
  std::cout << product << '\n';
#endif
}

A 36-digit product, printed two ways, and the stream that refuses it Python · int128_print_session.py

from session import run

# Both compilers; then the same program with std::cout << product switched on: the first error of each compiler.
run("""
clang++ -std=c++23 -Wall -Wextra int128_print.cpp -o int128_print && ./int128_print
g++-16 -std=c++23 -Wall -Wextra int128_print.cpp -o int128_print-gcc && ./int128_print-gcc
clang++ -std=c++23 -DUSE_STREAM int128_print.cpp -o int128_stream 2>&1 | grep -m1 error
g++-16 -std=c++23 -DUSE_STREAM int128_print.cpp -o int128_stream-gcc 2>&1 | grep -m1 error
""")

Output

$ clang++ -std=c++23 -Wall -Wextra int128_print.cpp -o int128_print && ./int128_print
a * b, helper:      999999999999999866000000000000001353
a * b, std::print:  999999999999999866000000000000001353
a * b mod m:        1764
a * b in 64 bits:   8046803363077555529
$ g++-16 -std=c++23 -Wall -Wextra int128_print.cpp -o int128_print-gcc && ./int128_print-gcc
a * b, helper:      999999999999999866000000000000001353
a * b, std::print:  999999999999999866000000000000001353
a * b mod m:        1764
a * b in 64 bits:   8046803363077555529
$ clang++ -std=c++23 -DUSE_STREAM int128_print.cpp -o int128_stream 2>&1 | grep -m1 error
int128_print.cpp:36:13: error: use of overloaded operator '<<' is ambiguous (with operand types 'ostream' (aka 'basic_ostream<char>') and '__int128')
$ g++-16 -std=c++23 -DUSE_STREAM int128_print.cpp -o int128_stream-gcc 2>&1 | grep -m1 error
int128_print.cpp:36:13: error: ambiguous overload for 'operator<<' (operand types are 'std::ostream' {aka 'std::basic_ostream<char>'} and '__int128')

Recorded with Python 3.14.8 on macOS 26 arm64. To run it yourself: mise exec python@3.14.8 -- python3 int128_print_session.py

__int128 is an extension of GCC and Clang, not part of the C++ standard, and GCC provides it only on targets with a 128-bit integer mode, which every 64-bit judge has; Microsoft’s compiler has no such type. Widen before you multiply: static_cast<__int128>(a) * b keeps all 36 digits of the product, and reducing it modulo m gives the exact remainder. Here a and b are m - 14 and m - 126, so the remainder must be 14 × 126 = 1,764, which is what both compilers printed. Printing is the awkward part. The iostreams have no operator<< for __int128, and both compilers rejected std::cout << product; std::print accepted it with both of these standard libraries, and a short helper that collects decimal digits works everywhere, including the older libraries some judges use. The lesson on judge environments lists which compilers each judge runs.

Checkpoint

Check: __int128 products and printing them

Question 1 of 2 a and b are long long values near 10¹⁸. Which expression keeps all 36 digits of their product?
Choose one answer.

static_cast<__int128>(a) * b static_cast<__int128>(a * b) static_cast<unsigned long long>(a) * b __int128 p = a * b;

Show the answer: Question 1 of 2

Answer: static_cast<__int128>(a) * b

Widen before you multiply. The product of two values near 10¹⁸ needs about 120 bits, and only a multiplication in __int128 keeps all of it; its remainder modulo m was the exact 1,764.
Question 2 of 2 A judge runs an older standard library than the two of this lesson. Which way of printing an __int128 works there for sure?
Choose one answer.

std::cout << value std::print with "{}" Casting it to long long and printing that A helper that collects the decimal digits into a string

Show the answer: Question 2 of 2

Answer: A helper that collects the decimal digits into a string

std::print accepted __int128 with both libraries of this lesson, and a short helper that builds the digits works everywhere, including older libraries, which is why contest templates carry one.

Five tools for larger problems, in one line each

Tool	What it does
A ModInt type	Wraps a residue, so that every operator reduces and repairs signs for you.
Fermat’s little theorem	Turns division by x into multiplication by x raised to MOD - 2, for a prime MOD.
Factorial tables	Answer each binomial coefficient with two multiplications after O(n) preparation.
A 64-bit modulus	Needs __int128 or a doubling loop for every multiplication of two residues.
__builtin_mul_overflow	Multiplies and reports whether the result overflowed, before anything goes wrong.

The first three keep modular arithmetic exact and short to write; the last two deal with products that do not fit in 64 bits.

Checkpoint

Check: The tools for larger problems

One question You must divide by x modulo the prime 1,000,000,007. Which tool of the table turns the division into a multiplication?
Choose one answer.

__builtin_mul_overflow Fermat's little theorem Factorial tables A ModInt type

Show the answer: One question

Answer: Fermat's little theorem

Modular arithmetic has no division of its own. For a prime modulus, Fermat's little theorem turns division by x into a multiplication by x raised to MOD - 2.

Practise

The questions follow your answers: a miss brings an easier one, and every choice explains itself.

ModInt and binomials modulo a prime, built and tested Pro: opens with a Pro, Premium or Ultimate pass

A small class removes the whole family of reduction and sign bugs, and the same ideas give modular division and binomial coefficients. This part builds the class, shows the modulus that breaks division, measures the fast way to prepare inverse factorials, and ends with an exercise.

In this part:

A ModInt type that cannot go negative
Inverses with Fermat’s little theorem, and the modulus that breaks them
When the modulus is not prime: the extended Euclidean algorithm, worked
Inverse factorials in one pass, measured
Your turn: binomials, grid paths and Catalan numbers

7 runnable examples (C header, C++, Python) · about 8 minutes

Opening this part with your pass…

This part opens with any MySmartCoPilot pass.

Pro pass · 1 week₹79$2.99
30 days₹179$5.99
1 year₹1,699$45

One payment; a pass never renews. The price shown is the total you pay: no fees or charges are added at checkout.

Choose a pass I have a licence key

It also opens every other in-depth part in Learn and every Pro tool. Sales are final, except where the law gives you a right to withdraw, for example in the EU and the UK (refund policy).

Products that do not fit: __int128, mulmod and overflow checks Pro: opens with a Pro, Premium or Ultimate pass

Some problems use a modulus near 10¹⁸, or ask whether a product passes a limit, and then even the reduction overflows 64 bits. This part compares three ways to multiply modulo a 64-bit prime, reproduces a printing bug that only the smallest __int128 triggers, and shows three checks that decide before multiplying.

In this part:

Three ways to multiply modulo a 64-bit prime, measured
Printing the smallest 128-bit value: a failure reproduced
Checking a product before it overflows
Where each tool is available, on the two pinned compilers

6 runnable examples (C++, Python) · about 7 minutes

Opening this part with your pass…

This part opens with any MySmartCoPilot pass.

Pro pass · 1 week₹79$2.99
30 days₹179$5.99
1 year₹1,699$45

One payment; a pass never renews. The price shown is the total you pay: no fees or charges are added at checkout.

Choose a pass I have a licence key

It also opens every other in-depth part in Learn and every Pro tool. Sales are final, except where the law gives you a right to withdraw, for example in the EU and the UK (refund policy).

Interview questions

Fresher · Warm-up

Why do so many programming problems ask for the answer modulo 1,000,000,007?

Because the true answers are too large for any integer type, and this modulus keeps the arithmetic simple. It is prime, so every value that is not a multiple of it has an inverse, and division works by Fermat's little theorem. It is small enough that two residues add up to less than 2,147,483,647, the int limit, and multiply to about 10^18, below the long long limit of about 9.2 × 10^18, so each operation needs at most a long long before it is reduced again. And it is large enough that a solution which is wrong by a small amount almost never matches the expected remainder by chance.
Fresher to mid

A solution counts good arrangements as total - bad, with both counts reduced modulo 1,000,000,007, and prints (total - bad) % MOD. A few tests fail with a negative output. Explain why, fix it, and say how you would make this kind of bug impossible in the rest of the code.

Model answer, Pro. Model answers open with any pass; prices are in the notice on this page. First step and follow-ups
Mid to senior

Your code multiplies two residues of a modulus near 10^18 with __int128 and passes on the judge. The same code must now also build with Microsoft's compiler. What do you replace the multiplication with, what does each option cost, and how do you prove the replacement is right?

Model answer, Pro. First step and follow-ups
Mid to senior

A problem asks for a / b modulo 1,000,000,000, which is not prime. A teammate computes b to the power MOD - 2 as the inverse, as they always do. What goes wrong, when does an answer exist at all, and how do you compute it?

Model answer, Pro. First step and follow-ups

Key takeaways

Work out the largest value from the constraints, then pick the type: 2.1 × 10⁹ for int, 9.2 × 10¹⁸ for long long.
Multiply in the wide type from the start: 1LL * a * b, never a * b stored in a long long.
Reduce after every operation, and add MOD after a subtraction, because % keeps the sign of the dividend.
__int128 holds 128-bit products with GCC and Clang; print it with a helper or std::print, never a stream.

References

Working Draft, Programming Languages: C++ (N4950), fundamental types and multiplicative operators (ISO/IEC JTC1/SC22/WG21)
128-bit Integers (GCC manual) (GNU Project)
Built-in Functions to Perform Arithmetic with Overflow Checking (GCC manual) (GNU Project)
Clang Language Extensions (checked arithmetic builtins) (LLVM Project)
Data Type Ranges (Microsoft C++) (Microsoft)
AtCoder Library documentation (modint) (AtCoder)
x86 Options (GCC manual), long double formats (GNU Project)
Writing ARM64 code for Apple platforms (Apple)
UndefinedBehaviorSanitizer (Clang documentation) (LLVM Project)

Report a problem with this lesson

In this module: C++ for DSA and competitive programming

Online judge C++ compilers, flags and limits Free lesson, Pro answers: 20 minutes
A clean C++ contest template, and habits to avoid Free core, Pro depth: 8 of 20 minutes free
Fast C++ input and output for online judges Free core, Pro depth: 8 of 20 minutes free
The STL toolkit for DSA in C++ Free core, Pro depth: 8 of 20 minutes free
Custom comparators and strict weak ordering Free core, Pro depth: 8 of 20 minutes free
C++ binary search: lower_bound and partition_point Free core, Pro depth: 7 of 20 minutes free
Overflow, __int128 and modular arithmetic Free core, Pro depth: 7 of 20 minutes free
C++ unordered_map: custom hashes and anti-hash tests Free core, Pro depth: 8 of 20 minutes free
Order-statistics trees with __gnu_pbds (GCC only) Free core, Pro depth: 8 of 20 minutes free
Deep recursion, stack limits and iterative DFS Free core, Pro depth: 7 of 20 minutes free
Stress testing contest solutions in C++ Free core, Pro depth: 11 of 30 minutes free

Your country

Overflow, __int128 and modular arithmetic

What you will learn

Before you start

What you will learn

Before you start

Choose the width from the constraints, before the code

Reduce after every operation, and repair the sign

The remainder keeps the sign of the dividend

A 128-bit type holds the products that 64 bits cannot

Five tools for larger problems, in one line each

Practise

ModInt and binomials modulo a prime, built and tested Pro: opens with a Pro, Premium or Ultimate pass

Products that do not fit: __int128, mulmod and overflow checks Pro: opens with a Pro, Premium or Ultimate pass

Interview questions

Why do so many programming problems ask for the answer modulo 1,000,000,007?

A solution counts good arrangements as total - bad, with both counts reduced modulo 1,000,000,007, and prints (total - bad) % MOD. A few tests fail with a negative output. Explain why, fix it, and say how you would make this kind of bug impossible in the rest of the code.

Your code multiplies two residues of a modulus near 10^18 with __int128 and passes on the judge. The same code must now also build with Microsoft's compiler. What do you replace the multiplication with, what does each option cost, and how do you prove the replacement is right?

A problem asks for a / b modulo 1,000,000,000, which is not prime. A teammate computes b to the power MOD - 2 as the inverse, as they always do. What goes wrong, when does an answer exist at all, and how do you compute it?

Key takeaways

References

Related tools