Обратный остаток / деление по модулю – Быстрый гайд

Revision ru2, by rembocoder, 2023-03-10 22:11:59

Я нашёл эти статьи, в них уже это описано:

https://mirror.codeforces.com/blog/entry/72527

https://mirror.codeforces.com/blog/entry/46620

Они обе очень хорошие. но я хотел написать более сжатый пост конкретно про обратный остаток, потому что он требуется во многих задачах, даже не связанных с теорией чисел.

Задача

Есть два целых числа A и B. Предположим, вы знаете, что A делится на B. Но они очень большие, поэтому вы знаете только их остатки по модулю некоторого простого числа M и вы хотели бы узнать остаток их частного. Но (A % M) может не делиться на(B % M), что делать?

Такой вопрос нередок в комбинаторных задачах, например, при подсчёте биномиальных коэффициентов, когда нужно поделить n! на k! и (n - k)!.

Решение

Короткий ответ – вам нужно вычислить B в степени M - 2 по модулю M (с помощью бинарного возведения в степень), а затем умножить A на это.

Примечание: это работает только если B % M – не 0, а M – простое.

#include <bits/stdc++.h>

using namespace std;

#define int int64_t

const int mod = 998244353;

int bin_exp(int a, int b) {
    if (b == 0) {
        return 1;
    }
    if (b % 2) {
        return bin_exp(a, b - 1) * a % mod;
    }
    int res = bin_exp(a, b / 2);
    return res * res % mod;
}

int inv(int a) {
    return bin_exp(a, mod - 2);
}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int a, b;
    cin >> a >> b;
    cout << a * inv(b) % mod << '\n';
}

Доказательство

Это известная формула, опирающаяся на малую теорему Ферма и на тот факт, что каждый ненулевой элемент кольца остатков по простому модулю имеет ровно один обратный элемент по умножению. Если вы хотите узнать больше, вы можете прочитать упомянутые мною статьи.

Tags обратный остаток, теория чисел, модульная арифметика, комбинаторика

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en4 English rembocoder 2023-03-11 20:36:27 709
ru4 Russian rembocoder 2023-03-11 20:35:14 716
ru3 Russian rembocoder 2023-03-11 20:28:48 151
en3 English rembocoder 2023-03-11 20:25:19 142 Tiny change: 'number `M` and you' -> 'number `M`: `A % M` and `B % M` and you'
en2 English rembocoder 2023-03-10 22:12:16 0 (published)
ru2 Russian rembocoder 2023-03-10 22:11:59 34 (опубликовано)
ru1 Russian rembocoder 2023-03-10 22:10:23 2008 Первая редакция перевода на Русский (сохранено в черновиках)
en1 English rembocoder 2023-03-10 22:03:02 1995 Initial revision (saved to drafts)