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
gcd(12, 8). Invariant: gcd(a,b) unchanged.
Live template
Line 1 active
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.
gcd(48, 18):48 % 18 = 12→gcd(18,12)→gcd(12,6)→gcd(6,0)→6.- Sieve up to 20: start boolean array true; mark multiples of 2,3,5,... from
p*p. Remaining trues are primes. - Modular pow:
pow(2, 10, 1000) == 24without building a giant int in a loop you forget to mod.
In code:
def gcd(a, b):while b: a, b = b, a % breturn 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.