Core Logic and Mathematical Principles
The multiplicative inverse serves as a substitute for division in modular arithmetic. If integers $a$ and $m$ are coprime and satisfy the congruence equation:
$$a \cdot x \equiv 1 \pmod m$$
then $x$ is called the multiplicative inverse of $a$ modulo $m$, denoted as $a^{-1}$. In modular arithmetic, dividing by a number is equivalent to multiplying by its inverse, i.e., $\frac{b}{a} \equiv b \cdot a^{-1} \pmod m$.
There are three core mathematical approaches to finding inverses:
- Fermat's Little Theorem: If $m$ is a prime and $\gcd(a, m) = 1$, then $a^{m-1} \equiv 1 \pmod m$. Dividing both sides by $a$ gives:
$$a \cdot a^{m-2} \equiv 1 \pmod m$$
Thus, $a^{-1} = a^{m-2} \bmod m$. This can be computed in $O(\log m)$ time using the fast exponentiation algorithm.
- Extended Euclidean Algorithm (EXGCD): If $m$ is not prime but guarantees $\gcd(a, m) = 1$, Fermat's Little Theorem fails. In this case, the congruence equation can be transformed into a linear Diophantine equation:
$$a \cdot x + m \cdot y = 1$$
Running $EXGCD$ directly will solve for $x$ with a time complexity of $O(\log \min(a, m))$.
- Linear Recursion for Inverses: When needing to find the inverses of all integers from $1$ to $N$ concerning a prime $p$, if each number is computed separately, the complexity would be $O(N \log p)$, which would timeout for $N \ge 10^6$. Using mathematical recursion, all inverses can be processed offline in $O(N)$ time.
Algorithm Derivation and State Design
Derivation of Linear Inverse Recursion Formula
Let us denote the inverse of $i$ modulo $p$ (where $p$ is prime and $i < p$) as the current value to be computed. Let $k = \lfloor \frac{p}{i} \rfloor$, $r = p \bmod i$. Thus, we have:
$$p = k \cdot i + r$$
In the context of modulo $p$, we have:
$$k \cdot i + r \equiv 0 \pmod p$$
Multiplying both sides by $i^{-1} \cdot r^{-1}$ gives:
$$k \cdot r^{-1} + i^{-1} \equiv 0 \pmod p$$
Rearranging the equation isolates $i^{-1}$ on the left side:
$$i^{-1} \equiv -k \cdot r^{-1} \pmod p$$
Substituting back $k = \lfloor \frac{p}{i} \rfloor$ and $r = p \bmod i$ into the equation gives:
$$i^{-1} \equiv -\lfloor \frac{p}{i} \rfloor \cdot (p \bmod i)^{-1} \pmod p$$
To eliminate the negative sign, we convert it to a positive modulo:
$$i^{-1} \equiv (p - \lfloor \frac{p}{i} \rfloor) \cdot (p \bmod i)^{-1} \pmod p$$
Let $inv[i]$ be the inverse of $i$, then the state transition equation is:
$$inv[i] = (p - p / i) \cdot inv[p \bmod i] \bmod p$$
Since $p \bmod i < i$, its inverse must have already been computed earlier, ensuring no dependency on future states. The base case is $inv[1] = 1$.
C++ Standard Source Code
#include <iostream>
#include <vector>
// 1. Fast exponentiation to find inverses (Fermat's Little Theorem), prerequisites: p is prime and a is coprime to p
long long power(long long base, long long exp, long long mod) {
long long res = 1;
base %= mod;
while (exp > 0) {
if (exp & 1) res = (res * base) % mod;
base = (base * base) % mod;
exp >>= 1;
}
return res;
}
long long get_inv_fermat(long long a, long long p) {
return power(a, p - 2, p);
}
// 2. EXGCD to find inverses, prerequisites: a is coprime to m (m may not be prime)
long long exgcd(long long a, long long b, long long &x, long long &y) {
if (b == 0) {
x = 1; y = 0;
return a;
}
long long x1, y1;
long long g = exgcd(b, a % b, x1, y1);
x = y1;
y = x1 - (a / b) * y1;
return g;
}
long long get_inv_exgcd(long long a, long long m) {
long long x, y;
long long g = exgcd(a, m, x, y);
if (g != 1) return -1; // gcd(a, m) != 1, inverse does not exist
return (x % m + m) % m;
}
// 3. Linear recursion to find inverses from 1 to n, prerequisites: p is prime and n < p
void get_all_inv(int n, long long p, std::vector<long long> &inv) {
inv.resize(n + 1);
inv[1] = 1; // Base case: the inverse of 1 is always 1
for (int i = 2; i <= n; ++i) {
// Prevent overflow in (p - p / i) * inv[p % i], must cast to long long
inv[i] = (p - p / i) * inv[p % i] % p;
}
}
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
int n;
long long p;
if (std::cin >> n >> p) {
std::vector<long long> inv;
get_all_inv(n, p, inv);
for (int i = 1; i <= n; ++i) {
std::cout << inv[i] << "\n";
}
}
return 0;
}NOIP Practical Pitfalls Guide
- Blindly applying Fermat's Little Theorem leading to zero solutions
When the modulus $m$ is not prime (such as common non-prime large moduli), or when $a$ is a multiple of $m$, using
power(a, m - 2, m)can yield incorrect garbage data, even outputting $0$ as the inverse when $a \equiv 0 \pmod m$, thus corrupting all subsequent multiplication logic. It is essential to clarify the nature of the modulus before calling; use $EXGCD$ for non-primes. - Out-of-bounds usage of
p % iin linear recursion When performing linear recursion to find inverses, the loop range must strictly limit to $i < p$. If the input $n \ge p$, then when $i = p$,p % ibecomes $0$, andinv[0]is undefined (or $0$), which will cause all subsequent entries in theinvarray to collapse to $0$.
Classic NOIP/Luogu Problems
1. Luogu P3811 [Template] Multiplicative Inverse
- Problem Description: Given a positive integer $N$ and a prime $P$, find the multiplicative inverses of all integers from $1$ to $N$ modulo $P$. Data constraints: $N \le 3 \times 10^6, P \le 2 \times 10^9$.
- Core Problem Essence: Batch processing of single-point inverses under high time limits.
- Core Solution Idea: If using fast exponentiation or $EXGCD$, the total complexity would be $O(N \log P)$, which would timeout at this data scale. Directly applying the state transition equation
inv[i] = (p - p / i) * inv[p % i] % pwill optimize both space and time complexity to $O(N)$ using one-dimensional linear DP with eitherstd::vectoror preallocated arrays.
2. Luogu P5431 [Template] Multiplicative Inverse 2
- Problem Description: Given $N$ positive integers $a_1, a_2, \dots, a_n$, a prime $P$, and a constant $K$, find $\sum_{i=1}^{n} \frac{K^i}{a_i} \pmod P$. Data constraints: $N \le 5 \times 10^6$.
- Core Problem Essence: Linear time inverse solving for arbitrary input sequences (offline inverses).
- Core Solution Idea: This problem cannot be solved directly via recursion. First, compute the prefix product $s_i = \prod_{j=1}^i a_j$. Then, use fast exponentiation to find the inverse of the total product $sv_n = (s_n)^{-1}$. Utilizing the inverse backtracking property: $sv_{i-1} = sv_i \cdot a_i \pmod P$, all prefix product inverses can be derived in $O(N)$ time. Finally, each individual element's inverse can be directly obtained via $a_i^{-1} = sv_i \cdot s_{i-1} \pmod P$ in $O(1)$ time. The entire algorithm requires only one fast exponentiation, with the rest being linear scans.