Mathematics for Competitive Programming

Whether an integer is even or odd. n is even if n mod 2 = 0, and odd otherwise. Parity is preserved under addition of even numbers and flips when adding an odd number.

An integer a divides b (written a | b) when there exists an integer k with b = a·k. Equivalently, b mod a = 0. Then a is a divisor of b and b is a multiple of a.

The sign indicates whether an integer is positive (> 0), negative (< 0), or zero. The product of two integers is positive when their signs agree and negative when they differ.

⌊x⌋ is the greatest integer ≤ x; ⌈x⌉ is the least integer ≥ x. For positive integers, ⌈a / b⌉ = (a + b − 1) / b using integer division.

log_b(x) is the exponent to which base b must be raised to obtain x. Useful for estimating sizes: a number x has about ⌊log2(x)⌋ + 1 bits.

Occurs when an arithmetic result exceeds the range of its integer type, wrapping around or causing undefined behavior. A 32-bit signed int holds up to about 2.1×10⁹; products of two such values often need 64-bit arithmetic.