Skip to content
Tutorials Center
My learning

Topics

Lesson 25 of 63 ยท Math for Contests

Gaussian Elimination, Mobius and Inclusion-Exclusion for Contests

Contest templates in Python: solve linear systems mod p and over GF(2), count solutions, and count pairs with a given gcd with Mobius in O(n^(2/3)).

Two families of math problems keep coming back in contests. The first says "we have some equations; how many solutions are there, or what is the unique one?" The second says "count pairs or tuples whose gcd is 1 (or g)", where n is up to 10^9 and a loop over all pairs is out of the question.

The first family is solved by Gaussian elimination, usually modulo a prime or over bits. The second by the Mobius function and inclusion-exclusion, combined with the trick of grouping equal values of n // d. This lesson gives you contest-ready templates for both, each tested against a brute force. The theory is in the DSA lessons Gaussian Elimination and Inclusion-Exclusion, Totient and Mobius; here we focus on what you type during a contest and where it breaks.

Linear systems modulo a prime: solution counting

In a contest the system usually has a modulus p (often 998244353) and the question is one of three: find the solution, say whether one exists, or count solutions. All three come out of one elimination if you track the rank:

  • Eliminate column by column; each column either gets a pivot or becomes a free variable.
  • After elimination, any row of the form 0 = non-zero means no solution.
  • Otherwise the number of solutions is p^(number of free variables), and setting every free variable to 0 gives one solution.
Python Linear system mod p: solution, rank and count

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Notes for contests: the cost is O(m * n * min(m, n)), so a 500 x 500 system is fine in C++ but slow in Python; vectorize with lists or reduce the problem size first. The determinant mod p comes from the same loop: multiply the pivots before normalizing the row, and negate for each swap.

Systems over bits: lights-out style problems

If each equation is "XOR of some variables equals 0 or 1", use integers as bit-rows. A classic: a grid of lamps, pressing a lamp toggles itself and its neighbors; can all lamps be turned off, and with how many presses at minimum?

Variables: whether each cell is pressed. Equation for each cell: XOR of presses of the cell and its neighbors equals the cell's current state. The minimum number of presses needs a search over the free variables (usually few): enumerate all 2^f assignments and take the cheapest.

Python Lights-out on a small grid via GF(2) elimination

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The same pattern solves "choose a subset of numbers whose XOR is k" (rows are numbers, columns are bits).

Counting coprime pairs for huge n

Recall the formula: the number of ordered pairs (a, b) with 1 <= a, b <= n and gcd(a, b) = 1 is

TEXT
sum over d of  mu(d) * (n // d)^2

For n = 10^9 we cannot sieve mu to n. Two tricks fix it:

  1. Sieve mu once up to L = n^(2/3) (about 10^6) and keep a prefix sum M(x) = mu(1) + ... + mu(x).
  2. The value n // d takes only about 2 * sqrt(n) distinct values. Group all d with the same quotient: they form a block [l, r], contributing (M(r) - M(l-1)) * (n // l)^2.

For d > L we need M(x) at arbitrary large x; it comes from the identity sum for d = 1..x of M(x // d) = 1, which gives M(x) = 1 - sum for d = 2..x of M(x // d), again over blocks with memoization. That makes the whole count O(n^(2/3)).

Python Coprime pairs: Mobius with block grouping and memoized M(x)

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The ratio for n = 10^9 is close to 6 / pi^2 = 0.6079....

Pairs with gcd exactly g

Pairs with gcd(a, b) = g correspond one-to-one with coprime pairs (a/g, b/g) in the range up to n // g. So the count is coprime_pairs(n // g). And the number of pairs with gcd >= 2 is n^2 - coprime_pairs(n).

A checklist for these problems

Clue in the statement Tool
"number of solutions" to equations mod p elimination, answer p^free or 0
"XOR of chosen items", toggling puzzles GF(2) elimination, bitmask rows
Large equations count (>500) reduce structure first, bitsets in C++
"pairs with gcd = 1", n up to 10^9 Mobius with block grouping, O(n^(2/3))
"number of integers not divisible by any of k given primes" inclusion-exclusion over subsets (2^k terms)
Count with sums of divisors Mobius inversion or sieve over multiples

Common mistakes: forgetting the 0 = non-zero check after elimination, normalizing the pivot before the determinant, using n // d loops without grouping (that is O(n)), and using floating-point n ** (2/3) without rounding.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. A consistent linear system mod p with 5 variables has rank 3. How many solutions does it have?

    The 2 non-pivot columns are free variables, each of which can take any of p values, giving p^2 solutions.
  2. 2. Which test shows that a linear system has no solution after elimination?

    Such a row says 0 = c with c non-zero, a contradiction. A missing pivot only means a free variable.
  3. 3. Why group the values of d by n // d in the Mobius sum?

    All d in a block share the same quotient, so one prefix-sum difference of mu handles the whole block.
  4. 4. How many ordered pairs (a, b) with 1 <= a, b <= n have gcd exactly g?

    Divide both numbers by g: the pairs correspond to coprime pairs up to n // g.

Summary

  • Eliminate mod p while tracking pivots: a contradictory row means 0 solutions, otherwise the count is p^(free variables).
  • Over bits, store rows as integers and combine them with XOR; enumerate the few free variables to minimize the number of presses.
  • Coprime pairs up to n: sum of mu(d) * (n // d)^2, grouped into blocks of equal n // d, with a memoized Mertens function for O(n^(2/3)).
  • Gcd exactly g reduces to coprime pairs up to n // g.
  • Always test templates against brute force on tiny inputs.

Next: nCr Mod p with Lucas, Catalan and Stirling Numbers