Advanced number theory techniques

Senior-level number theory problems tend to combine several ideas at once: modular arithmetic for remainders, integer representations for self-similar structures, cycle detection for processes that repeat, and lcm or gcd reasoning to narrow down a search space.

Modular arithmetic

When an answer is requested modulo a prime, Python's built-in pow(a, b, m) computes a^b mod m in $O(\log b)$ time, without ever materializing the full, astronomically large value of a^b.

The modular inverse of a modulo m is the number x such that a * x is congruent to 1 modulo m, and Python computes it directly with pow(a, -1, m). This is what lets you "divide" under a modulus: to compute (b / a) mod m, compute b * pow(a, -1, m) mod m instead, since ordinary division does not make sense modulo m. The inverse only exists when gcd(a, m) = 1; if it does not, pow(a, -1, m) raises an exception rather than returning a meaningless answer.

Every intermediate value in modular arithmetic stays bounded by m, so even with a, b, and m each as large as $10^9$, the product a * b still fits comfortably before you take the result modulo m.

Self-similar sets, represented as integers

A self-similar set is built by repeating a transformation on itself, at every scale. The Cantor set removes the middle third of an interval and repeats the same removal on each remaining third. Constructions like this often come with a natural fraction, some position p / n inside an interval, that changes at every step.

Representing that fraction with floating-point numbers accumulates rounding error with every iteration, which can make two truly equal fractions look different, and can make a genuine cycle in the sequence go undetected. Keeping the numerator as a plain integer over a fixed denominator avoids this entirely, and lets a dictionary reliably tell you when a value has been seen before.

Iterated maps and cycle detection

Applying a function f repeatedly to a value drawn from a finite set of possible states must eventually repeat a state, since there are only finitely many states to visit. Track each state's first iteration number in a dictionary; the moment a state reappears, you have found both where the cycle starts and how long it is.

This matters because some problems ask for the state after an enormous number of iterations, such as $10^{18}$, far too many to simulate directly. If the sequence enters a cycle of length L starting at iteration C, the state at iteration N (for any N >= C) is the same as the state at iteration C + ((N - C) mod L), a single computation instead of $10^{18}$ steps.

A worked example

Take the tent map f(r) = 2 * min(r, 1 - r) on fractions r in [0, 1]. Since min(r, 1 - r) never exceeds 0.5, f(r) never exceeds 1, so the map stays inside [0, 1] at every step, which is exactly the property a self-similar construction like this needs.

Start at r = 1/5, represented as the numerator 1 over a fixed denominator of 5. In terms of the numerator alone, one step of the map is new_p = 2 * min(p, 5 - p). From p = 1: min(1, 4) = 1, so the next numerator is 2. From p = 2: min(2, 3) = 2, so the next numerator is 4. From p = 4: min(4, 1) = 1, so the next numerator is 2 again, a value already seen. The sequence of numerators is 1, 2, 4, 2, 4, 2, 4, ...; it enters a cycle of length 2 starting at iteration 1, alternating between 2 and 4 forever.

1import sys2
3
4def main() -> None:5    data = sys.stdin.read().split()6    a, m = int(data[0]), int(data[1])7    p, n = int(data[2]), int(data[3])8
9    # Modular inverse: the x such that a * x = 1 (mod m).10    inv = pow(a, -1, m)11    print(f"Inverse of {a} mod {m}: {inv}")12    print(f"Check: {a} * {inv} = {(a * inv) % m} (mod {m})")13
14    # Cycle detection on the tent map f(p/n) = 2 * min(p/n, 1 - p/n),15    # tracked through the integer numerator p over a fixed denominator n.16    seen = {p: 0}17    sequence = [p]18
19    state = p20    while True:21        state = 2 * min(state, n - state)22        if state in seen:23            cycle_start = seen[state]24            cycle_length = len(sequence) - cycle_start25            break26        seen[state] = len(sequence)27        sequence.append(state)28
29    print(f"Numerators over {n}: {sequence}")30    print(f"Cycle starts at iteration {cycle_start}, length {cycle_length}")31
32
33if __name__ == "__main__":34    main()

7 11 1 5

Inverse of 7 mod 11: 8
Check: 7 * 8 = 1 (mod 11)
Numerators over 5: [1, 2, 4]
Cycle starts at iteration 1, length 2

Common mistakes

Using floating-point arithmetic to represent fractions in a self-similar construction is the most damaging mistake, since accumulated rounding error can make cycle detection either miss a real cycle or report a false one. Keep numerators as plain integers over a shared denominator instead.

Another mistake is calling pow(a, -1, m) without first checking that gcd(a, m) = 1. If the two are not coprime, no inverse exists, and the call raises an exception rather than silently returning a wrong answer; check the gcd first if the input might not guarantee coprimality.

A third mistake is assuming a simulated sequence that has not cycled yet after many iterations is simply a very long cycle. Since any iterated map on a finite state space must eventually repeat, a sequence that runs far longer than the state space's size without repeating points to a bug in the simulation, not an unusually large cycle.

Why this works, and the cost

Modular exponentiation and modular inverse both run in $O(\log m)$ time, the exponentiation by repeated squaring and the inverse through the extended Euclidean algorithm. Representing a self-similar construction with integers keeps every comparison exact, so cycle detection is reliable rather than approximate. Once a cycle's start and length are known, answering a query about any iteration count, however large, costs a single modulo computation instead of a simulation.

Constraints and search

When several constraints bound the same value, for instance a value that must be divisible by both 5 and 7, the tightest single constraint that captures both is divisibility by their lcm, lcm(5, 7) = 35. Multiple period-like constraints combine the same way: a solution's overall period is the lcm of every individual constraint's own period, which is often far smaller than the product of all the individual bounds, and lets a search consider only the multiples of that lcm instead of every candidate value.