Mathematical Algorithms

Compute the greatest common divisor by repeatedly replacing (a, b) with (b, a mod b); the extended form also finds x, y with ax + by = gcd.

Compute the least common multiple as a / gcd(a, b) * b, dividing before multiplying to avoid overflow.

Find every prime up to n by crossing out multiples of each prime starting from its square, in O(n log log n).

Decompose n into prime powers by trial division up to sqrt(n), or in O(log n) per query using a precomputed smallest-prime-factor table.

Compute x^n in O(log n) multiplications by squaring x and multiplying it in wherever the binary expansion of n has a 1 bit.

Do arithmetic on remainders: reduce after every add, subtract and multiply so results stay small, and use a prime modulus like 1e9+7 so division works.

Find a^-1 mod m — the number that multiplies a to 1 — via Fermat's little theorem when m is prime or the extended Euclidean algorithm for any coprime m.

Count arrangements and selections: nCr via factorial and inverse-factorial tables mod p, Pascal's triangle, stars and bars, and inclusion-exclusion.