Modular arithmetic · 1 of 2 Advanced
Modular arithmetic basics
Keep huge answers small with remainders, raise a number to a large power by repeated squaring, and divide by a prime modulus with Fermat's inverse.
Books1
Links4
- Modular Arithmetic Modular exponentiation and two ways to find an inverse, with C++ templates for a remainder type and graded practice problems. usaco.guide (opens in a new tab)
- Binary Exponentiation Fast power with a recursive and an iterative implementation, then the same squaring applied to Fibonacci numbers, repeated permutations and counting paths in a graph. cp-algorithms.com (opens in a new tab)
- Modular Multiplicative Inverse The inverse by Fermat’s theorem and by the extended Euclidean algorithm, and every inverse below m in linear time. cp-algorithms.com (opens in a new tab)
- 快速幂 (Fast power) Iterative and recursive fast power, then modular powers, Fibonacci numbers, repeated permutations, path counting and other uses of repeated squaring. oi-wiki.org (opens in a new tab)