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

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

https://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';
}

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

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