Modular Arithmetic
Keep arithmetic safe under a modulus by tracking the algebraic rules that still survive after reduction.
Modular Arithmetic
The main note is rendered from the TeX source. Code lives in a separate C++ file so the write-up stays readable.
Overview
Modular arithmetic is not just ``take \(\% M\) often.'' The important part is knowing which algebraic operations still behave well after reduction and which ones need extra conditions.
When to Use It
Use it whenever:
answers are required modulo \(M\),
intermediate values grow too large,
a recurrence, combinatorial count, or matrix product naturally lives in \(\mathbb{Z}/M\mathbb{Z}\).
Core Idea
Addition, subtraction, and multiplication respect reduction: \[ (a+b)\bmod M,\quad (a-b)\bmod M,\quad (ab)\bmod M. \] Division does not exist automatically. Dividing by \(x\) means multiplying by its modular inverse, which only makes sense when the inverse exists.
Key Insight
The algebraic structure matters. If the modulus is prime, every non-zero residue has an inverse. For composite moduli, only numbers coprime to the modulus are invertible.
Worked Problem
Problem.
Count the number of ways to build strings of length \(n\), where the recurrence doubles or triples previous counts, and print the answer modulo \(10^9+7\).
Why modular arithmetic fits.
The recurrence only needs addition and multiplication, both of which are safe modulo \(M\). So the whole DP can stay in reduced form from the start.
Correctness Intuition
Reducing after each safe operation does not change the final residue because reduction is compatible with addition and multiplication. The only time care is needed is when an expression secretly relies on division or ordering.
Complexity Analysis
The arithmetic operations stay \(O(1)\). The benefit is numerical safety, not asymptotic improvement.
Implementation
The code gives a small ModInt template with normalization, addition, subtraction, multiplication, and fast exponentiation.
Common Pitfalls
Using negative residues without re-normalizing into \([0, M-1]\).
Writing
a / b % MODas if ordinary division were valid.Overflowing
a * bbefore the modulus is applied.
Variants / Extensions
Modular inverse and division.
CRT when one modulus is not enough.
NTT-friendly moduli for fast polynomial multiplication.
Practice Problems
DP or combinatorics modulo a prime.
Fast exponentiation and modular recurrence simulation.
Any counting problem whose raw numbers are too large to store directly.
References
Code
Contest-ready reference implementation for the idea explained above.
template <int MOD>
struct ModInt {
int value;
ModInt(long long v = 0) { value = normalize(v); }
static int normalize(long long v) {
v %= MOD;
if (v < 0) v += MOD;
return (int)v;
}
ModInt& operator+=(const ModInt& other) {
value += other.value;
if (value >= MOD) value -= MOD;
return *this;
}
ModInt& operator-=(const ModInt& other) {
value -= other.value;
if (value < 0) value += MOD;
return *this;
}
ModInt& operator*=(const ModInt& other) {
value = (int)((long long)value * other.value % MOD);
return *this;
}
friend ModInt operator+(ModInt a, const ModInt& b) { return a += b; }
friend ModInt operator-(ModInt a, const ModInt& b) { return a -= b; }
friend ModInt operator*(ModInt a, const ModInt& b) { return a *= b; }
static ModInt power(ModInt base, long long exp) {
ModInt result(1);
while (exp > 0) {
if (exp & 1) result *= base;
base *= base;
exp >>= 1;
}
return result;
}
};
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.