fact[] / invfact[] and Legendre's FormulaWatch the factorial table fill forward, the single inverse appear, the inverse-factorial table fill backward, then count the factors of p in n! via Legendre's formula.
| Operation | Time | Space | Note |
|---|---|---|---|
| Build fact[0..N] | O(N) | O(N) | one forward loop |
| Build invfact[0..N] | O(N + log p) | O(N) | one inverse + backward loop |
| C(n, k) after precompute | O(1) | O(1) | three multiplies |
| Single inverse (Fermat) | O(log p) | O(1) | ap-2 mod p |
| Legendre vp(n!) | O(logp n) | O(1) | sum of floor divisions |
fact[0] = 1, each cell is the previous times its index: fact[i] = fact[i-1]·i mod p. One pass, O(N).invfact[N] = fact[N]p-2 mod p by Fermat's little theorem. This is the only modular inverse in the whole precompute, O(log p).invfact[i-1] = invfact[i]·i mod p, valid because (i-1)! = i!/i so ((i-1)!)-1 = (i!)-1·i. One pass, O(N).The third row of the table, fact·invfact, shows the self-check: it must be 1 in every column (this verifies the inverse table).
| Situation | Method | Per query |
|---|---|---|
| m prime, n < m | fact[]/invfact[] tables | O(1) |
| m prime, n ≥ m | Lucas' theorem | O(logm n) |
| m = pe (prime power) | Granville (gen. Wilson) | O(e·logp n) |
| m composite | per prime power + CRT | Σ + O(r) |
This visualization animates the first row (the common large-prime case) plus Legendre's formula, which is the gate that decides when you must leave it for Lucas or Granville.
fact[p-1] = p-1 (Wilson) if you set N = p-1.fact[4] = 24 ≡ 4 ≡ -1 (mod 5) (Wilson's theorem).n! ≡ 0 (mod p) for n ≥ p.| n | p | terms | vp(n!) | meaning |
|---|---|---|---|---|
| 10 | 2 | 5 + 2 + 1 | 8 | 28 divides 10! |
| 100 | 5 | 20 + 4 | 24 | 100! ends in 24 zeros |
| 100 | 3 | 33 + 11 + 3 + 1 | 48 | 348 divides 100! |
| 6 | 7 | (none, p > n) | 0 | 6! is coprime to 7 |
Set Legendre n and p above to reproduce any of these in Phase 3. Whenever the total is 0, n! is invertible mod p (the table method applies); whenever it is ≥ 1, n! ≡ 0 (mod p).
The exponent of p in C(n,k) equals the number of carries when you add k and (n−k) in base p. Example with p = 2:
(p-1)! ≡ -1 mod p) gives a free correctness check: if you build the table to p-1, the last factorial cell must read p-1. Set N = p−1 to see it.invfact[] with one inverse plus a backward pass is O(N + log p), versus O(N log p) if you inverted every factorial separately — roughly a 30× difference at p ≈ 109.fact[i] = fact[i-1]·i; one Fermat inverse gives invfact[N]; the backward loop computes invfact[i-1] = invfact[i]·i (because (i-1)! = i!/i). Legendre's formula counts the factors of p in n!. See junior.md and professional.md for proofs.