Обратный элемент по модулю: малая теорема Ферма или расширенный Евклид — что когда брать?
Понял, что делить по модулю напрямую нельзя, нужен обратный элемент: a^{-1} mod m такой, что a · a^{-1} ≡ 1. Вижу два способа — через малую теорему Ферма (a^{m-2}) и через расширенный алгоритм Евклида. В чём разница, когда какой работает и какая асимптотика?
2 ответа
Оба способа дают a^{-1} mod m за O(log m), но условия применимости разные.
Малая теорема Ферма работает только когда m простое (и a не кратно m). Тогда a^{m-1} ≡ 1, значит a^{-1} ≡ a^{m-2}:
long long inv_fermat(long long a, long long m) { // m простое
return binpow(a, m - 2, m); // O(log m)
}
Это самый частый случай на олимпиадах, потому что модуль обычно 10^9+7 (простой). Просто и без подводных камней.
Расширенный Евклид работает для любого m, лишь бы gcd(a, m) = 1. Он ищет x, y такие, что a·x + m·y = 1, откуда a·x ≡ 1 (mod m), то есть x — искомый обратный:
long long ext_gcd(long long a, long long b, long long &x, long long &y) {
if (b == 0) { x = 1; y = 0; return a; }
long long x1, y1;
long long g = ext_gcd(b, a % b, x1, y1);
x = y1;
y = x1 - (a / b) * y1;
return g;
}
long long inv_euclid(long long a, long long m) {
long long x, y;
long long g = ext_gcd(a, m, x, y);
if (g != 1) return -1; // обратного нет
return (x % m + m) % m; // нормализуем в [0, m)
}
Итог: модуль простой → Ферма (короче). Модуль составной, но gcd(a,m)=1 → расширенный Евклид. Если gcd(a,m) ≠ 1 — обратного не существует вообще.
Важный частный случай — нужно поделить на много разных чисел 1..n по простому модулю (например, для формулы биномиальных коэффициентов). Тогда не считай Ферма по отдельности для каждого (O(n log m)), а посчитай все обратные за O(n) рекуррентой:
inv[1] = 1;
for (int i = 2; i <= n; i++)
inv[i] = (MOD - (MOD / i) * inv[MOD % i] % MOD) % MOD;
Это стандартный приём предподсчёта inv[i] для всех i от 1 до n за O(n). Работает для простого модуля MOD > n.