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

Revision ru4, by rembocoder, 2023-03-11 20:35:14

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

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

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

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

Задача

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

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

Решение

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

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

Реализация

Если вы не используете #define int int64_t
Если вы используете #define int int64_t

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

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

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)