Math & Number Theory

Math problems often hide a shortcut that beats counting one step at a time. Instead of multiplying a number by itself n times, you can square it and halve the exponent over and over - a bit like doubling a recipe by doubling it again and again rather than adding one portion at a time.

Example: 2^10 equals (2^5)^2, and 2^5 equals (2^2)^2 * 2. That's only a handful of multiplications - roughly as many as it takes to halve 10 down to 1 - instead of ten separate ones. Spotting the hidden identity is what turns a slow loop into just a few quick steps.

Euclid's insight: gcd(a, b) = gcd(b, a mod b), repeating until the remainder is 0. It converges in O(log min(a,b)) steps. LCM follows directly: lcm(a,b) = a / gcd(a,b) * b — divide before multiplying to avoid overflow.

To test one number for primality, trial-divide only up to √n — if no divisor is found by then, none exists (divisors come in pairs straddling √n). To find all primes up to n, the Sieve of Eratosthenes is far better than testing each: mark every multiple of each prime as composite, leaving the primes unmarked, in O(n log log n).

When answers grow astronomically (counting paths, combinatorics), problems ask for the result modulo 1e9+7 (a large prime) so it fits in a 64-bit integer. The arithmetic rules let you apply the mod at every step instead of at the end:

Apply the mod after every multiply/add to keep numbers bounded — don't compute the giant number first.

Computing x^n by multiplying n times is O(n). Binary exponentiation squares the base and halves the exponent: x^n = (x^(n/2))^2, handling the odd case with one extra multiply — O(log n). Combined with a mod at each step, it computes x^n mod m for huge n, which is the backbone of modular inverse and many counting problems.