Sefism.Competitive programming: Advanced

Tauseef Fayyaz

Chapter 02

Maths basics

Modular arithmetic, primes, divisors, fast powers and counting under a modulus: the number theory that appears from the easiest rounds upwards.

Modular arithmetic

Also called mod, modulo 1e9+7, 998244353, remainder

What: Working with remainders after division by a fixed number, usually 10^9 + 7 or 998244353. Addition, subtraction and multiplication can be reduced after every step.
Why: When an answer is huge, problems ask for it modulo a prime so it fits in 64 bits. Reducing often keeps every intermediate value small.

C++

const ll MOD = 1'000'000'007;
ll add(ll a, ll b) { return (a + b) % MOD; }
ll mul(ll a, ll b) { return a * b % MOD; }
ll sub(ll a, ll b) { return ((a - b) % MOD + MOD) % MOD; }

Watch out

Subtracting without adding MOD back, which leaves a negative remainder in C++.

Binary exponentiation

Also called fast power, modpow, exponentiation by squaring

What: Computing a^e in O(log e) multiplications by squaring the base and multiplying it in whenever the current bit of e is set.
Why: Powers with exponents up to 10^18 appear directly and inside modular inverses, and a simple loop would take far too long.

C++

ll power(ll base, ll e, ll mod) {
  ll result = 1;
  base %= mod;
  while (e > 0) {
    if (e & 1) result = result * base % mod;
    base = base * base % mod;
    e >>= 1;
  }
  return result;
}

Watch out

Forgetting to reduce base first, so the first square overflows when base is near 10^18.

GCD and LCM

Also called greatest common divisor, least common multiple, Euclid, std::gcd

What: The greatest common divisor is the largest number dividing both values, found by Euclid's algorithm in O(log n). The least common multiple is a / gcd(a, b) * b.
Why: Fractions, periodic events, array operations that keep a gcd invariant and many easy problems reduce to gcd reasoning.

C++

ll g = gcd(a, b);          // from <numeric>
ll l = a / gcd(a, b) * b;  // divide first to avoid overflow
ll arrayGcd = 0;
for (ll x : v) arrayGcd = gcd(arrayGcd, x);

Watch out

Computing lcm as a * b / gcd(a, b), which overflows before the division.

Sieve of Eratosthenes

Also called prime sieve, sieve, smallest prime factor

What: Marks every multiple of each prime as composite, finding all primes up to n in O(n log log n). Storing the smallest prime factor instead lets you factorise any number up to n quickly.
Why: When a problem asks about primes or divisors for many numbers up to 10^6 or 10^7, one sieve at the start beats testing each number.

C++

vector<bool> isPrime(n + 1, true);
isPrime[0] = isPrime[1] = false;
for (int i = 2; 1LL * i * i <= n; i++)
  if (isPrime[i])
    for (int j = i * i; j <= n; j += i)
      isPrime[j] = false;

Watch out

Sieving up to 10^9: the memory and time explode, so use trial division for a few big numbers instead.

Trial division and divisors

Also called prime factorisation, factorization, divisors, sqrt trick

What: Divide x by every candidate p while p * p <= x. Whatever is left above 1 is one last prime. Divisors come in pairs d and x / d, so listing them also takes O(sqrt x).
Why: For single numbers up to 10^12 or so, O(sqrt x) is fast, and the prime factorisation answers questions about divisors, gcds and squares.

C++

vector<ll> factors;
for (ll p = 2; p * p <= x; p++)
  while (x % p == 0) { factors.push_back(p); x /= p; }
if (x > 1) factors.push_back(x);  // one prime above sqrt

Watch out

Forgetting the final x > 1 check, which drops a large prime factor.

Parity and invariants

Also called odd even, invariant, observation

What: An invariant is a quantity an allowed operation never changes, such as the parity of a sum or the gcd of an array. If the start and the goal differ in it, the answer is impossible.
Why: Many easier problems look like simulations but are solved by one observation about what never changes.
Example: You may add 2 to any element. Can you make all elements equal? Only if every element has the same parity, because adding 2 never changes a number's parity.

Watch out

Simulating operations for minutes instead of asking what they can never change.

Modular inverse

Also called inverse mod p, Fermat's little theorem, division under mod

What: The number b^-1 such that b * b^-1 leaves remainder 1. When the modulus p is prime and b is not a multiple of p, it equals b^(p-2) mod p by Fermat's little theorem.
Why: Division is not allowed directly under a modulus, so averages, probabilities and binomial coefficients all need an inverse.

C++

// MOD is prime, so a^(MOD-2) is the inverse of a
ll inv(ll a) { return power(a, MOD - 2, MOD); }
ll divide(ll a, ll b) { return a * inv(b) % MOD; }

Watch out

Using Fermat when the modulus is not prime; then you need the extended Euclidean algorithm and gcd(b, m) = 1.

Binomial coefficients mod p

Also called nCr, combinations, factorials mod p, combinatorics

What: Precompute factorials and inverse factorials up to the largest n once, then each n choose r is three multiplications.
Why: Counting problems ask for the number of ways modulo a prime, often for many queries, and this answers each in O(1).

C++

ll fact[N], invFact[N];  // filled once at the start
// fact[i] = i! % MOD
// invFact[i] = power(fact[i], MOD - 2, MOD)
ll nCr(int n, int r) {
  if (r < 0 || r > n) return 0;
  return fact[n] * invFact[r] % MOD * invFact[n - r] % MOD;
}

Watch out

Precomputing only up to n when a formula needs factorials of n + m or 2n.

Go deeper