Math & Bits

Math & Number Theory

GCD, primes, modular arithmetic and digit manipulation.

Medium, about 75 minutes to practise.

1Understand

The idea

Euclid's algorithm finds the GCD in O(log n): gcd(a, b) = gcd(b, a % b). The sieve of Eratosthenes lists all primes up to n in O(n log log n). For huge answers, take % MOD after every multiplication and use pow(base, exp, mod) for fast modular powers. Pull digits off a number with % 10 and // 10.

Intuition

Euclid's algorithm finds GCD in O(log n): gcd(a, b) = gcd(b, a % b). LCM follows from a // gcd * b (careful with overflow order). The sieve of Eratosthenes lists primes up to n in O(n log log n).

For huge answers, take % MOD after every multiplication and use pow(base, exp, MOD) for modular exponentiation. Pull digits with % 10 and // 10.

Number-theory problems in interviews are usually these building blocks composed, not deep proofs.

What you will be able to do

  • Apply the sieve of Eratosthenes
  • Take modulo at every step

When to use it

  • Primes up to n
  • Answer modulo 10^9+7
  • Reverse or sum digits without strings

2See it

Walkthrough

GCD by Euclid

a=12, b=8, replace a with b, b with a%b.

1 / 5

12
8
01

gcd(12, 8). Invariant: gcd(a,b) unchanged.

while b:

Live template

Line 1 active

1sieve = [True] * (n + 1)
2for p in range(2, int(n ** 0.5) + 1):
3 if sieve[p]:
4 for m in range(p * p, n + 1, p): sieve[m] = False

Complexity: time O(n log log n), space O(n)

GCD is O(log n). Sieve is O(n log log n) time and O(n) space, fine for n ≤ 10⁷ in contests, heavy for much larger; then factor individually in O(√n). Always mod inside loops for combinatorics counts.

Read the walkthrough as text

GCD and sieve sketch.

  1. gcd(48, 18): 48 % 18 = 12 → gcd(18,12) → gcd(12,6) → gcd(6,0) → 6.
  2. Sieve up to 20: start boolean array true; mark multiples of 2,3,5,... from p*p. Remaining trues are primes.
  3. Modular pow: pow(2, 10, 1000) == 24 without building a giant int in a loop you forget to mod.

In code:

  • def gcd(a, b):
  • while b: a, b = b, a % b
  • return a

3Recognise it

Kinds of problems (11)

Same pattern, different surfaces. Each row is a problem shape you should recognise, not only the first walkthrough example.

  • GCD / LCM

    Example. Greatest common divisor of two numbers.

    How. Euclidean: while b: a, b = b, a % b.

  • Sieve of Eratosthenes

    Example. All primes up to n.

    How. Cross off multiples from p*p; iterate p to √n.

  • Fast power (modular exponentiation)

    Example. Compute a^b mod m.

    How. Square-and-multiply: halve exponent, square base; multiply when bit set.

  • Digit manipulation

    Example. Sum or reverse digits without string conversion.

    How. while n: digit = n % 10; n //= 10; accumulate.

  • Overflow-safe arithmetic and modulo

    Example. Products under mod 10^9+7.

    How. Mod after each multiply/add; use long long or Python ints freely.

  • Lines through points (slope as a reduced fraction)

    Example. Count unique lines through point pairs.

    How. Normalise slope as (dx,dy) gcd-reduced with sign canonicalisation.

  • Counting squares or rectangles from points

    Example. Count axis-aligned rectangles from point set.

    How. Map (x,y); for diagonal pair check other two corners exist.

  • Combinatorics modulo 10^9 + 7

    Example. n choose k mod M.

    How. Precompute factorials and inverse factorials modulo M.

  • Simulation with a repeating cycle

    Example. Find state after huge steps using cycle detection.

    How. Simulate until (state, index) repeats; skip full cycles on remainder.

  • Prime factorisation by division

    Example. Factor n into primes.

    How. Trial divide d from 2 while d*d ≤ n; count multiplicity.

  • Reservoir sampling and shuffling (given random draws)

    Example. Pick k uniform random items from stream.

    How. Reservoir: keep k slots; replace with probability k/i at step i.

Common mistakes

Failure modes the tutor watches for. Open the Common mistake tab in the walkthrough to watch one fail live.

  • Slow primality

    Why it happens. Try every integer up to n for primality.

    How it fails. is_prime(n) loop d in 2..n-1, O(n) per test, TLE on 10⁶.

    Fix. Trial divide to √n, or sieve for many queries up to N.

  • Late modulo

    Why it happens. Mod once at the end keeps intermediates exact.

    How it fails. Product of factorials overflows 64-bit then mod, wrong in fixed-width judges.

    Fix. Mod after each multiply/add in combinatorics chains.

  • Negative digits

    Why it happens. -7 % 10 feels like -7 in other languages.

    How it fails. Python n=-123: n%10 is 7 with // toward -∞, digit loop must use positive mod recipe.

    Fix. Use abs(n) for digits or normalise modulo to [0, m) explicitly.

4Check yourself

Concept check

A short quiz on this lesson before you practise. Optional, and it does not gate coding.

Ready to practise?

Mastery comes from solving. The lesson is optional context.

All lessons