The modular inverse of an integer (a) under modulus (p) is an integer (x) such that [ a \cdot x \equiv 1 \pmod p. ] When (p) is a prime, Fermat’s little theorem provides a direct way to compute (x).

The theorem states (a^{p-1} \equiv 1 \pmod p), therefore [ a \cdot x \equiv a^{p-1} \pmod p \quad\Rightarrow\quad x \equiv a^{p-2} \pmod p. ] Thus the inverse can be obtained via fast exponentiation.

Exponentiation method

The following C++ function binpow computes (a^{b} \bmod m) using binary exponentiation.

long long binpow(long long base, long long exp, long long mod) {
    long long result = 1;
    base %= mod;
    while (exp > 0) {
        if (exp & 1) result = (result * base) % mod;
        base = (base * base) % mod;
        exp >>= 1;
    }
    return result;
}

// Usage: inverse of n modulo p (p prime)
long long inverse(long long n, long long p) {
    return binpow(n, p - 2, p);
}

For a prime modulus, this is both simple and efficient for a single query.

Linear precomputation

When inverses of many numbers (1,2,\dots,n) are needed modulo a prime (p), a linear (O(n)) method is available. Starting from the relation [ p = \left\lfloor \frac{p}{i} \right\rfloor \cdot i + (p \bmod i), ] and after taking everything modulo (p), we obtain [ i^{-1} \equiv -\left\lfloor \frac{p}{i} \right\rfloor \cdot (p \bmod i)^{-1} \pmod p. ] This yields the recurrence [ \text{inv}[i] = \big(p - \lfloor p/i \rfloor\big) \cdot \text{inv}[p \bmod i] \bmod p. ]

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, p;
    cin >> n >> p;
    vector<long long> inv(n + 1);
    inv[1] = 1;
    cout << inv[1] << "\n";
    for (int i = 2; i <= n; ++i) {
        inv[i] = (p - p / i) * inv[p % i] % p;
        cout << inv[i] << "\n";
    }
    return 0;
}

Application: random stack probability

Problem: Perform (2n) operations. Each operation either pushes a given integer onto a stack or pops from the stack (denoted by -1). After all operations, the popped sequence must be non‑decreasing. Find the probability that the sequence is valid, modulo (998244353).

Solution outline: Maintain a min‑heap (priority queue) to always pop the smallest available element. For a valid sequence we must pop only the current minimum. Use a map (or frequency array) to count occurrences of each element currently in the heap. While processing:

• On push (x): add (x) into the heap, increment its count. If (x) is smaller than the last popped value, the sequence cannot be valid.
• On pop: take the top element (t). Let (c) be its frequency and (s) be the heap size. The numerator accumulates (c), the denominator accumulates (s), both multiplicatively modulo (p). Then remove one occurrence of (t). Finally, compute (\text{ans} = \text{numeraotr} \times \text{denominator}^{-1} \bmod p), using modular inverse via exponentiation.

#include <bits/stdc++.h>
using namespace std;

const long long MOD = 998244353;

long long mod_pow(long long a, long long b) {
    long long res = 1;
    a %= MOD;
    while (b) {
        if (b & 1) res = res * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<int> freq(400005, 0);
    priority_queue<int, vector<int>, greater<int>> pq;
    long long num = 1, den = 1;
    int last = -1;

    for (int i = 0; i < 2 * n; ++i) {
        int x;
        cin >> x;
        if (x != -1) {
            pq.push(x);
            freq[x]++;
            if (x < last) {
                cout << 0 << "\n";
                return 0;
            }
        } else {
            int top = pq.top();
            num = num * freq[top] % MOD;
            den = den * pq.size() % MOD;
            last = top;
            freq[top]--;
            pq.pop();
        }
    }

    long long inv_den = mod_pow(den, MOD - 2);
    long long ans = num * inv_den % MOD;
    cout << ans << "\n";

    return 0;
}

This technique highlights how modular inverses naturally arise in problems involving rational probabilities under a prime modulus.