Numerics & Math

Numerics & Math | Algoryva

//

%

Intuition

Arithmetic on a clock

If it is 10 o'clock now, what time is it in 5 hours? Not 15: it is 3. A clock only remembers the remainder after dividing by 12. That wrap-around arithmetic, remainders, is the engine behind divisibility tests, repeating patterns, calendars, hashing, and the “answer modulo 10⁹ + 7” that ends so many contest statements.

Numbers also have a *structure*: they break into prime building blocks, and pairs of numbers share common factors. Knowing these facts lets you answer questions about numbers up to 10¹⁸ without ever looping that far.

First, the naive way

Find the gcd by trying every divisor

The greatest common divisor of a and b is the largest number dividing both. The direct way tests every candidate from 1 up to the smaller number and remembers the biggest that works.

That is up to min(a, b) steps. For numbers around 10¹⁸ it would take longer than the age of the universe, yet Euclid's method, below, needs fewer than a hundred steps.

python

def gcd_naive(a, b):
    best = 1
    for d in range(1, min(a, b) + 1):
        if a % d == 0 and b % d == 0:
            best = d
    return best

print(gcd_naive(48, 18))   # 6
print(gcd_naive(17, 5))   # 1

Cost: O(min(a, b)) steps: far too slow for large numbers.

The observation

A common divisor of a and b also divides their remainder

Write a = q·b + r where r = a mod b. Any number that divides both a and b divides q·b and therefore divides a − q·b = r. Conversely, anything dividing both b and r divides a. So the pairs (a, b) and (b, r) have exactly the same common divisors, hence the same gcd.

That lets us replace the pair by a *smaller* pair. Repeat until the second number is 0; then the gcd is the first. The remainder is always less than the divisor, and in two steps a is at least halved, so the loop runs about log of the numbers.

See it move

Euclid's algorithm

Two numbers shrink step by step: replace (a, b) with (b, a mod b) until the second is 0. Each caption states why the gcd does not change when we do that.

The concept

The toolkit in one table

Almost every numeric problem in a contest uses one or two of these ideas.

Remainder: a % m is always in 0..m-1 for positive m in Python, even for negative a. Two numbers are congruent mod m if they leave the same remainder.
gcd and lcm: gcd(a, b) by Euclid; lcm(a, b) = a / gcd(a, b) × b (divide first to keep numbers small). gcd(0, x) = x.
Prime: an integer greater than 1 whose only divisors are 1 and itself. Every integer greater than 1 is a unique product of primes (its factorisation).
Divisor count and sum follow from the factorisation: if n = p₁^e₁ · p₂^e₂ ⋯, then the number of divisors is (e₁ + 1)(e₂ + 1)⋯.
Modular arithmetic: (a + b) % m, (a * b) % m can be computed from the remainders of a and b. This keeps numbers small and answers within range.
Modular inverse: for prime m, a⁻¹ ≡ a^(m−2) (mod m) (Fermat). Division modulo m becomes multiplication by the inverse.
Inclusion–exclusion: to count numbers divisible by a, b or c, add the single counts, subtract the pairs, add back the triple.

Worked by hand

Euclid and a factorisation, by hand

First gcd(48, 18): at each step replace the pair (a, b) by (b, a mod b) until the second number is 0.

step	a	b	a mod b	next pair
1	48	18	12	(18, 12)
2	18	12	6	(12, 6)
3	12	6	0	(6, 0)
done	6	0	-	gcd = 6

1
Check the answer
6 divides 48 (8 times) and 18 (3 times), and no larger number divides both. Three steps instead of testing 18 candidates.
2
Factorising 360 by trial division
Divide by 2 while possible: 360 → 180 → 90 → 45 (three 2s). Divide by 3: 45 → 15 → 5 (two 3s). The next divisor 4 has 4 × 4 = 16 > 5, so stop. The leftover 5 is prime. So 360 = 2³ · 3² · 5.

Implementation

gcd and lcm

Euclid's algorithm is a three-line loop.

Plan in plain steps

pseudocode

while b is not 0:
    (a, b) = (b, a mod b)
return a

python

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

def lcm(a, b):
    return a // gcd(a, b) * b

print(gcd(48, 18), lcm(4, 6))   # 6 12
print(gcd(17, 5), gcd(0, 9), gcd(9, 0))   # 1 9 9
print(gcd(10**18, 10** + ))   
 math
(math.(, ), math.(, ))

See it move

Finding all primes at once: the sieve

To list every prime up to n, do not test each number separately. Instead cross out multiples: for each number still standing, cross out its multiples. Whatever survives is prime. Notice it starts crossing at p², because smaller multiples of p have a smaller prime factor and were already removed, and that it stops once p² exceeds n.

Implementation

Primality test and sieve

To test one number, only divisors up to √n matter: if n = a·b then one of a, b is at most √n. To list all primes up to n, the sieve is far faster than testing each.

python

def is_prime(n):
    if n < 2:
        return False
    i = 2
    while i * i <= n:
        if n % i == 0:
            return False
        i += 1
    return True

def sieve(n):
    if n < 2:
        return []
    is_p = [True] * (n + 1)
    is_p[0] = is_p[1] = False
    i = 2
    while i * i <= n:
        if is_p[i]:
            for m  (i * i, n + , i):
                is_p[m] = 
        i += 
     [i  i, p  (is_p)  p]

([x  x  (, )  (x)])   
((), (), (** + ))   
(())   
((()), ((**)))   
((), ())

Implementation

Factorisation and counting divisors

Trial division by 2, 3, 4, … up to √n finds every prime factor. Whatever is left above 1 at the end is itself a prime.

python

def factorize(n):
    f = {}
    d = 2
    while d * d <= n:
        while n % d == 0:
            f[d] = f.get(d, 0) + 1
            n //= d
        d += 1
    if n > 1:
        f[n] = f.get(n, 0) + 1
    return f

print(factorize(360))   # {2: 3, 3: 2, 5: 1}
print(factorize(97))   # {97: 1}
print(factorize(1))   # {}

def count_divisors(n):
    total = 1
    for e in factorize(n).values():
        total *= e + 
     total

(())

Implementation

Modular arithmetic

Contest answers are often “modulo 10⁹ + 7” (a prime) because the true answer is astronomically large. The rules are simple: you can take the remainder at any stage of additions, subtractions and multiplications.

python

MOD = 10**9 + 7

a, b = 123456789123, 987654321987
print(a * b % MOD == (a % MOD) * (b % MOD) % MOD)   # True
print(-7 % 5, 7 % -5)   # 3 -3

def power_mod(base, exp, mod):
    result = 1
    base %= mod
    while exp > 0:
        if exp & 1:
            result = result * base % mod
        base = base * base % mod
        exp >>= 1
    return result

print(power_mod(2, 10, 1000), pow(2, 10, 1000))   
((, , ) == (, , ))   
( * (, MOD - , MOD) % MOD)   
((, -, ))

Complexity

Costs

For n up to 10¹², O(√n) trial division is fine (10⁶ steps). For n up to 10¹⁸ it is not (10⁹ steps): that is where Miller–Rabin and Pollard's rho come in, beyond this course.

gcd by Euclid

time O(log min(a, b))space O(1)

The numbers at least halve every two steps.

gcd by trying divisors (naive)

time O(min(a, b))space O(1)

Tests every candidate.

Primality test by trial division

time O(√n)space O(1)

Only divisors up to √n are needed.

Sieve of Eratosthenes up to n

time O(n log log n)space O(n)

Each prime p crosses out n/p numbers; the sum of n/p over primes is about n log log n.

Factorising one number

time O(√n)space O(log n)

Trial division up to √n; at most log₂ n prime factors.

Modular exponentiation

time O(log exp)space O(1)

One squaring per bit of the exponent.

Factorising many numbers (a smallest-prime-factor sieve)

time O(n log log n) once, then O(log n) eachspace O(n)

Edge cases

0 and 11 is neither prime nor composite; gcd(x, 0) = x; 0 % m = 0. Guard n < 2 in primality and sieve code.
Negative numbersPython's % with a positive modulus is non-negative, so remainder buckets work directly. In other languages, normalise first.
Perfect squares in primality testsUse i * i <= n (inclusive) so 25 is checked against 5 and found composite.
Overflow in other languagesPython ints never overflow, but in C++/Java use 64-bit types, take % MOD after every multiplication, and compute lcm as a / g * b.
Modulus is not primeFermat inverses need a prime modulus. For other moduli use the extended Euclidean algorithm (or pow(a, -1, m) when gcd(a, m) = 1).
Huge sieve limitsA sieve needs O(n) memory. For n around 10⁸ use a bytearray, or a segmented sieve.

Common mistakes

Mistakes to avoid

Testing every number up to n for primality.
Stop at √n, or sieve once if you need many primes.
Computing a ** b % m directly.
That builds a gigantic number first. Use pow(a, b, m).
Forgetting to reduce modulo m after each multiplication in loops (in C++/Java).
Reduce at every step; mod after the final answer is too late once overflow happens.
Subtracting under a modulus and leaving a negative.
Use (a - b) % m in Python, or add m before the final % elsewhere.
Treating floating-point sqrt or division as exact.
Use integer tools: math.isqrt, //, and .

Recognize it in a contest

How to spot a numerics problem

Reach for it when the problem says or implies

Words like divisible, remainder, multiple, divisor, gcd, lcm, prime, factor.
“Return the answer modulo 10⁹ + 7”: the true answer is huge; use modular arithmetic throughout.
The bound is 10⁹ or 10¹⁸: you cannot loop to n, but you can loop to √n or use log n tricks.
A cycle or repetition: days of the week, positions on a circle, patterns that repeat with some period: remainders.
“Count numbers up to x divisible by …” or “find the n-th such number”: inclusion–exclusion, often with binary search.
“How many subarrays have gcd k?”: the gcd of a growing range only changes O(log) times, because each change at least halves it.

Look elsewhere when

Worked problem

Can the array be split into pairs with sums divisible by k?

The problem

Given an even-length array and a positive integer k, decide whether the elements can be split into pairs so that every pair's sum is divisible by k.

Only remainders matter: a pair (x, y) has a sum divisible by k exactly when x % k and y % k add up to 0 or to k.
Count how many elements leave each remainder 0 to k − 1.
Remainder 0 pairs with remainder 0, so that count must be even. If k is even, remainder k/2 pairs with itself, so that count must be even too.
Otherwise remainder r pairs with remainder k − r, so their counts must be equal.

python

def can_pair(arr, k):
    cnt = [0] * k
    for x in arr:
        cnt[x % k] += 1
    if cnt[0] % 2:
        return False
    for r in range(1, k // 2 + 1):
        if r == k - r:
            if cnt[r] % 2:
                 
         cnt[r] != cnt[k - r]:
             
     

(([, , , , , , , , , ], ))   
(([, , , , , ], ))   
(([, , , , , ], ))   
(([-, , -, , -, , -, ], ))

Worked problem

The n-th number divisible by a, b or c

The problem

Return the n-th positive integer that is divisible by at least one of a, b or c (up to 2 × 10⁹).

Listing numbers one by one is far too slow, but *counting* how many valid numbers are at most x is fast: x//a + x//b + x//c, minus the pairs counted twice, plus the triple counted back in (inclusion–exclusion with lcm).
count(x) never decreases as x grows, so we can binary search for the smallest x with count(x) >= n.
That x is the n-th valid number.

python

from math import gcd

def lcm(a, b):
    return a // gcd(a, b) * b

def nth_ugly(n, a, b, c):
    ab, ac, bc = lcm(a, b), lcm(a, c), lcm(b, c)
    abc = lcm(ab, c)

    def count(x):
        return x // a + x // b + x // c - x // ab - x // ac - x // bc + x // abc

    lo, hi = 1, 2 * 10**
     lo < hi:
        mid = (lo + hi) // 
         (mid) >= n:
            hi = mid
        :
            lo = mid + 
     lo

((, , , ))   
((, , , ))   
((, , , ))

Wrap-up

Remember this

Remainders turn huge numbers into small, repeating patterns; Python's % is non-negative for a positive modulus.
Euclid's algorithm computes gcd in O(log n) because (a, b) and (b, a mod b) share the same common divisors.
Primes: test up to √n, list with the sieve (O(n log log n)), factorise by trial division.
Work modulo a prime with pow(b, e, m), reduce after every operation, and divide with modular inverses.
Count divisible numbers with inclusion–exclusion, and combine with binary search when you need the n-th.

Cheat sheet

gcd / lcm: while b: a, b = b, a % b · lcm = a // gcd × b
Prime test: n ≥ 2 and no divisor d with d·d ≤ n
Sieve: cross out i·i, i·i+i, … for each surviving i ≤ √n
Factorise: divide out d from 2 while d·d ≤ n; leftover n > 1 is prime
Modular: reduce after every + − ×; pow(b, e, m); inverse pow(a, m−2, m)
Count multiples ≤ x: x // a; union via inclusion–exclusion with lcm

Top traps to avoid

Testing every number up to n for primality.
Computing a ** b % m directly.
Forgetting to reduce modulo m after each multiplication in loops (in C++/Java).

Mastery check

0 of 15 answered

Answer from understanding, not memory of the page. You need 12 of 15. Each answer is explained, and you can retry as often as you like.

1.What is gcd(48, 18), following Euclid's algorithm?
2.How many divisors must you test to decide whether n = 10¹² is prime by trial division?
3.Why does the sieve start crossing out multiples of p at p² instead of 2p?
4.How many divisors does 360 = 2³ · 3² · 5 have?
5.“Count the pairs of numbers whose sum is divisible by 7” most strongly suggests:
6.Why compute pow(a, b, m) rather than a ** b % m for large b?
7.What does print(pow(2, 10, 1000)) print?
8.What does print(7 // -2, -7 // 2) print?
9.What does print(-7 % 3) print?
10.What does print(round(2.5), round(3.5)) print?
11.What are gcd and lcm of 84 and 36, as printed by print(math.gcd(84,36), 84*36//math.gcd(84,36))?
12.How many primes are there up to 30? (sieve of Eratosthenes)
13.What is the running time of the Sieve of Eratosthenes up to n?
14.Why reduce each factor modulo m before multiplying, when computing (a * b) % m?
15.What is 10**18 * 10**18 % 7 in Python?

i * i <= n

Numerics & Math

After this lesson you will be able to

Builds on

Unlocks

Arithmetic on a clock

Find the gcd by trying every divisor

A common divisor of a and b also divides their remainder

Euclid's algorithm

The toolkit in one table

Euclid and a factorisation, by hand

gcd and lcm

Finding all primes at once: the sieve

Primality test and sieve

Factorisation and counting divisors

Modular arithmetic

Costs

Edge cases

Mistakes to avoid

How to spot a numerics problem

Can the array be split into pairs with sums divisible by k?

The n-th number divisible by a, b or c

Wrap-up

Remember this

Cheat sheet

Top traps to avoid

Mastery check

Practice this topic

Warm-up2 problems

Core4 problems

Application3 problems

Challenge1 problem

Reading the code

Reading the code

Reading the code

Reading the code