Как делить по модулю простого числа через обратный элемент (a / b mod p)?
В формуле для числа сочетаний C(n,k) = n! / (k!·(n-k)!) по модулю 10^9+7 нужно делить. Но (a / b) % p напрямую же неверно! Как корректно посчитать «деление» по простому модулю?
2 ответа
Деление по модулю — это умножение на обратный элемент. По определению a / b означает a · b^{-1}, где b^{-1} — такое число, что b · b^{-1} ≡ 1 (mod p). Обычное целочисленное деление (a/b)%p неверно, потому что оно теряет дробную часть и не согласовано с модульной арифметикой.
Для простого p обратный считается через малую теорему Ферма: b^{-1} = b^{p-2} mod p.
long long divmod(long long a, long long b, long long p) {
return a % p * binpow(b, p - 2, p) % p; // a · b^{-1} mod p
}
Сложность одного деления — O(log p) (за счёт возведения в степень). Условие: b не должно делиться на p (иначе обратного нет). Для биномиальных коэффициентов предподсчитай факториалы и обратные факториалы:
long long C(int n, int k) {
if (k < 0 || k > n) return 0;
return fact[n] * inv_fact[k] % MOD * inv_fact[n-k] % MOD;
}
где inv_fact[n] = binpow(fact[n], MOD-2, MOD). Тогда каждое C(n,k) — O(1) после O(n) предподсчёта.
Маленький, но частый баг: люди считают inv_fact[i] для каждого i отдельным возведением в степень — это O(n log p). Лучше посчитать inv_fact[n] один раз через Ферма, а остальные получить рекуррентой назад: inv_fact[i-1] = inv_fact[i] * i % MOD. Тогда весь предподсчёт факториалов и их обратных — O(n + log p).