Soit \(p\) un nombre premier. Nous notons \(v_p(n)\) la valuation \(p\)-adique de \(n\), et \((n)_p\) le quotient de \(n\) par la plus grande puissance de \(p\) qui le divise. Ainsi, on a \(n = p^{v_p(n)} (n)_p\).
Théorème de Lucas
Le théorème de Lucas permet de calculer un grand coefficient binomial modulo un petit nombre premier. Il évite les problèmes de surcharge mémoire liés au prétraitement des factorielles et garantit l'existence des inverses modulo \(p\).
Énoncé : Pour tout premier \(p\), on a \[ \binom{n}{m} \equiv \binom{\lfloor n/p \rfloor}{\lfloor m/p \rfloor} \binom{n \bmod p}{m \bmod p} \pmod{p}, \] avec la convention que \(\binom{a}{b} = 0\) si \(a < b\).
Pour la preuve, on utilise un lemme : pour un premier \(p\), \((x+y)^p \equiv x^p + y^p \pmod{p}\). Cela découle du développement binomial où les coefficients \(\binom{p}{i}\) pour \(1 \leq i < p\) sont divisibles par \(p\).
En appliquant ce lemme à \((1+x)^n\) avec \(n = qp + r\), on obtient une représentation qui sépare les contributions des puissances de \(p\), conduisant à la formule du théorème.
Interprétation : En exprimant \(n\) et \(m\) en base \(p\), le coefficient binomial se décompose en un produit de coefficients binomiaux par chiffre.
Implémentation récursive : On prétraite les factorielles et leurs inverses modulo \(p\) en \(O(p)\), puis on résout par division en base \(p\).
int binomial_mod_prime(int n, int m, int prime, vector<int>& fact, vector<int>& inv_fact) {
if (n < m) return 0;
return 1LL * fact[n] * inv_fact[m] % prime * inv_fact[n - m] % prime;
}
int lucas(int n, int m, int prime, vector<int>& fact, vector<int>& inv_fact) {
if (m == 0) return 1;
int r_n = n % prime, r_m = m % prime;
if (r_n < r_m) return 0;
int local = binomial_mod_prime(r_n, r_m, prime, fact, inv_fact);
return 1LL * local * lucas(n / prime, m / prime, prime, fact, inv_fact) % prime;
}</int></int></int></int>
Théorème de Wilson
Le théorème de Wilson classique : \((p-1)! \equiv -1 \pmod{p}\) si et seulement si \(p\) est premier. La preuve repose sur l'appariement des inverses modulo \(p\).
Généralisation aux puissences de premiers : Pour un premier \(p\) et un entier \(k \geq 1\), on a \[ (p^k!)_p \equiv \begin{cases} 1 & \text{si } p=2 \text{ et } k \geq 3, \\ -1 & \text{sinon}. \end{cases} \pmod{p^k}. \] Cela s'obtient en étudiant les solutions de \(x^2 \equiv 1 \pmod{p^k}\), qui dépendent de la parité de \(p\).
Algorithme exLucas
L'algorithme exLucas résout le problème : calculer \(\binom{n}{m} \bmod t\) où \(t\) est un entier quelconque, avec \(n, m\) très grands. On décompose \(t\) en facteurs premiers : \(t = \prod_{i=1}^k p_i^{c_i}\). Pour chaque facteur premier puissance, on calcule \(\binom{n}{m} \bmod p_i^{c_i}\), puis on combine les résultats via le théorème des restes chinois (CRT).
Pour un module \(p^k\), on écrit \[ \binom{n}{m} = \frac{n!}{m!(n-m)!} \equiv \frac{(n!)_p}{(m!)_p ((n-m)!)_p} \cdot p^{v_p(n!) - v_p(m!) - v_p((n-m)!)} \pmod{p^k}. \] Si l'exposant de \(p\) est au moins \(k\), le résultat est \(0\). Sinon, on calcule séparément la valuation \(p\)-adique et la partie sans facteur \(p\).
Calcul de \(v_p(n!)\) : On utilise la formule \[ v_p(n!) = \sum_{i=1}^{\lfloor \log_p n \rfloor} \left\lfloor \frac{n}{p^i} \right\rfloor, \] calculable en \(O(\log_p n)\).
int valuation_factorial(long long x, int prime) {
int count = 0;
while (x > 0) {
x /= prime;
count += x;
}
return count;
}
Calcul de \((n!)_p\) : On sépare les facteurs premiers à \(p\) et ceux qui sont multiples de \(p\). Soit \[ f(l, r) = \prod_{\substack{i=l \\ i \perp p}}^r i \pmod{p^k}, \] alors on a une périodicité modulo \(p^k\). On prétraite un tableau pour \(f(1, i)\) avec \(0 \leq i < p^k\). Par récursion, on obtient \[ (n!)_p \equiv f(1, n \bmod p^k) \cdot \left( f(1, p^k) \right)^{\lfloor n/p^k \rfloor} \cdot \left( \lfloor n/p \rfloor ! \right)_p \pmod{p^k}. \]
int compute_part_without_prime(long long x, int prime, int exponent, int modulus) {
int result = 1;
bool sign_factor = (prime > 2 || exponent <= 2);
for (; x > 0; x /= prime) {
if ((x / modulus) % 2 != 0 && sign_factor) {
result = (modulus - result) % modulus;
}
result = 1LL * result * precomputed[x % modulus] % modulus;
}
return result;
}
int combination_mod_prime_power(long long n, long long m, int prime, int exponent) {
int pk = power(prime, exponent);
int val = valuation_factorial(n, prime) - valuation_factorial(m, prime) - valuation_factorial(n - m, prime);
if (val >= exponent) return 0;
// Prétraitement des tableaux pour la partie sans facteur premier
vector<int> precomp(pk, 1);
for (int i = 1; i < pk; ++i) {
precomp[i] = (i % prime != 0) ? 1LL * precomp[i - 1] * i % pk : precomp[i - 1];
}
int part_n = compute_part_without_prime(n, prime, exponent, pk);
int part_m = compute_part_without_prime(m, prime, exponent, pk);
int part_nm = compute_part_without_prime(n - m, prime, exponent, pk);
int inverse_m = modular_inverse(part_m, pk);
int inverse_nm = modular_inverse(part_nm, pk);
int res = 1LL * power(prime, val) * part_n % pk * inverse_m % pk * inverse_nm % pk;
return res;
}</int>
Finalement, pour exLucas, on décompose le module \(t\), on applique la combinaison modulo chaque puissance de premier, et on combine via CRT.
int ex_lucas(long long n, long long m, int modulus) {
vector<pair int="">> factors;
int temp = modulus;
for (int i = 2; i * i <= temp; ++i) {
if (temp % i == 0) {
int cnt = 0;
while (temp % i == 0) {
temp /= i;
++cnt;
}
factors.emplace_back(i, cnt);
}
}
if (temp > 1) {
factors.emplace_back(temp, 1);
}
vector<int> residues, moduli;
for (auto [p, c] : factors) {
int pk = power(p, c);
int val = combination_mod_prime_power(n, m, p, c);
residues.push_back(val);
moduli.push_back(pk);
}
return chinese_remainder_theorem(residues, moduli);
}</int></pair>
L'algorithme a une complexité de prétraitement en \(O(\sqrt{t} + \sum p_i)\) et une complexité par requête en \(O(\log_p n)\) pour chaque facteur premier.