Mathematics for Competitive Programming

Parity of an integer

Whether an integer is even or odd. n is even if n mod 2 = 0, and odd otherwise. Parity is preserved under addition of ev

Divisibility

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

Sign of an integer

The sign indicates whether an integer is positive (> 0), negative (< 0), or zero. The product of two integers is positiv

Floor and ceiling

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

Logarithm as an exponent

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 ⌊