INVARIANT · MATHS · LET THE NUMBER THEORY DO THE COUNTING
01
00/15
01 / COVER MODULE 28 · MATHS
INVARIANT · MODULE 28 · MATHS AND MODULAR ARITHMETIC
LET THE NUMBER THEORY DO THE COUNTING

These problems look like loops over 10¹² numbers or 2ⁿ strings. Each one gives way to a fact about whole numbers: a carry stops at the first digit below 9, a finite map must loop, a divisor counts its multiples, n / d takes few values, and a prime modulus makes every number invertible. Twelve moves, fifteen problems.

15Problems
5Families
12Units
12Live walks
← → ↑ ↓  or  W A S D  navigate SPACE next   DOUBLE-CLICK to advance I index   G goto problem   P predict H hide solutions   F fullscreen
INVARIANT · MATHS · LET THE NUMBER THEORY DO THE COUNTING · MATHS AND MODULAR ARITHMETIC
02 / INDEX PRESS I FROM ANYWHERE

INDEX — ALL 15 PROBLEMS

Click any problem to jump straight to it. Solved ones turn green. Press I from anywhere to come back here. The number is the problem's fixed number in this deck, not a slide position.

DIGITS AND BASES · 04
DIVISIBILITY · 02
PRIMES · 03
COUNTING WITH DIVISION · 02
MODULAR ARITHMETIC · 04
SOLVED HAS A JUDGE LINK
INVARIANT · MATHS · LET THE NUMBER THEORY DO THE COUNTING · MATHS AND MODULAR ARITHMETIC
03 / MECHANISM UNIT 01 · CARRY FROM THE RIGHT

THE CARRY STOPS AT THE FIRST DIGIT BELOW 9

Add from the last digit. A 9 becomes 0 and hands its 1 to the left; the first digit below 9 takes the 1, and nothing to its left changes, so the function returns there. Only an array of 9s gets a new digit in front.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · MATHS · LET THE NUMBER THEORY DO THE COUNTING · MATHS AND MODULAR ARITHMETIC
04 / DRILL UNIT 01 · Carry From the Right

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

plusOne([9, 9])?

Both 9s become 0 and pass the 1 left. The loop ends with the carry still owed, so a 1 goes in front: 99 + 1 = 100.

DRILL 02 · RECALL

Why can the loop return as soon as a digit is below 9?

A digit d below 9 becomes d + 1, at most 9, so it makes no 10 and passes nothing on. Every digit to its left keeps its value.

INVARIANT · MATHS · LET THE NUMBER THEORY DO THE COUNTING · MATHS AND MODULAR ARITHMETIC
05 / PROBLEM #01 · DIGITS · EASY

Plus One

EASY digits ▶ SOLVE ON LEETCODE
SIGNAL — WHAT GIVES IT AWAY

A number too long for any integer type is given as an array of digits. Add one to it.

INTUITION

Add the way it is done on paper, from the last digit. A digit below 9 takes the 1 and nothing carries past it, so the answer is ready. A 9 becomes 0 and passes the 1 to the digit on its left. If every digit was 9, the carry falls off the front, and the answer is a 1 followed by zeros, one digit longer.

STEPS
  1. Walk the digits from the last to the first
  2. A digit below 9 grows by 1, and the array is returned
  3. A 9 becomes 0 and the carry moves left
  4. If the walk ends, every digit was 9, so put a 1 in front
BRUTEO(n), adding with a carry kept for every digit
→
OPTIMALO(n)
↕ SCROLL
vector<int> plusOne(vector<int>& digits) {
    for (int i = (int)digits.size() - 1; i >= 0; i--) {
        if (digits[i] < 9) { digits[i]++; return digits; }   // the carry stops here
        digits[i] = 0;                         // 9 + 1 = 10: write 0, carry 1
    }
    digits.insert(digits.begin(), 1);          // every digit was 9
    return digits;
}
TIMEO(n)the walk stops at the first digit below 9
SPACEO(1)in place, plus one cell when every digit is 9
TRAP

Dropping the last carry. When every digit is 9 the loop ends with all zeros and a carry still owed. Returning the array then turns [9] into [0], not [1, 0].

INVARIANT · MATHS · LET THE NUMBER THEORY DO THE COUNTING · MATHS AND MODULAR ARITHMETIC
06 / MECHANISM UNIT 02 · A BASE WITH NO ZERO

SHIFT TO ZERO, THEN DIVIDE

The letters are the digits 1 to 26 of a base with no 0. Subtract 1, and the last letter is the remainder mod 26 counted from A. The quotient is the title before it, so repeat on it, and reverse the letters at the end.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · MATHS · LET THE NUMBER THEORY DO THE COUNTING · MATHS AND MODULAR ARITHMETIC
07 / DRILL UNIT 02 · A Base With No Zero · 1 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

convertToTitle(52)?

51 mod 26 = 25, which is Z, and 51 / 26 = 1. Then 0 mod 26 = 0, which is A. Reversed, AZ, and 1 × 26 + 26 = 52.

DRILL 02 · RECALL

Why subtract 1 before taking n mod 26?

In ordinary base 26 the digits are 0 to 25. Here Z stands for 26, so shifting every letter down by 1 makes them ordinary digits for one step.

INVARIANT · MATHS · LET THE NUMBER THEORY DO THE COUNTING · MATHS AND MODULAR ARITHMETIC
08 / DRILL UNIT 02 · A Base With No Zero · 2 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

convertToTitle(703)?

702 mod 26 = 0 gives A and leaves 27. 26 mod 26 = 0 gives A and leaves 1. 0 gives A. ZZ is 702, so 703 is the first three-letter title.

INVARIANT · MATHS · LET THE NUMBER THEORY DO THE COUNTING · MATHS AND MODULAR ARITHMETIC
09 / PROBLEM #02 · DIGITS · EASY

Excel Sheet Column Title

EASY digits ▶ SOLVE ON LEETCODE
SIGNAL — WHAT GIVES IT AWAY

Turn a column number into its Excel title: 1 is A, 26 is Z, 27 is AA.

INTUITION

Titles are numbers in base 26, but the digits run from A = 1 to Z = 26 and there is no zero. Subtract 1 first, and the last letter is (n − 1) mod 26 counted from A, a digit from 0 to 25. The rest of the title is the number (n − 1) / 26, so repeat on it until nothing is left. The letters come out last first, so reverse them.

STEPS
  1. While n > 0, subtract 1 from n
  2. The last letter is A plus n mod 26
  3. Divide n by 26 and repeat
  4. Reverse the letters
BRUTEO(n), counting titles up from A
→
OPTIMALO(log n)
↕ SCROLL
string convertToTitle(int columnNumber) {
    string t;
    int n = columnNumber;
    while (n > 0) {
        n--;                                   // the letters are 1 to 26, so shift to 0 to 25
        t += char('A' + n % 26);               // the last letter
        n /= 26;                               // the title before it
    }
    reverse(t.begin(), t.end());
    return t;
}
TIMEO(log n)one letter per factor of 26
SPACEO(log n)the letters of the title
TRAP

Shifting only the letter. Taking the letter from (n − 1) mod 26 but dividing n, not n − 1, by 26 leaves a stray carry. 26 comes out AZ; Z is right.

INVARIANT · MATHS · LET THE NUMBER THEORY DO THE COUNTING · MATHS AND MODULAR ARITHMETIC
10 / MECHANISM UNIT 03 · A FINITE MAP MUST LOOP

A REMAINDER THAT COMES BACK REPEATS THE DIGITS

Long division makes each digit from the remainder alone, and a remainder is below the denominator. So within b digits a remainder comes back, and everything after it repeats. The map remembers where each remainder's digit went, which is where the bracket goes.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · MATHS · LET THE NUMBER THEORY DO THE COUNTING · MATHS AND MODULAR ARITHMETIC
11 / DRILL UNIT 03 · A Finite Map Must Loop · 1 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

isHappy(20)?

20 goes 4, 16, 37, 58, 89, 145, 42 and back to 20. The cycle never holds 1.

DRILL 02 · RECALL

Why must the walk of digit-square sums come back to a value?

A number with d digits maps to at most 81d. From 999 or below the next value is at most 243, so the walk is trapped among fewer than 1000 values and must repeat one.

INVARIANT · MATHS · LET THE NUMBER THEORY DO THE COUNTING · MATHS AND MODULAR ARITHMETIC
12 / PROBLEM #03 · DIGITS · EASY

Happy Number

EASY digits ▶ SOLVE ON LEETCODE
SIGNAL — WHAT GIVES IT AWAY

Replace n by the sum of the squares of its digits again and again. Does it reach 1?

INTUITION

A number with d digits maps to at most 81d, so after a step or two every value is below 1000, and from there it stays below 1000. A walk on finitely many values must repeat one, and after that it goes round a cycle forever. So the question is whether the cycle is the one at 1. Run a slow walker one step at a time and a fast one two steps at a time. Inside the cycle the fast one gains a step each round, so they meet, and they meet at 1 when 1 is the cycle.

STEPS
  1. Write next(n), the sum of the squares of the digits
  2. Start slow at n and fast at next(n)
  3. Move slow one step and fast two until fast is 1 or they meet
  4. n is happy when fast is 1
BRUTEO(log n) with a set of the values seen
→
OPTIMALO(log n)
↕ SCROLL
int sq(int n) {                                // the sum of the squares of the digits
    int s = 0;
    for (; n > 0; n /= 10) s += (n % 10) * (n % 10);
    return s;
}

bool isHappy(int n) {
    int slow = n, fast = sq(n);
    while (fast != 1 && slow != fast) {        // a finite walk must repeat
        slow = sq(slow);
        fast = sq(sq(fast));                   // gains one step a round
    }
    return fast == 1;
}
TIMEO(log n)values fall below 1000 within a few steps, and the cycle is short
SPACEO(1)two numbers, no set
TRAP

Starting both walkers on n. Then slow equals fast before either moves, the loop never runs, and only n = 1 is happy. 7 goes 49, 97, 130, 10, 1, and comes out false.

INVARIANT · MATHS · LET THE NUMBER THEORY DO THE COUNTING · MATHS AND MODULAR ARITHMETIC
13 / PROBLEM #04 · DIGITS · MED

Fraction to Recurring Decimal

MED digits ▶ SOLVE ON LEETCODE
SIGNAL — WHAT GIVES IT AWAY

Write numerator / denominator as a decimal, with the repeating part in brackets.

INTUITION

Long division makes one digit per step from a remainder r below the denominator: the digit is 10r / b and the next remainder is 10r mod b. Everything after depends only on r, so when a remainder comes back the digits since its first visit repeat forever. Keep a map from each remainder to where its digit went. A remainder of 0 ends the decimal, and one seen before puts the bracket at its first place. Work with absolute values in 64 bits, and put the sign in first.

STEPS
  1. The sign is minus when exactly one of the two is negative and the numerator is not 0
  2. Write the whole part, a / b, and stop if a mod b is 0
  3. Before each digit, note where the remainder r is
  4. The digit is 10r / b and r becomes 10r mod b
  5. When r comes back, put ( at its first place and ) at the end
BRUTEO(b), the same division with a list of the remainders searched each time
→
OPTIMALO(b)
↕ SCROLL
string fractionToDecimal(int numerator, int denominator) {
    long long a = numerator, b = denominator;  // −2^31 / −1 does not fit an int
    string s;
    if (a != 0 && (a < 0) != (b < 0)) s += '-';
    a = llabs(a); b = llabs(b);
    s += to_string(a / b);
    long long r = a % b;
    if (r == 0) return s;
    s += '.';
    unordered_map<long long, int> at;          // remainder -> where its digit went
    while (r != 0 && !at.count(r)) {
        at[r] = s.size();
        r *= 10;
        s += char('0' + r / b);
        r %= b;
    }
    if (r != 0) { s.insert(at[r], "("); s += ')'; }   // the remainder came back
    return s;
}
TIMEO(b)at most b different remainders before one repeats
SPACEO(b)the map of remainders
TRAP

A minus sign on zero. Testing only whether the signs differ writes 0 / −5 as −0. The answer is 0, so the sign also needs a numerator that is not 0.

INVARIANT · MATHS · LET THE NUMBER THEORY DO THE COUNTING · MATHS AND MODULAR ARITHMETIC
14 / DRILL UNIT 03 · A Finite Map Must Loop · 2 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

fractionToDecimal(1, 6)?

r = 1 gives the digit 1 and r = 4. r = 4 gives 6 and r = 4 again, so only the 6 repeats, from its first place.

DRILL 02 · RECALL

Why is the map keyed by the remainder and not by the digit?

Two places can make the same digit from different remainders, as 1 / 6 makes 1 then 6, while 1 / 7 makes 1 and 4 before any repeat. Only a repeated remainder repeats what follows.

INVARIANT · MATHS · LET THE NUMBER THEORY DO THE COUNTING · MATHS AND MODULAR ARITHMETIC
15 / MECHANISM UNIT 04 · EUCLID REDUCES THE SLOPE

DIVIDE BY THE GCD, FIX THE SIGN

Two points lie on one line through p exactly when their directions from p are parallel. Dividing a direction by the gcd of its parts and making the first non-zero part positive gives one exact pair of integers per line, so a map can count them.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · MATHS · LET THE NUMBER THEORY DO THE COUNTING · MATHS AND MODULAR ARITHMETIC
16 / DRILL UNIT 04 · Euclid Reduces the Slope

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

The key for the direction from (1, 4) to (−2, −2)?

dx = −3 and dy = −6, with gcd 3, so (−1, −2). dx is negative, so both signs flip.

DRILL 02 · RECALL

Why reduce by the gcd instead of keying the map by dy / dx?

Floating-point division rounds, so equal slopes can come out as different doubles, and a vertical line divides by 0. A reduced pair of integers is exact.

INVARIANT · MATHS · LET THE NUMBER THEORY DO THE COUNTING · MATHS AND MODULAR ARITHMETIC
17 / PROBLEM #05 · GCD · HARD

Max Points on a Line

HARD gcd ▶ SOLVE ON LEETCODE
SIGNAL — WHAT GIVES IT AWAY

Given up to 300 points, find the most that lie on one straight line.

INTUITION

Fix a point p. Every other point q lies on the line through p in the direction q − p, and two points share a line through p when their directions are parallel. Divide (dx, dy) by gcd(|dx|, |dy|) and make the first non-zero part positive, and parallel directions become the same pair of integers, with no division and no rounding. Count the pairs for each p. The best count plus p itself is the answer.

STEPS
  1. For each point p, start an empty count of directions
  2. For each later point q, take dx and dy from p to q
  3. Divide both by their gcd and fix the sign
  4. Add one to that direction; the best count plus 1 is a line through p
BRUTEO(n³), testing every pair's line against every point with a cross product
→
OPTIMALO(n² log C)
↕ SCROLL
int maxPoints(vector<vector<int>>& points) {
    int n = points.size(), best = 1;
    for (int i = 0; i < n; i++) {
        map<pair<int, int>, int> cnt;          // direction from p -> points along it
        for (int j = i + 1; j < n; j++) {
            int dx = points[j][0] - points[i][0], dy = points[j][1] - points[i][1];
            int g = __gcd(abs(dx), abs(dy));   // points are distinct, so g > 0
            dx /= g; dy /= g;
            if (dx < 0 || (dx == 0 && dy < 0)) { dx = -dx; dy = -dy; }   // one sign per line
            best = max(best, ++cnt[{dx, dy}] + 1);
        }
    }
    return best;
}
TIMEO(n² log C)n² pairs, each with one gcd of numbers up to 2 · 10⁴
SPACEO(n)the counts for one p
TRAP

Two signs for one line. (1, 1) and (−1, −1) are the same direction. Without fixing the sign, [[0, 0], [1, 1], [−1, −1]] counts 2 from every point, though all 3 are on one line.

INVARIANT · MATHS · LET THE NUMBER THEORY DO THE COUNTING · MATHS AND MODULAR ARITHMETIC
18 / MECHANISM UNIT 05 · COUNT THROUGH THE MULTIPLES

A DIVISOR COUNTS ITS MULTIPLES

Two numbers have a gcd of at least d when d divides both. So walk d down from the largest value, count the numbers sitting at d, 2d, 3d, and stop at the first d that finds two. The walks over all d cost M log M.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · MATHS · LET THE NUMBER THEORY DO THE COUNTING · MATHS AND MODULAR ARITHMETIC
19 / DRILL UNIT 05 · Count Through the Multiples

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

Common Divisors on 6 10 15?

gcd(6, 10) = 2, gcd(6, 15) = 3 and gcd(10, 15) = 5. Walking d down from 15, d = 5 is the first to find two numbers, 10 and 15.

DRILL 02 · RECALL

Why is the walk over every d only O(M log M)?

M / 1 + M / 2 + M / 3 + … is M times the harmonic sum, which grows like ln M.

INVARIANT · MATHS · LET THE NUMBER THEORY DO THE COUNTING · MATHS AND MODULAR ARITHMETIC
20 / PROBLEM #06 · GCD · MED

Common Divisors

MED gcd ▶ SOLVE ON CSESCSES does not rate its problems; the chip is this deck's estimate. Submit the Python tab as PyPy3.
SIGNAL — WHAT GIVES IT AWAY

Among up to 2 · 10⁵ numbers no larger than 10⁶, find the largest gcd of any two.

INTUITION

Trying every pair is 2 · 10¹⁰ gcds. Turn it round. Two of the numbers have a gcd of at least d exactly when d divides both of them, so the answer is the largest d that divides two of the numbers. Count how often each value occurs. For each d from the top down, add up the counts at d, 2d, 3d and so on, and stop at the first d whose total reaches 2. The sums over all d cost M / 1 + M / 2 + … = O(M log M).

STEPS
  1. Count how often each value occurs
  2. For d from the largest value down to 1
  3. Add up the counts at the multiples of d
  4. The first d with a total of 2 or more is the answer
BRUTEO(n² log M), a gcd for every pair
→
OPTIMALO(M log M)
↕ SCROLL
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    scanf("%d", &n);
    vector<int> x(n);
    for (int& v : x) scanf("%d", &v);
    int M = *max_element(x.begin(), x.end());
    vector<int> cnt(M + 1, 0);
    for (int v : x) cnt[v]++;
    for (int d = M; d >= 1; d--) {             // the largest d first
        int k = 0;
        for (int m = d; m <= M && k < 2; m += d) k += cnt[m];   // the numbers d divides
        if (k >= 2) { printf("%d\n", d); return 0; }
    }
}
TIMEO(M log M)M / d multiples for each d, and the harmonic sum is M log M
SPACEO(M)one count per value
TRAP

Marking values instead of counting them. With a seen flag in place of a count, two equal numbers look like one. [2, 2] has gcd 2, but each d then finds a single value and the search finds nothing.

INVARIANT · MATHS · LET THE NUMBER THEORY DO THE COUNTING · MATHS AND MODULAR ARITHMETIC
21 / MECHANISM UNIT 06 · CROSS OUT THE MULTIPLES

EACH PRIME CROSSES OUT FROM ITS SQUARE

A number left standing when the walk reaches it has no smaller prime factor, so it is prime. Its multiples below its square have a smaller factor and are crossed out already, so each prime starts at its square, and the sieve stops once the square passes the end.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · MATHS · LET THE NUMBER THEORY DO THE COUNTING · MATHS AND MODULAR ARITHMETIC
22 / DRILL UNIT 06 · Cross Out the Multiples · 1 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

Which of 4, 9, 25, 36 is not a T-prime?

4, 9 and 25 are squares of the primes 2, 3 and 5. 36 is 6², and 6 is not prime, so 36 has nine divisors.

DRILL 02 · RECALL

Why may each prime start crossing out at p × p?

A multiple k × p with k < p has a prime factor of k, smaller than p, whose turn came earlier and crossed it out.

INVARIANT · MATHS · LET THE NUMBER THEORY DO THE COUNTING · MATHS AND MODULAR ARITHMETIC
23 / PROBLEM #07 · PRIMES · EASY

T-primes

EASY primes ▶ SOLVE ON CODEFORCESCodeforces 230B, rated 1300.
SIGNAL — WHAT GIVES IT AWAY

For up to 10⁵ numbers as large as 10¹², say whether each has exactly three divisors.

INTUITION

Divisors come in pairs d and x / d, so an odd count means x is a perfect square, with its root r paired with itself. Three divisors are then 1, r and x, and nothing else divides x exactly when nothing else divides r, so r is prime. x ≤ 10¹² makes r ≤ 10⁶. A sieve of Eratosthenes to 10⁶ crosses out the multiples of each prime from its square and leaves the primes, and each query takes an exact integer square root and one look.

STEPS
  1. Sieve up to √(largest x), crossing out p², p² + p, … for each prime p
  2. For each x, take r, the integer square root
  3. x has three divisors when r² = x and r is prime
BRUTEO(n√X), trial division of every number
→
OPTIMALO(√X log log X + n)
↕ SCROLL
#include <bits/stdc++.h>
using namespace std;

long long isqrt(long long x) {                 // the exact floor of √x
    long long r = (long long)sqrt((double)x);
    while (r * r > x) r--;
    while ((r + 1) * (r + 1) <= x) r++;
    return r;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n;
    cin >> n;
    vector<long long> x(n);
    for (auto& v : x) cin >> v;
    int M = isqrt(*max_element(x.begin(), x.end()));
    vector<bool> prime(M + 1, true);
    prime[0] = prime[1] = false;
    for (long long p = 2; p * p <= M; p++)
        if (prime[p])
            for (long long q = p * p; q <= M; q += p) prime[q] = false;   // cross out p's multiples
    string out;
    for (long long v : x) {
        long long r = isqrt(v);
        out += r * r == v && prime[r] ? "YES\n" : "NO\n";   // 1, r and r² only
    }
    cout << out;
}
TIMEO(√X log log X + n)the sieve to 10⁶, then one root per number
SPACEO(√X)the sieve
TRAP

Any perfect square. A square has an odd number of divisors, but only the square of a prime has three. 16 = 4² has five, 1, 2, 4, 8 and 16.

INVARIANT · MATHS · LET THE NUMBER THEORY DO THE COUNTING · MATHS AND MODULAR ARITHMETIC
24 / PROBLEM #08 · PRIMES · MED

Closest Prime Numbers in Range

MED primes ▶ SOLVE ON LEETCODE
SIGNAL — WHAT GIVES IT AWAY

Among the primes between left and right, find the two closest, the smaller pair on a tie.

INTUITION

Sieve once up to right, then walk the numbers from left in order and keep the last prime seen. Each new prime makes a pair with it, and only neighbouring primes can be the closest pair, since a prime between two others is closer to both. Keep the pair with the smallest gap; a strict < keeps the earlier pair on a tie.

STEPS
  1. Sieve to right, with 0 and 1 not prime
  2. Walk x from left to right, keeping the previous prime
  3. A prime x pairs with the previous prime; keep the pair if its gap is strictly smaller
  4. Return [−1, −1] if fewer than two primes were met
BRUTEO(R√R), trial division of every number in the range
→
OPTIMALO(R log log R)
↕ SCROLL
vector<int> closestPrimes(int left, int right) {
    vector<bool> prime(right + 1, true);
    prime[0] = prime[1] = false;
    for (long long p = 2; p * p <= right; p++)
        if (prime[p])
            for (long long q = p * p; q <= right; q += p) prime[q] = false;
    vector<int> best = {-1, -1};
    int prev = -1;                             // the last prime met
    for (int x = left; x <= right; x++) {
        if (!prime[x]) continue;
        if (prev != -1 && (best[0] == -1 || x - prev < best[1] - best[0]))
            best = {prev, x};                  // < keeps the earlier pair on a tie
        prev = x;
    }
    return best;
}
TIMEO(R log log R)the sieve to right dominates the walk
SPACEO(R)the sieve
TRAP

Leaving 1 marked prime. The sieve crosses out multiples, and 1 is a multiple of nothing, so it must be cleared by hand. Otherwise left = 1, right = 2 returns [1, 2], not [−1, −1].

INVARIANT · MATHS · LET THE NUMBER THEORY DO THE COUNTING · MATHS AND MODULAR ARITHMETIC
25 / DRILL UNIT 06 · Cross Out the Multiples · 2 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

closestPrimes(1, 10)?

The primes are 2, 3, 5 and 7. 2 and 3 differ by 1, the only gap smaller than 2.

INVARIANT · MATHS · LET THE NUMBER THEORY DO THE COUNTING · MATHS AND MODULAR ARITHMETIC
26 / MECHANISM UNIT 07 · THE SMALLEST PRIME FACTOR

THE TABLE NAMES THE NEXT PRIME

A sieve that writes into each number the first prime that reaches it stores its smallest prime factor. Factoring is then looking up, dividing out every copy, and looking up again on what is left. Each prime p with exponent e multiplies the count of divisors by e + 1.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · MATHS · LET THE NUMBER THEORY DO THE COUNTING · MATHS AND MODULAR ARITHMETIC
27 / DRILL UNIT 07 · The Smallest Prime Factor · 1 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

Counting Divisors on 12?

12 = 2² × 3, so (2 + 1)(1 + 1) = 6: 1, 2, 3, 4, 6 and 12.

DRILL 02 · RECALL

Why must the spf sieve run p up to M and not stop at √M?

Stopping at √M still labels every composite, but a prime p above √M is reached only when the outer loop gets to p, which writes spf[p] = p.

INVARIANT · MATHS · LET THE NUMBER THEORY DO THE COUNTING · MATHS AND MODULAR ARITHMETIC
28 / DRILL UNIT 07 · The Smallest Prime Factor · 2 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

How many divisors does 360 = 2³ × 3² × 5 have?

(3 + 1)(2 + 1)(1 + 1) = 24. A divisor picks 0 to 3 twos, 0 to 2 threes and 0 or 1 five.

INVARIANT · MATHS · LET THE NUMBER THEORY DO THE COUNTING · MATHS AND MODULAR ARITHMETIC
29 / PROBLEM #09 · PRIMES · EASY

Counting Divisors

EASY primes ▶ SOLVE ON CSESCSES does not rate its problems; the chip is this deck's estimate. Submit the Python tab as PyPy3.
SIGNAL — WHAT GIVES IT AWAY

For up to 10⁵ numbers no larger than 10⁶, print how many divisors each has.

INTUITION

If x = p₁^e₁ · p₂^e₂ ⋯, a divisor picks 0 to e₁ copies of p₁, 0 to e₂ of p₂, and so on, so there are (e₁ + 1)(e₂ + 1)⋯ of them. Factoring by trial division costs √x per number. A sieve that stores spf[x], the smallest prime factor of every x, factors any x in O(log x): divide out spf[x], then spf of what is left, until 1. The sieve walks every prime p to the end and gives spf = p to each multiple still unlabelled.

STEPS
  1. Sieve spf up to the largest x, labelling multiples of each prime p not yet labelled
  2. For each x, take p = spf[x] and divide out every copy of p, counting e
  3. Multiply the answer by e + 1
  4. Repeat on what is left until it is 1
BRUTEO(n√M), trial division of every number
→
OPTIMALO(M log log M + n log M)
↕ SCROLL
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    scanf("%d", &n);
    vector<int> xs(n);
    for (int& v : xs) scanf("%d", &v);
    int M = *max_element(xs.begin(), xs.end());
    vector<int> spf(M + 1, 0);                 // spf[x]: the smallest prime factor of x
    for (int p = 2; p <= M; p++)
        if (spf[p] == 0)                       // nothing smaller divides p, so p is prime
            for (int q = p; q <= M; q += p)
                if (spf[q] == 0) spf[q] = p;
    for (int x : xs) {
        int d = 1;
        while (x > 1) {
            int p = spf[x], e = 0;
            while (x % p == 0) { x /= p; e++; }   // p^e divides x exactly
            d *= e + 1;                        // 0 to e copies of p
        }
        printf("%d\n", d);
    }
}
TIMEO(M log log M + n log M)the sieve, then O(log x) divisions per number
SPACEO(M)the spf array
TRAP

Sieving only to √M. That is enough to cross out every composite, but an spf table must also label the primes. With p only up to 1000, a prime x above 1000, such as 1009, keeps spf[x] = 0 and never divides out.

INVARIANT · MATHS · LET THE NUMBER THEORY DO THE COUNTING · MATHS AND MODULAR ARITHMETIC
30 / MECHANISM UNIT 08 · BLOCKS OF EQUAL QUOTIENTS

ONE BLOCK PER VALUE OF THE QUOTIENT

The sum of σ(i) is the sum of d × (n / d). The quotient n / d stays the same over a whole block of d, from l to n / (n / l), and takes fewer than 2√n values. One step per block adds the quotient times the sum of the block.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · MATHS · LET THE NUMBER THEORY DO THE COUNTING · MATHS AND MODULAR ARITHMETIC
31 / DRILL UNIT 08 · Blocks of Equal Quotients · 1 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

For n = 12, which d have n / d = 2?

l = 5 gives q = 12 / 5 = 2 and r = 12 / 2 = 6. 12 / 4 is 3 and 12 / 7 is 1.

DRILL 02 · RECALL

Why are there fewer than 2√n blocks?

Fewer than √n blocks start at a d up to √n. Past √n the quotient itself is below √n, so it has fewer than √n values left to take.

INVARIANT · MATHS · LET THE NUMBER THEORY DO THE COUNTING · MATHS AND MODULAR ARITHMETIC
32 / DRILL UNIT 08 · Blocks of Equal Quotients · 2 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

Sum of Divisors for n = 3?

σ(1) + σ(2) + σ(3) = 1 + 3 + 4 = 8. As blocks, 1 × 3 + (2 + 3) × 1 = 8.

INVARIANT · MATHS · LET THE NUMBER THEORY DO THE COUNTING · MATHS AND MODULAR ARITHMETIC
33 / PROBLEM #10 · FLOOR · HARD

Sum of Divisors

HARD floor ▶ SOLVE ON CSESCSES does not rate its problems; the chip is this deck's estimate. Submit the Python tab as PyPy3.
SIGNAL — WHAT GIVES IT AWAY

Find σ(1) + σ(2) + … + σ(n) mod 10⁹ + 7, where σ(i) is the sum of the divisors of i, for n up to 10¹².

INTUITION

Swap the order of the sum. A number d is a divisor of d, 2d, 3d, …, so of n / d numbers up to n, and the total is the sum of d · (n / d) over d from 1 to n. That is still 10¹² terms, but n / d takes fewer than 2√n different values. For d from l, every d up to r = n / (n / l) gives the same q = n / l, so the whole block adds q · (l + … + r). The block sum is (l + r)(r − l + 1) / 2, and one of the two factors is even, so halve that one before taking anything mod P.

STEPS
  1. Start at l = 1
  2. q = n / l, and the block of d with the same q ends at r = n / q
  3. Add q · (l + … + r), halving the even factor of (l + r)(r − l + 1) first
  4. Move l to r + 1 until it passes n
BRUTEO(n log n), adding each d to every multiple of it
→
OPTIMALO(√n)
↕ SCROLL
#include <bits/stdc++.h>
using namespace std;

int main() {
    const long long P = 1000000007;
    long long n;
    scanf("%lld", &n);
    long long total = 0;
    for (long long l = 1; l <= n; ) {
        long long q = n / l, r = n / q;        // every d in [l, r] has n / d = q
        long long a = l + r, b = r - l + 1;    // l + ... + r = a * b / 2
        if (a % 2 == 0) a /= 2; else b /= 2;   // halve the even one before any mod
        long long s = (a % P) * (b % P) % P;
        total = (total + q % P * s) % P;       // each d divides q numbers up to n
        l = r + 1;
    }
    printf("%lld\n", total);
}
TIMEO(√n)fewer than 2√n blocks
SPACEO(1)a few numbers
TRAP

Halving after the mod. (a mod P)(b mod P) / 2 is not ab / 2 mod P once a or b reaches P, since the reduced product can be odd. n = 10⁹ still passes and n = 10¹² fails. Halve the even factor first, while it is exact.

INVARIANT · MATHS · LET THE NUMBER THEORY DO THE COUNTING · MATHS AND MODULAR ARITHMETIC
34 / MECHANISM UNIT 09 · COUNT THE FIVES

EACH POWER OF 5 ADDS A ROUND

A trailing zero needs a 2 and a 5, and the 5s are scarcer. The multiples of 5 each give one, the multiples of 25 a second, of 125 a third. Dividing n by 5 again and again counts exactly those, one round per power of 5.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · MATHS · LET THE NUMBER THEORY DO THE COUNTING · MATHS AND MODULAR ARITHMETIC
35 / DRILL UNIT 09 · Count the Fives

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

trailingZeroes(30)?

30 / 5 = 6 multiples of 5, and 30 / 25 = 1 of them, 25, has a second 5. 6 + 1 = 7.

DRILL 02 · RECALL

Why count the 5s in n! and not the 2s?

Every second number gives a 2 and only every fifth a 5, so the 5s run out first and decide how many 10s there are.

INVARIANT · MATHS · LET THE NUMBER THEORY DO THE COUNTING · MATHS AND MODULAR ARITHMETIC
36 / PROBLEM #11 · FLOOR · MED

Factorial Trailing Zeroes

MED floor ▶ SOLVE ON LEETCODE
SIGNAL — WHAT GIVES IT AWAY

Count the trailing zeroes of n!.

INTUITION

Each trailing zero is a factor 10 = 2 · 5, and n! has more 2s than 5s, so count the 5s. Every multiple of 5 up to n gives one, and there are n / 5 of them. Multiples of 25 give a second, n / 25 more, multiples of 125 a third, and so on. Dividing n by 5 again and again produces exactly n / 5, n / 25, n / 125, … to add up.

STEPS
  1. z = 0
  2. While n > 0, divide n by 5 and add the result to z
  3. Return z
BRUTEO(n log n), counting the 5s in each factor
→
OPTIMALO(log n)
↕ SCROLL
int trailingZeroes(int n) {
    int z = 0;
    while (n > 0) {
        n /= 5;                                // the multiples of 5, then 25, then 125, ...
        z += n;
    }
    return z;
}
TIMEO(log n)one division by 5 per power of 5
SPACEO(1)one counter
TRAP

Counting each multiple of 5 once. 25 = 5 · 5 brings two 5s. n / 5 alone gives 25! five zeroes; it has six.

INVARIANT · MATHS · LET THE NUMBER THEORY DO THE COUNTING · MATHS AND MODULAR ARITHMETIC
37 / MECHANISM UNIT 10 · SQUARE AND MULTIPLY

ONE SQUARE PER BIT

a^b is the product of a^(2^k) over the bits k set in b. Walk the bits from the lowest. Each round multiplies r by the current power when the bit is set, then squares the power. b of 10⁹ takes 30 rounds, not 10⁹ products.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · MATHS · LET THE NUMBER THEORY DO THE COUNTING · MATHS AND MODULAR ARITHMETIC
38 / DRILL UNIT 10 · Square and Multiply · 1 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

power(3, 13, 1000)?

13 = 1101₂, so 3¹³ = 3⁸ × 3⁴ × 3 = 1594323, and mod 1000 that is 323.

DRILL 02 · RECALL

How many squarings does power make for b = 10⁹?

10⁹ is below 2³⁰, so it has 30 bits, and each bit costs one squaring and at most one multiplication.

INVARIANT · MATHS · LET THE NUMBER THEORY DO THE COUNTING · MATHS AND MODULAR ARITHMETIC
39 / DRILL UNIT 10 · Square and Multiply · 2 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · RECALL

Why reduce a mod m before the loop and after every product?

Two factors below 10⁹ + 7 multiply to below 1.1 × 10¹⁸, which fits a 64-bit integer. Unreduced, a² would overflow after one round.

INVARIANT · MATHS · LET THE NUMBER THEORY DO THE COUNTING · MATHS AND MODULAR ARITHMETIC
40 / PROBLEM #12 · MOD · EASY

Exponentiation

EASY mod ▶ SOLVE ON CSESCSES does not rate its problems; the chip is this deck's estimate. Submit the Python tab as PyPy3.
SIGNAL — WHAT GIVES IT AWAY

Compute 2 · 10⁵ values a^b mod 10⁹ + 7, with a and b up to 10⁹.

INTUITION

Multiplying b times is 10⁹ steps per query. Write b in binary instead. a^b is the product of a^(2^k) over the bits k set in b, and each a^(2^k) is the square of the one before. So walk the bits of b from the lowest: when a bit is set, multiply the result by the current power, then square the power and shift b. Every product is taken mod P, and with both factors below P it fits in 64 bits.

STEPS
  1. r = 1, and a is reduced mod P
  2. While b > 0, multiply r by a when the low bit of b is set
  3. Square a and shift b right
  4. r is a^b mod P, with 0⁰ = 1
BRUTEO(b), multiplying b times
→
OPTIMALO(log b)
↕ SCROLL
#include <bits/stdc++.h>
using namespace std;

long long power(long long a, long long b, long long m) {   // a^b mod m
    long long r = 1 % m;
    a %= m;
    while (b > 0) {
        if (b & 1) r = r * a % m;              // this bit of b is set
        a = a * a % m;                         // a, a^2, a^4, a^8, ...
        b >>= 1;
    }
    return r;
}

int main() {
    const long long P = 1000000007;
    int n;
    scanf("%d", &n);
    while (n--) {
        long long a, b;
        scanf("%lld %lld", &a, &b);
        printf("%lld\n", power(a, b, P));
    }
}
TIMEO(log b)one square per bit of b
SPACEO(1)two numbers
TRAP

Taking 0⁰ as 0. A shortcut that returns 0 whenever a is 0 breaks the statement's rule that 0⁰ = 1. With r starting at 1 and no shortcut, b = 0 returns 1 for every a.

INVARIANT · MATHS · LET THE NUMBER THEORY DO THE COUNTING · MATHS AND MODULAR ARITHMETIC
41 / MECHANISM UNIT 11 · FERMAT SHRINKS THE EXPONENT

THE POWERS REPEAT EVERY P − 1 STEPS

For a prime P, a^(P − 1) = 1 whenever P does not divide a. So the powers of a repeat every P − 1 exponents, and a huge exponent can be cut mod P − 1 before the last power. The bench's P is 13, so the powers of 2 repeat every 12.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · MATHS · LET THE NUMBER THEORY DO THE COUNTING · MATHS AND MODULAR ARITHMETIC
42 / DRILL UNIT 11 · Fermat Shrinks the Exponent

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

2^100 mod 13?

100 mod 12 = 4, so 2¹⁰⁰ = 2⁴ = 16, and 16 mod 13 = 3.

DRILL 02 · RECALL

Why is the exponent cut mod P − 1 and not mod P?

Fermat's little theorem. The powers of a come back to 1 after P − 1 steps, so exponents that differ by a multiple of P − 1 give the same value.

INVARIANT · MATHS · LET THE NUMBER THEORY DO THE COUNTING · MATHS AND MODULAR ARITHMETIC
43 / PROBLEM #13 · MOD · MED

Exponentiation II

MED mod ▶ SOLVE ON CSESCSES does not rate its problems; the chip is this deck's estimate. Submit the Python tab as PyPy3.
SIGNAL — WHAT GIVES IT AWAY

Compute a^(b^c) mod 10⁹ + 7, where b^c can have billions of digits.

INTUITION

P = 10⁹ + 7 is prime, so Fermat's little theorem gives a^(P − 1) ≡ 1 for any a that P does not divide. Powers of a then repeat every P − 1 steps, and the exponent b^c can be cut to b^c mod (P − 1), which square and multiply computes without ever writing b^c down. The cut is mod P − 1, not mod P. The only a that P divides here is 0, and b^c mod (P − 1) is 0 only when b is 0, so 0⁰ = 1 still comes out right.

STEPS
  1. e = b^c mod (P − 1), by square and multiply
  2. Print a^e mod P, again by square and multiply
BRUTEO(b^c), impossible: b^c has up to 9 · 10⁹ digits
→
OPTIMALO(log b + log c)
↕ SCROLL
#include <bits/stdc++.h>
using namespace std;

long long power(long long a, long long b, long long m) {   // a^b mod m
    long long r = 1 % m;
    a %= m;
    while (b > 0) {
        if (b & 1) r = r * a % m;              // this bit of b is set
        a = a * a % m;                         // a, a^2, a^4, a^8, ...
        b >>= 1;
    }
    return r;
}

int main() {
    const long long P = 1000000007;
    int n;
    scanf("%d", &n);
    while (n--) {
        long long a, b, c;
        scanf("%lld %lld %lld", &a, &b, &c);
        long long e = power(b, c, P - 1);      // a^(P − 1) = 1, so cut the exponent mod P − 1
        printf("%lld\n", power(a, e, P));
    }
}
TIMEO(log b + log c)two fast powers per query
SPACEO(1)a few numbers
TRAP

Cutting the exponent mod P. Powers of a repeat every P − 1 steps, not every P. The samples' exponents are all below P, so the wrong cut passes them. It fails on a = 2, b = 2, c = 30, where b^c = 2³⁰ is past P.

INVARIANT · MATHS · LET THE NUMBER THEORY DO THE COUNTING · MATHS AND MODULAR ARITHMETIC
44 / MECHANISM UNIT 12 · FACTORIALS AND THEIR INVERSES

ONE INVERSE, THEN WALK DOWN THE TABLE

A division mod a prime is a multiplication by the inverse, and Fermat gives it as x^(P − 2). Take one inverse, of the largest factorial, by a fast power. 1 / (i − 1)! = i / i! gives every smaller one by one multiplication.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · MATHS · LET THE NUMBER THEORY DO THE COUNTING · MATHS AND MODULAR ARITHMETIC
45 / DRILL UNIT 12 · Factorials and Their Inverses · 1 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

C(5, 2) mod 7 from f = 1 1 2 6 3 1, inv[2] = 4, inv[3] = 6?

f[5] × inv[2] × inv[3] = 1 × 4 × 6 = 24, and 24 mod 7 = 3. C(5, 2) = 10, and 10 mod 7 = 3 too.

DRILL 02 · RECALL

Why take one inverse by a power and the rest by inv[i − 1] = inv[i] × i?

A fast power is about 30 squarings. The walk down costs one multiplication per entry, so a table of 10⁶ inverses takes 10⁶ steps, not 3 · 10⁷.

INVARIANT · MATHS · LET THE NUMBER THEORY DO THE COUNTING · MATHS AND MODULAR ARITHMETIC
46 / PROBLEM #14 · MOD · MED

Binomial Coefficients

MED mod ▶ SOLVE ON CSESCSES does not rate its problems; the chip is this deck's estimate. Submit the Python tab as PyPy3.
SIGNAL — WHAT GIVES IT AWAY

Answer 10⁵ queries C(a, b) mod 10⁹ + 7 with a up to 10⁶.

INTUITION

C(a, b) = a! / (b! (a − b)!), but a division mod P is a multiplication by an inverse. By Fermat, x^(P − 2) is the inverse of x mod P. Store every factorial up to the largest a, then one inverse, of the largest factorial, by a fast power. The rest come down the table for free, since 1 / (i − 1)! = i / i!. Each query is then two multiplications.

STEPS
  1. f[i] = i! mod P for every i up to the largest a
  2. inv[M] = f[M]^(P − 2), and inv[i − 1] = inv[i] · i going down
  3. C(a, b) = f[a] · inv[b] · inv[a − b] mod P
BRUTEO(a) a query, building Pascal's triangle row by row
→
OPTIMALO(M + n)
↕ SCROLL
#include <bits/stdc++.h>
using namespace std;

long long power(long long a, long long b, long long m) {   // a^b mod m
    long long r = 1 % m;
    a %= m;
    while (b > 0) {
        if (b & 1) r = r * a % m;              // this bit of b is set
        a = a * a % m;                         // a, a^2, a^4, a^8, ...
        b >>= 1;
    }
    return r;
}

int main() {
    const long long P = 1000000007;
    int n;
    scanf("%d", &n);
    vector<int> a(n), b(n);
    for (int i = 0; i < n; i++) scanf("%d %d", &a[i], &b[i]);
    int M = *max_element(a.begin(), a.end());
    vector<long long> f(M + 1), inv(M + 1);
    f[0] = 1;
    for (int i = 1; i <= M; i++) f[i] = f[i - 1] * i % P;
    inv[M] = power(f[M], P - 2, P);            // Fermat: x^(P − 2) is 1 / x
    for (int i = M; i > 0; i--) inv[i - 1] = inv[i] * i % P;   // 1 / (i − 1)! = i / i!
    for (int i = 0; i < n; i++)
        printf("%lld\n", f[a[i]] * inv[b[i]] % P * inv[a[i] - b[i]] % P);
}
TIMEO(M + n)two passes over the table and one fast power, then O(1) a query
SPACEO(M)the two tables
TRAP

Dividing the reduced factorials. f[a] / (f[b] · f[a − b]) as an integer division is right only while a! is below P. It passes all three samples, and 13! is the first factorial past P, so C(13, 1) already comes out 0.

INVARIANT · MATHS · LET THE NUMBER THEORY DO THE COUNTING · MATHS AND MODULAR ARITHMETIC
47 / PROBLEM #15 · MOD · MED

Beautiful Numbers

MED mod ▶ SOLVE ON CODEFORCESCodeforces 300C, rated 1800.
SIGNAL — WHAT GIVES IT AWAY

Count the numbers of length n, made of the digits a and b only, whose digit sum is also made of a and b only, mod 10⁹ + 7.

INTUITION

There are 2ⁿ numbers to test, but the digit sum depends only on how many digits are a. With i of them it is a·i + b·(n − i), and the C(n, i) ways to place the a digits all share it. So loop i from 0 to n, test that one sum digit by digit, and add C(n, i) when it passes. The factorial tables of row 14 give each C(n, i) in O(1).

STEPS
  1. Build f and inv up to n
  2. For i from 0 to n, the sum is a·i + b·(n − i)
  3. Test every digit of the sum against a and b
  4. If all pass, add C(n, i)
BRUTEO(2ⁿ · n), testing every number
→
OPTIMALO(n log n)
↕ SCROLL
#include <bits/stdc++.h>
using namespace std;

long long power(long long a, long long b, long long m) {   // a^b mod m
    long long r = 1 % m;
    a %= m;
    while (b > 0) {
        if (b & 1) r = r * a % m;              // this bit of b is set
        a = a * a % m;                         // a, a^2, a^4, a^8, ...
        b >>= 1;
    }
    return r;
}

int main() {
    const long long P = 1000000007;
    int a, b, n;
    scanf("%d %d %d", &a, &b, &n);
    vector<long long> f(n + 1), inv(n + 1);
    f[0] = 1;
    for (int i = 1; i <= n; i++) f[i] = f[i - 1] * i % P;
    inv[n] = power(f[n], P - 2, P);
    for (int i = n; i > 0; i--) inv[i - 1] = inv[i] * i % P;
    long long total = 0;
    for (int i = 0; i <= n; i++) {             // i digits are a, n − i are b
        int s = a * i + b * (n - i);           // the sum depends only on i
        bool good = true;
        for (; s > 0; s /= 10)                 // every digit of the sum
            if (s % 10 != a && s % 10 != b) good = false;
        if (good) total = (total + f[n] * inv[i] % P * inv[n - i]) % P;   // C(n, i) placings
    }
    printf("%lld\n", total);
}
TIMEO(n log n)n + 1 sums, each with up to 8 digits
SPACEO(n)the two tables
TRAP

Testing one digit of the sum. An if where the while belongs checks only the last digit. Both samples pass, but with a = 2, b = 6 and n = 2, the sum 6 + 6 = 12 ends in a good digit and holds a 1, so 66 is counted and the answer 0 comes out 1.

INVARIANT · MATHS · LET THE NUMBER THEORY DO THE COUNTING · MATHS AND MODULAR ARITHMETIC
48 / DRILL UNIT 12 · Factorials and Their Inverses · 2 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

Beautiful Numbers with a = 1, b = 2, n = 2?

11 has sum 2, a good number. 12 and 21 have sum 3 and 22 has sum 4, which are not. Only i = 2 passes, and C(2, 2) = 1.

INVARIANT · MATHS · LET THE NUMBER THEORY DO THE COUNTING · MATHS AND MODULAR ARITHMETIC
49 / SIGNALS WHEN YOU SEE X, REACH FOR Y

WHICH MOVE, AND WHAT GIVES IT AWAY

Twelve moves, and each has a phrase in the statement that gives it away.

A NUMBER TOO LONG FOR ANY TYPE, AS AN ARRAY OF DIGITS

add from the right; stop at the first digit below 9

CARRYO(n)
A NUMBERING WITH NO ZERO: A TO Z, THEN AA

subtract 1, then take the remainder and divide

BIJECTIVE BASEO(log n)
REPEAT A STEP ON A NUMBER: DOES IT END OR LOOP

the values are finitely many, so watch for one coming back

FINITE MAPO(cycle)
POINTS ON ONE LINE, OR ONE DIRECTION

divide (dx, dy) by their gcd and fix the sign

REDUCED DIRECTIONO(n² log C)
THE LARGEST GCD OR A COUNT OF DIVISIBLE PAIRS

for each d, count the numbers at its multiples

MULTIPLESO(M log M)
PRIMES UP TO 10⁶, OR IN A RANGE

cross out each prime's multiples from its square

SIEVEO(M log log M)
FACTOR MANY NUMBERS UP TO 10⁶

a table of smallest prime factors, then divide down

SPF TABLEO(log x) each
A SUM OF n / d FOR n UP TO 10¹²

group the d whose quotient is the same

QUOTIENT BLOCKSO(√n)
THE ZEROES OR PRIME POWERS IN n!

add n / p, n / p², n / p³, …

LEGENDREO(log n)
a^b WITH b UP TO 10⁹ OR MORE

square and multiply over the bits of b

FAST POWERO(log b)
AN EXPONENT THAT IS ITSELF A HUGE POWER

cut the exponent mod P − 1, by Fermat

FERMATO(log b)
C(n, k) mod P, MANY TIMES

factorials, one inverse by a power, then walk down

INVERSE FACTORIALSO(M + q)
INVARIANT · MATHS · LET THE NUMBER THEORY DO THE COUNTING · MATHS AND MODULAR ARITHMETIC
50 / RECALL RETRIEVAL, NOT RECOGNITION · 1 OF 2

NAME THE MOVE FROM THE STATEMENT

DRILL 01 · TRANSFER

Pow(x, n) for n up to 2³¹ − 1, without recursion. Which move?

Walk the bits of n, squaring x each round and multiplying it in when the bit is set. recursion-1 halves n with a call instead; the work is the same 31 rounds.

DRILL 02 · TRANSFER

Count Primes asks how many primes lie below n, for n up to 5 · 10⁶. Which move?

Sieve up to n and count what is left standing. bit-manipulation runs the same sieve; testing each number by trial division would be n√n.

INVARIANT · MATHS · LET THE NUMBER THEORY DO THE COUNTING · MATHS AND MODULAR ARITHMETIC
51 / RECALL RETRIEVAL, NOT RECOGNITION · 2 OF 2

NAME THE MOVE FROM THE STATEMENT

DRILL 01 · TRANSFER

Count Good Numbers needs 5^a × 4^b mod 10⁹ + 7 for a and b up to 10¹⁵. Which move?

Two fast powers of about 50 rounds each. Fermat could cut the exponents mod P − 1 first, but at 10¹⁵ the bits are few enough without it.

DRILL 02 · RECALL

Why does C(n, k) mod P need P to be prime?

With P prime, every x from 1 to P − 1 has an inverse, and Fermat gives it as x^(P − 2). Mod 10, 2 has none, so dividing by 2! would be impossible.

INVARIANT · MATHS · LET THE NUMBER THEORY DO THE COUNTING · MATHS AND MODULAR ARITHMETIC
52 / TRAPS PLAUSIBLE, WRONG, AND SILENT

SIX WAYS TO BE PLAUSIBLY WRONG

None of these fail the samples. Each one fails a hidden test.

CUTTING THE EXPONENT MOD P

Fermat makes the powers of a repeat every P − 1 steps. An exponent cut mod P passes every sample below P and fails beyond it.

DIVIDING THE REDUCED FACTORIALS

f[a] / (f[b] · f[a − b]) on numbers already taken mod P is no longer a division of the factorials. Multiply by inverses.

LEAVING 1 MARKED PRIME

A sieve crosses out multiples, and 1 is a multiple of nothing. Clear 0 and 1 by hand.

ANY PERFECT SQUARE

A square has an odd number of divisors, but only a prime's square has three. Check the root against the sieve.

HALVING AFTER THE MOD

(a mod P)(b mod P) can be odd when ab is even. Halve the even factor while it is still exact.

A MINUS SIGN ON ZERO

Signs that differ make a negative answer, unless the numerator is 0. 0 / −5 is 0.

INVARIANT · MATHS · LET THE NUMBER THEORY DO THE COUNTING · MATHS AND MODULAR ARITHMETIC
53 / CHEATSHEET REVISION SURFACE

ONE SCREEN, THE WHOLE DECK

Twelve moves on one page. The right column is the cue for each.

ALGORITHM
TIME
SPACE
REACH FOR IT WHEN
Carry
O(n)
O(1)
from the right; a digit below 9 takes the 1 and returns
Bijective base
O(log n)
O(log n)
n−−, letter n % 26, n /= 26, reverse
Finite map
O(cycle)
O(1) or O(b)
Floyd's two walkers, or a map of what was seen
Reduced direction
O(n² log C)
O(n)
(dx, dy) / gcd, first non-zero part positive
Multiples
O(M log M)
O(M)
d from the top; add cnt at d, 2d, …; stop at 2
Sieve
O(M log log M)
O(M)
clear 0, 1; each prime crosses out from p · p
SPF table
O(M log log M)
O(M)
spf[q] = p if unset; divide out, d *= e + 1
Quotient blocks
O(√n)
O(1)
r = n / (n / l); add q · (l + … + r); l = r + 1
Legendre
O(log n)
O(1)
while n: n /= p; z += n
Fast power
O(log b)
O(1)
bit set: r = r·a; then a = a·a; b >>= 1
Fermat
O(log b)
O(1)
a^(b^c) = a^(b^c mod (P − 1)) for prime P
Inverse factorials
O(M + q)
O(M)
inv[M] = f[M]^(P − 2); inv[i − 1] = inv[i] · i
INVARIANT · MATHS · LET THE NUMBER THEORY DO THE COUNTING · MATHS AND MODULAR ARITHMETIC
54 / CLOSE MODULE 28 · MATHS AND MODULAR ARITHMETIC

TAKE IT NOW

The carry stopped at the first digit below 9; a base with no 0 shifted before it divided; a remainder that came back repeated the digits; the gcd gave each line one direction; a divisor counted the numbers at its multiples; the sieve crossed out from each prime's square, and its smallest prime factors factored a number by looking up; the quotient n / d came in blocks; the fives in n! came one round per power of 5; square and multiply walked the bits; Fermat cut the exponent mod P − 1; and one inverse walked down the factorial table. Pow(x, n) is in recursion-1 and Count Primes in bit-manipulation.

00%
OF THIS DECK SOLVED
← ALL TOPICS← BASICS← BIT MANIPULATION

Module 28. Fifteen problems: seven on LeetCode, six on CSES and two on Codeforces. Next in the sheet: advanced strings.

INVARIANT · MATHS · LET THE NUMBER THEORY DO THE COUNTING · MATHS AND MODULAR ARITHMETIC
■ TOO SMALL TO READ
1280×720
INVARIANT · MODULE 28 · MATHS AND MODULAR ARITHMETIC

This one needs a laptop

Not a preference — an arithmetic one. Every slide is a fixed 1280 × 720 stage: a graph animating beside the code that drives it, with the problems laid out two columns wide. It scales as a single piece, so on a screen this size the body text comes out around 4px tall.

Shrinking it further would not help, and rebuilding it to reflow would mean losing the thing that makes it worth reading.

YOUR SCREEN0 × 0
NEEDED1060 × 610
WHAT IS WAITING ON THE LAPTOP
WATCH IT RUN, THEN RUN IT FROM MEMORY
Your progress is saved per device, so anything you tick on the laptop will be waiting there.