Number Theory for Competitive Programming

Interview-style DSA rarely asks you to compute $\binom{1000}{500} \bmod (10^9 + 7)$ or find every prime under ten million — but competitive programming asks for exactly that, constantly. This lesson is the number theory toolkit that shows up over and over in contests: it’s less about clever tricks and more about a handful of building blocks you’ll reuse in dozens of problems.

What you’ll learn

• GCD, LCM, and Euclid’s algorithm — the foundation everything else builds on.
• Modular arithmetic rules for add/subtract/multiply, and why division needs special handling.
• Fast modular exponentiation — computing $a^b \bmod m$ in $O(\log b)$ instead of $O(b)$.
• Modular inverse via Fermat’s little theorem, so division under a modulus becomes multiplication.
• The Sieve of Eratosthenes for finding every prime up to $n$, plus a pointer to the linear sieve.
• Prime factorization and combinatorics mod p with precomputed factorials — answering $\binom{n}{k} \bmod p$ in $O(1)$ per query.

The cue

You are looking at number theory when…

• The answer must be returned modulo $10^9 + 7$. That is not decoration — it means the true answer is astronomically large, so you must never materialise it, and every intermediate multiplication needs a % MOD.
• The problem involves divisibility, factors, multiples, primes, or coprimality — LC 204, 1071, 1201, 2413.
• You need $a^b$ where b is enormous ($10^{18}$), or nCr mod p for large n.
• Constraints are in the millions and the operation is “for every number up to n, find its smallest prime factor / count its divisors” — that is a sieve, not a per-number loop.
• The statement mentions cycles that repeat every k steps, which is modular arithmetic in disguise.

The reframe: these problems are not about clever algorithms so much as knowing which identity turns an impossible computation into a cheap one — Euclid for gcd, binary exponentiation for powers, Fermat’s little theorem for division under a modulus, a sieve for bulk primality. Each replaces a linear or exponential loop with a logarithmic or amortised one.

Reach for something else when the “number theory” is really just arithmetic simulation (that is simulation), when the modulus is not prime — Fermat’s inverse silently produces garbage, and you need the extended Euclidean algorithm instead — or when only one primality test is needed, where $O(\sqrt n)$ trial division beats building a sieve.

GCD, LCM, and Euclid’s algorithm

The greatest common divisor of two numbers can be found without ever listing their factors: gcd(a, b) == gcd(b, a % b), and the recursion bottoms out the moment the second argument hits 0.

gcd_lcm.py

import math
 
 
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a
 
 
def lcm(a, b):
    return a * b // gcd(a, b)
 
 
print("gcd(48, 18):", gcd(48, 18))            # 6
print("lcm(4, 6):", lcm(4, 6))                # 12
print("math.gcd matches:", math.gcd(48, 18))  # stdlib version -- use this in practice
print("math.lcm matches:", math.lcm(4, 6))    # Python 3.9+

diagram Euclid's algorithm: gcd(48, 18) shrinks to 0 in three steps mermaid

  graph LR
    N0["gcd(48, 18)"] --> N1["gcd(18, 12)"]
    N1 --> N2["gcd(12, 6)"]
    N2 --> N3["gcd(6, 0) = 6"]

Each step replaces (a, b) with (b, a % b), and a % b is always smaller than b — so the pair shrinks fast (logarithmically) no matter how large a and b start out.

Modular arithmetic rules

Contest answers are usually taken $\bmod\ p$ for a large prime like $10^9 + 7$, both to keep numbers bounded and to give a clean, unique answer. Addition, subtraction, and multiplication all distribute cleanly over the modulus:

$$(a + b) \bmod m = \bigl((a \bmod m) + (b \bmod m)\bigr) \bmod m$$ $$(a - b) \bmod m = \bigl((a \bmod m) - (b \bmod m) + m\bigr) \bmod m$$ $$(a \cdot b) \bmod m = \bigl((a \bmod m) \cdot (b \bmod m)\bigr) \bmod m$$

The + m in the subtraction rule matters in Python less than in most other languages (Python’s % always returns a non-negative result for a positive modulus), but it’s worth keeping the habit — it’s what makes the rule portable to any language.

Division is the odd one out: $(a / b) \bmod m$ is not $\bigl((a \bmod m) / (b \bmod m)\bigr) \bmod m$ in general. Division under a modulus needs the modular inverse, covered below.

Fast modular exponentiation

Computing $a^b \bmod m$ by multiplying a into an accumulator b times is $O(b)$ — far too slow when b is $10^9$ or more. Binary exponentiation cuts this to $O(\log b)$ by squaring the base and only folding it into the result on the bits of b that are 1:

mod_pow.py

def power_mod(base, exp, mod):
    result = 1
    base %= mod
    while exp > 0:
        if exp & 1:                       # this bit of exp is 1 -> fold the current base in
            result = (result * base) % mod
        base = (base * base) % mod        # square the base for the next bit
        exp >>= 1                          # move to the next bit
    return result
 
 
print("3^13 mod 7:", power_mod(3, 13, 7))
print("built-in pow() does the same:", pow(3, 13, 7))

sketch Binary exponentiation: consuming exp one bit at a time p5.js Pause Restart

Each step squares the base; a lit bit (gold) folds the current base into the running result.

pow(a, b, m) is already this

Python’s built-in three-argument pow(a, b, m) performs exactly this binary exponentiation in C, and is both faster and less error-prone than a hand-rolled version. Write power_mod once to understand the mechanism, then use pow(a, b, m) in every contest solution.

Modular inverse via Fermat’s little theorem

Division under a modulus works by multiplying by the modular inverse of the divisor instead. When the modulus $p$ is prime, Fermat’s little theorem gives a one-line formula:

$$a^{-1} \equiv a^{p-2} \pmod p$$

mod_inverse.py

MOD = 1_000_000_007
 
 
def mod_inverse(a, mod=MOD):
    return pow(a, mod - 2, mod)       # valid ONLY when mod is prime (Fermat's little theorem)
 
 
a = 123456
inv = mod_inverse(a)
print("inverse of", a, "mod", MOD, ":", inv)
print("check: a * inv mod p == 1 ->", (a * inv) % MOD == 1)

Why this works

Fermat’s little theorem states $a^{p-1} \equiv 1 \pmod p$ for a prime $p$ whenever $a$ isn’t a multiple of $p$. Divide both sides by $a$ (multiply by $a^{-1}$): $a^{p-2} \equiv a^{-1} \pmod p$. So raising a to the power p - 2 under the same modulus is the inverse — no separate algorithm needed, just another call to fast modular exponentiation.

Sieve of Eratosthenes

Finding every prime up to some limit n by trial-dividing each number individually is O(n sqrt(n)). The sieve flips the approach: start every number as “prime”, then cross off every multiple of each prime found, starting from its square (smaller multiples were already crossed off by a smaller prime).

sieve.py

def sieve_of_eratosthenes(limit):
    is_prime = [True] * (limit + 1)
    is_prime[0] = is_prime[1] = False
    for i in range(2, int(limit ** 0.5) + 1):
        if is_prime[i]:
            for multiple in range(i * i, limit + 1, i):
                is_prime[multiple] = False
    return [i for i, prime in enumerate(is_prime) if prime]
 
 
primes = sieve_of_eratosthenes(50)
print("primes up to 50:", primes)
print("count:", len(primes))

sketch Sieve of Eratosthenes: crossing off multiples of each prime p5.js Pause Restart

Gold = the current prime i. Blue = still believed prime. Gray = crossed off (composite).

Going further: the linear sieve

The sieve above is $O(n \log \log n)$ — essentially linear, and fast enough for the vast majority of contest constraints (n up to $10^7$ or so). When a problem needs a true $O(n)$ sieve (or the smallest prime factor of every number, useful for fast factorization), the linear sieve marks every composite exactly once by only ever crossing a number off using its smallest prime factor. It’s more code for the same asymptotic class in most practical ranges, so reach for it only when profiling says the classic sieve is the bottleneck.

Prime factorization

Once you have primes (or even without a sieve, for a single number), trial division up to $\sqrt{n}$ finds every prime factor and its exponent:

prime_factorization.py

def prime_factorize(n):
    factors = {}
    d = 2
    while d * d <= n:
        while n % d == 0:
            factors[d] = factors.get(d, 0) + 1
            n //= d
        d += 1
    if n > 1:                 # whatever's left over is itself a prime factor
        factors[n] = factors.get(n, 0) + 1
    return factors
 
 
print(prime_factorize(360))   # {2: 3, 3: 2, 5: 1}  ->  2^3 * 3^2 * 5 = 360
print(prime_factorize(97))    # {97: 1}  --  97 is prime

Combinatorics mod p: nCr with precomputed factorials

$$\binom{n}{k} = \frac{n!}{k! \, (n-k)!}$$

Computing this directly under a modulus needs the modular inverses of k! and (n - k)! — and precomputing every factorial and inverse factorial up to the largest n you’ll ever need turns each individual query into an $O(1)$ lookup, which matters when a problem asks for thousands of nCr queries.

ncr_mod_p.py

MOD = 1_000_000_007
MAX_N = 200_000
 
fact = [1] * (MAX_N + 1)
for i in range(1, MAX_N + 1):
    fact[i] = fact[i - 1] * i % MOD
 
inv_fact = [1] * (MAX_N + 1)
inv_fact[MAX_N] = pow(fact[MAX_N], MOD - 2, MOD)   # one Fermat inverse, at the top
for i in range(MAX_N, 0, -1):
    inv_fact[i - 1] = inv_fact[i] * i % MOD         # (n-1)!^-1 = n!^-1 * n, walking down
 
 
def n_choose_k(n, k):
    if k < 0 or k > n:
        return 0
    return fact[n] * inv_fact[k] % MOD * inv_fact[n - k] % MOD
 
 
print("C(10, 3):", n_choose_k(10, 3))                       # 120
print("C(1000, 500) mod 1e9+7:", n_choose_k(1000, 500))

Only one expensive pow(..., MOD - 2, MOD) call is needed in the whole setup — every other inverse factorial is derived from the next one with a single multiplication, since inv_fact[i - 1] = inv_fact[i] * i % MOD falls straight out of fact[i] = fact[i - 1] * i.

Python ints don’t overflow — but take the modulus anyway

Python integers grow arbitrarily large, so fact[200000] (a number with hundreds of thousands of digits) would compute “correctly” without a modulus — it just gets astronomically slow, since every multiplication now works on huge numbers instead of machine-word-sized ones. Taking % MOD after every operation keeps every intermediate value bounded and the arithmetic fast, and matches what the judge expects as the answer anyway. Never skip the modulus just because Python can handle big integers.

Dry run

Euclid — gcd(48, 18). Each step replaces (a, b) with (b, a mod b):

step	a	b	a % b
1	48	18	12
2	18	12	6
3	12	6	0 → stop, answer is a = 6

Three iterations for numbers up to 48. The bound is $O(\log \min(a,b))$ because a % b at least halves a every two steps — if b ≤ a/2 the remainder is already below a/2, and if b > a/2 then a % b = a − b < a/2. Worst case is consecutive Fibonacci numbers, which is where the log base turns out to be the golden ratio.

Binary exponentiation — 3^13 mod (10^9+7). 13 = 1101₂, so only the set bits contribute:

exp	bit	base (squared each round)	result
13	1	3	3
6	0	9	3 — bit clear, result untouched
3	1	81	243
1	1	6561	1594323

Four iterations instead of thirteen multiplications; at exp = 10^18 it is 60 instead of $10^{18}$.

• The base is squared every round whether or not the bit is set. That is what makes base hold $3^{2^k}$ at round k, so the set bits pick out exactly the factors whose exponents sum to 13: $3^8 \cdot 3^4 \cdot 3^1$.
• Every multiplication is followed by % mod. Skip it and the intermediates grow without bound — harmless in Python (arbitrary precision, just slow), catastrophic in C++ or Java where they overflow silently.
• Python’s built-in pow(base, exp, mod) does exactly this, in C. Use it in interviews and say what it does; write the loop only when asked to show the mechanism.

Sieve of Eratosthenes up to 30. Start at i*i, not 2i — every smaller multiple of i already has a smaller prime factor and was crossed off earlier:

i	marks composite	why start at i*i
2	4, 6, 8, …, 30	—
3	9, 12, …, 30	6 was already crossed by 2
5	25, 30	10, 15, 20 already gone

Primes: 2 3 5 7 11 13 17 19 23 29. 24 marking operations in total, against roughly 99 division tests for per-number trial division — and the gap widens fast, since the sieve is $O(n \log\log n)$ against $O(n\sqrt n)$.

• The outer loop stops at $\sqrt n$. Any composite ≤ n has a factor ≤ √n, so it has already been marked by the time i passes there.
• $\log \log n$ is essentially a constant — about 3 for $n = 10^6$. Treat the sieve as linear when estimating.

Complexity

Task	Naive	Optimized	Notes
GCD	—	$O(\log(\min(a, b)))$	Euclid’s algorithm
$a^b \bmod m$	$O(b)$	$O(\log b)$	Binary (fast) exponentiation
Modular inverse	—	$O(\log p)$	Fermat’s little theorem, requires prime modulus
Primes up to $n$	$O(n \sqrt{n})$ trial division	$O(n \log \log n)$	Sieve of Eratosthenes ($O(n)$ with a linear sieve)
$\binom{n}{k} \bmod p$, many queries	$O(k)$ per query	$O(n)$ precompute, $O(1)$ per query	Precomputed factorials + inverse factorials

The variant map

Need	Tool	Cost
gcd(a, b)	Euclid — or math.gcd, which is C-speed	$O(\log \min(a,b))$
lcm(a, b)	a // gcd(a, b) * b — divide before multiplying to avoid a huge intermediate	$O(\log)$
Solve ax + by = gcd(a,b)	extended Euclid	$O(\log)$
$a^b \bmod m$	binary exponentiation, or pow(a, b, m)	$O(\log b)$
$a^{-1} \bmod p$, p prime	Fermat: pow(a, p - 2, p)	$O(\log p)$
$a^{-1} \bmod m$, m composite	extended Euclid — Fermat is invalid here	$O(\log m)$
All primes ≤ n	sieve of Eratosthenes	$O(n \log\log n)$
Smallest prime factor of every n	modified sieve storing the factor, not a boolean	$O(n \log\log n)$, then $O(\log n)$ per factorisation
Factorise one number	trial division to $\sqrt n$	$O(\sqrt n)$
$\binom{n}{k} \bmod p$, many queries	precomputed factorials + inverse factorials	$O(n)$ setup, $O(1)$ per query
Divisor count / sum	from the prime factorisation: $\prod (e_i + 1)$	$O(\sqrt n)$
“Is n prime”, single query	trial division to $\sqrt n$	$O(\sqrt n)$ — do not build a sieve
Enormous n, primality	Miller–Rabin (deterministic for 64-bit with fixed bases)	$O(k \log^3 n)$

Pitfalls

• Forgetting % MOD on an intermediate. In Python the answer stays correct but the integers grow and everything crawls; in a fixed-width language it overflows silently. Apply the modulus after every multiplication and addition.
• Using Fermat’s inverse with a composite modulus. pow(a, m - 2, m) is only an inverse when m is prime. With composite m it returns a number with no error and every downstream result is wrong. Use extended Euclid, and check that gcd(a, m) == 1 — otherwise no inverse exists at all.
• a * b // gcd(a, b) for LCM. Compute a // gcd * b instead; the reordered version keeps the intermediate small, which matters outside Python.
• Starting the sieve’s inner loop at 2*i. Correct but wasteful — every multiple below i*i already has a smaller prime factor.
• Building a sieve for one primality test. $O(n \log\log n)$ setup to answer a question that trial division answers in $O(\sqrt n)$.
• Negative modulo. Python’s % returns a non-negative result for a positive modulus, so -7 % 5 is 3. C and Java give -2. Do not carry that assumption between languages.
• 0 and 1 in the sieve. Neither is prime; both need explicit initialisation to False.
• Overflowing the factorial table. Precompute factorials mod p as you build them, never as exact integers.

Interview follow-ups

They ask	What they’re checking	The answer
“Why is Euclid $O(\log)$?”	Whether you can justify it	Because a % b at least halves a every two steps: if b ≤ a/2 the remainder is already under a/2, and if b > a/2 then a % b = a − b < a/2. Worst case is consecutive Fibonacci numbers
“Why does the problem say mod $10^9+7$?”	Whether you understand the constraint	Because the true answer is astronomically large. $10^9+7$ is prime (so Fermat’s inverse works) and small enough that a product of two residues fits in 64 bits
“Compute $a^b$ with $b = 10^{18}$”	Binary exponentiation	Square the base each round and multiply into the result on set bits of b: 60 iterations instead of $10^{18}$. In Python, pow(a, b, m) does it natively
“How do you divide under a modulus?”	The key identity	You multiply by the modular inverse. For prime p, $a^{-1} \equiv a^{p-2}$ by Fermat’s little theorem. For composite moduli use extended Euclid, and note the inverse exists only when gcd(a, m) = 1
“Primes up to $10^6$”	Choosing the right tool	Sieve — $O(n \log\log n)$, essentially linear. Per-number trial division would be $O(n\sqrt n)$, about a billion operations
“Now factorise $10^5$ different numbers”	Extending the sieve	Store each number’s smallest prime factor during the sieve instead of a boolean. Each factorisation then costs $O(\log n)$ divisions with no trial division at all
”$\binom{n}{k} \bmod p$ for $10^5$ queries”	Precomputation	Factorials and inverse factorials up to n once in $O(n)$, then each query is f[n] * inv[k] % p * inv[n-k] % p in $O(1)$
“The modulus is $2^{32}$, not a prime”	The trap	Fermat no longer applies. Use extended Euclid, and be aware that inverses only exist for values coprime to the modulus — for $2^{32}$ that means odd numbers only

Practice — real LeetCode problems

A sieve, a GCD in disguise, and a problem that is one theorem long once you recognise it.

LC 204 — Count Primes · Medium

Problem. Return the number of prime numbers strictly less than n.

Constraints. 0 <= n <= 5 * 10**6.

Examples. n = 10 gives 4 (2, 3, 5, 7) · n = 0 gives 0 · n = 1 gives 0

pch.exerciseTag pch.exerciseTitle

Editorial · approach, complexity, follow-ups

Time $O(n \log \log n)$ — the sum of $n/p$ over primes $p$ below $n$. Effectively linear, and the number to quote. Space $O(n)$ bits.

Both optimisations have one-line justifications, and both get asked about:

• Start at $p^2$. Any multiple $kp$ with $k < p$ has a prime factor smaller than $p$, so it was already crossed out on an earlier pass.

• Stop when $p^2 \ge n$. A composite below $n$ must have a prime factor at most $\sqrt{n}$, so every composite is already gone.

• Strictly less than n. n = 3 gives 1 (just the 2), and n = 2 gives 0. Off-by-one here is the most common wrong answer on the problem.

• n = 0 and n = 1 must not index sieve[1], hence the early return. A bare [True] * n with sieve[0] = sieve[1] = False crashes on n = 0 and n = 1.

• p * p < n, not p * p <= n — with indices running to n - 1, a p where p * p == n has no multiple inside the array anyway. Either bound is correct here; the strict one matches the index range exactly.

• sum(sieve) works because True is 1. Cute, and fine to use.

In Python the inner loop is often written as a slice assignment, sieve[p*p::p] = [False] * len(sieve[p*p::p]), which pushes the work into C and is several times faster. Worth showing after the explicit loop.

Follow-ups you should expect: “List the primes, not the count?” — the same sieve, then enumerate. “Primes up to $10^{12}$?” — a plain sieve needs too much memory; use a segmented sieve, and mention Miller-Rabin for testing a single large number. “Smallest prime factor of every number?” — store p instead of False during the sieve; that gives $O(\log n)$ factorisation per query afterwards. “Prime factorise one number?” — trial division to $\sqrt{n}$ is enough. “Count primes in a range [a, b]?” — segmented sieve, or two prefix counts.

LC 1071 — Greatest Common Divisor of Strings · Easy

Problem. A string t divides s if s is t repeated some number of times. Return the longest string that divides both str1 and str2, or "" if there is none.

Constraints. 1 <= len(str1), len(str2) <= 1000, uppercase English letters.

Examples. "ABCABC" and "ABC" gives "ABC" · "ABABAB" and "ABAB" gives "AB" · "LEET" and "CODE" gives ""

pch.exerciseTag pch.exerciseTitle

Editorial · approach, complexity, follow-ups

A number-theory identity wearing a string costume. Once you see that string concatenation behaves like addition of exponents over a common base, the whole problem is two lines.

Why commuting is the right test. If both strings are repetitions of a common base t, then str1 + str2 and str2 + str1 are both t repeated (len(str1) + len(str2)) / len(t) times, so they are equal. The converse is the non-obvious direction — it is a standard result that xy = yx for strings forces both to be powers of a common word. You are not expected to prove it at a whiteboard, but you should state that you are using it rather than pretend it is obvious.

Why the length is the GCD. Any common divisor’s length divides both lengths, so it divides their GCD; and given that a common divisor exists, the prefix of that GCD length is one. So it is the longest.

Time $O(m + n)$ for the concatenation and comparison. Space $O(m + n)$ for the two temporary strings.

• Return "", not None, when there is no common divisor.
• "LEET" and "CODE" have GCD length 4, so a length check alone would wrongly return "LEET". The commuting test is what rejects it — skipping it is the classic wrong solution that passes the first two examples.
• str1[:g] versus str2[:g] — once the strings commute, both prefixes are identical, so either works.
• Equal strings return the whole string, since the GCD of n and n is n.

Follow-ups you should expect: “Prove it, or at least test it without the theorem?” — take the candidate prefix of GCD length and verify it repeats to build both strings; still $O(m + n)$ and much easier to defend. “Repeated Substring Pattern (LC 459)?” — the same family: s is a repetition if s appears in (s + s)[1:-1]. “Shortest string both divide (the LCM)?” — exists exactly when a GCD does, with length lcm(m, n). “Why does math.gcd suffice?” — it is Euclid’s algorithm in C, $O(\log \min(m, n))$.

LC 1250 — Check If It Is a Good Array · Hard

Problem. You may pick a subset of nums, multiply each chosen number by any integer, and add the results. The array is good if some choice sums to exactly 1. Return whether it is good.

Constraints. 1 <= len(nums) <= 10**5, 1 <= nums[i] <= 10**9.

Examples. [12,5,7,23] gives True · [29,6,10] gives True · [3,6] gives False

pch.exerciseTag pch.exerciseTitle

Editorial · approach, complexity, follow-ups

Bezout’s identity. For integers $a$ and $b$, the set $\{ax + by : x, y \in \mathbb{Z}\}$ is exactly the set of multiples of $\gcd(a, b)$. Extended to $n$ numbers: the reachable sums are precisely the multiples of the GCD of all of them. So 1 is reachable exactly when that GCD is 1 — when the numbers are setwise coprime.

Note this is setwise coprime, not pairwise. [6,10,15] has no two elements coprime, yet the GCD of all three is 1, so it is good. Being able to draw that distinction is most of what the problem is testing.

Time $O(n \log \max)$. Space $O(1)$.

• Seed with 0. gcd(0, x) == x, so 0 is the correct identity element for folding. Seeding with nums[0] also works but needs a guard for an empty array.
• The early exit is safe because gcd(1, x) == 1 always — once the running GCD is 1 it stays 1. Not required for correctness, but a natural thing to point out.
• [3,6] is False. Every reachable sum is a multiple of 3, and 1 is not.
• [1] is True — pick the 1 and multiply by 1.
• The multipliers may be negative, which is what makes [29,6,10] work: for example $29 \cdot 1 + 6 \cdot (-5) + 10 \cdot 0 = -1$, then negate. If the multipliers were restricted to non-negative integers this would be the Frobenius coin problem, which is a genuinely different and much harder question.

Follow-ups you should expect: “Find the actual multipliers?” — the extended Euclidean algorithm, folded across the array. “Reach some other target t?” — t is reachable exactly when the GCD divides it. “Non-negative multipliers only?” — the Chicken McNugget / Frobenius problem; no simple closed form beyond two numbers. “Why is this rated Hard?” — purely for the recognition step; the code is four lines and that gap is the lesson.

LeetCode problem set

Generated from the problem database, so each entry carries its sheet membership and reported companies. Tick them off as you go — progress is saved in this browser, and the Export button writes it to a file you can keep.

4 problems

0 easy4 medium0 hard

Work down the ladder. Tick each problem off as you go — progress is saved in this browser, and the Export button in the filter bar writes it to a file you can keep.

• ○204Count PrimesmediumThe Sieve of Eratosthenes above, applied directly to count primes below a limit
• ○264Ugly Number IImediumNot a sieve, but the same "multiples of small primes" thinking: merge three pointers tracking multiples of 2, 3, and 5
• ○279Perfect SquaresmediumUsually solved with DP, but Lagrange's four-square theorem (every positive integer is a sum of at most four perfect squares) gives a number-theory shortcut most solvers never see
• ○1390Four DivisorsmediumSum the divisors of every number that has exactly four of them; a direct application of prime factorization

Self-check

pch.quizTag Number theory — self-check

1. Why is Euclid's algorithm O(log min(a, b))?

   A Because it subtracts one each step B Because `a % b` at least halves `a` every two steps — if b ≤ a/2 the remainder is already under a/2, and if b > a/2 then a % b = a − b < a/2 C Because gcd is bounded by 32 bits D Because the numbers are sorted first
   pch.quizShowAnswer

   B — Because `a % b` at least halves `a` every two steps — if b ≤ a/2 the remainder is already under a/2, and if b > a/2 then a % b = a − b < a/2 — The worst case is consecutive Fibonacci numbers, which is why the log base works out to the golden ratio. gcd(48,18) takes three steps.

2. A problem says 'return the answer modulo 10^9 + 7'. What does that tell you?

   A That the answer fits in an int B That the true answer is astronomically large, so it must never be materialised — every multiplication and addition needs a % MOD, and the modulus being prime means Fermat's inverse is available C That the input contains primes D That you should use floating point
   pch.quizShowAnswer

   B — That the true answer is astronomically large, so it must never be materialised — every multiplication and addition needs a % MOD, and the modulus being prime means Fermat's inverse is available — It is also chosen so that a product of two residues still fits in 64 bits. In Python skipping the mod is 'only' slow; in C++ it overflows silently.

3. In binary exponentiation, why is the base squared even when the current bit is 0?

   A To keep the loop simple B Because base must hold a^(2^k) at round k — the squaring is what builds the ladder, and the set bits select which rungs get multiplied in C To apply the modulus D It should not be; that is a bug
   pch.quizShowAnswer

   B — Because base must hold a^(2^k) at round k — the squaring is what builds the ladder, and the set bits select which rungs get multiplied in — For 3^13 = 3^8 · 3^4 · 3^1, the bases 3, 9, 81, 6561 are produced by unconditional squaring and bits 1101 pick three of them.

4. How do you divide under a modulus?

   A Use floating-point division and round B Multiply by the modular inverse — for prime p, a^(-1) = a^(p-2) by Fermat's little theorem; for composite moduli use extended Euclid C Divide and then take the modulus D Division is not defined under a modulus
   pch.quizShowAnswer

   B — Multiply by the modular inverse — for prime p, a^(-1) = a^(p-2) by Fermat's little theorem; for composite moduli use extended Euclid — Applying Fermat with a composite modulus is the dangerous case: it returns a number with no error and every result downstream is wrong. The inverse exists only when gcd(a, m) = 1.

5. Why does the sieve's inner loop start at `i*i` rather than `2*i`?

   A To avoid marking i itself B Because every multiple of i below i*i has a smaller prime factor and was already crossed off by that smaller prime C Because i*i is the first composite D To keep the loop O(1)
   pch.quizShowAnswer

   B — Because every multiple of i below i*i has a smaller prime factor and was already crossed off by that smaller prime — When i = 5, the numbers 10, 15 and 20 were already marked by 2 and 3. The outer loop can also stop at √n, since any composite ≤ n has a factor ≤ √n.

6. You need one primality test for a single number around 10^12. Sieve?

   A Yes, sieve up to 10^12 B No — trial division to √n is about 10^6 operations, while a sieve of that size is impossible in memory. Miller–Rabin if n grows further C Yes, but only up to √n D Use Fermat's little theorem directly
   pch.quizShowAnswer

   B — No — trial division to √n is about 10^6 operations, while a sieve of that size is impossible in memory. Miller–Rabin if n grows further — Sieves are for bulk queries. Building one to answer a single question is the classic misapplication — and at 10^12 the array alone would need terabytes.

Recall card

• Cue — “modulo $10^9+7$”, divisibility, primes, gcd, huge exponents, or a per-number question asked for every value up to n.
• gcd — Euclid: while b: a, b = b, a % b. $O(\log)$. LCM = a // gcd * b (divide first).
• $a^b \bmod m$ — binary exponentiation: square the base each round, multiply in on set bits. $O(\log b)$; Python’s pow(a, b, m) is this in C.
• Division under a modulus = multiply by the inverse. Prime p: pow(a, p-2, p). Composite: extended Euclid, and only when gcd(a, m) = 1.
• Sieve — inner loop starts at i*i, outer stops at $\sqrt n$. $O(n\log\log n)$, effectively linear. Store the smallest prime factor instead of a boolean and factorisation becomes $O(\log n)$ per number.
• One primality test — trial division to $\sqrt n$. Do not build a sieve.
• nCr mod p — precompute factorials and inverse factorials once, $O(1)$ per query.
• Apply % MOD after every operation, not at the end.

Recap

• GCD/LCM: Euclid’s algorithm shrinks (a, b) to gcd in $O(\log(\min(a, b)))$; use math.gcd and math.lcm in practice.
• Modular arithmetic: add/subtract/multiply distribute cleanly over a modulus; division needs the modular inverse instead.
• Fast exponentiation: $O(\log b)$ via squaring, or just call pow(a, b, m).
• Modular inverse: pow(a, p - 2, p) for prime p, via Fermat’s little theorem.
• Sieve of Eratosthenes: $O(n \log \log n)$ to find every prime up to n; a linear sieve reaches true $O(n)$ when needed.
• nCr mod p: precompute factorials and inverse factorials once, then answer every query in $O(1)$.

That closes out the sparse table and number theory building blocks — between static-array RMQ and this modular-arithmetic toolkit, you can now recognize and solve a large share of the “math-flavored” problems that show up throughout competitive programming.

Next: String Algorithms: KMP, Z, and Rabin-Karp — linear-time pattern matching, the other family of classic CP building blocks that shows up just as often as the number theory above.