Deep Dive into Modular Arithmetic and Extended Euclidean Algorithm

Core Logic and Mathematical Principles

Modular arithmetic is the cornerstone of number theory algorithms. In the computer's two's complement architecture, it is essential to ensure that all addition, subtraction, and multiplication operations are performed modulo at each step to prevent integer overflow.

The greatest common divisor (GCD) is fundamentally based on the Euclidean algorithm. Its mathematical foundation is as follows: if $a = q \cdot b + r$, then $\text{gcd}(a, b) = \text{gcd}(b, r)$. Since $r = a \bmod b$, we have $\text{gcd}(a, b) = \text{gcd}(b, a \bmod b)$. When $b = 0$, $\text{gcd}(a, 0) = a$. The worst-case time complexity is $O(\log \min(a, b))$, particularly in cases involving adjacent Fibonacci numbers.

The Extended Euclidean Algorithm (EXGCD) is used to solve Bézout's Identity:

$$a \cdot x + b \cdot y = \text{gcd}(a, b)$$

This equation always has an integer solution $(x, y)$. The logic for solving it involves recursive backtracking: let $b \cdot x' + (a \bmod b) \cdot y' = \text{gcd}(b, a \bmod b) = \text{gcd}(a, b)$. Substituting $a \bmod b = a - \lfloor \frac{a}{b} \rfloor \cdot b$ into the equation yields:

$$a \cdot y' + b \cdot (x' - \lfloor \frac{a}{b} \rfloor \cdot y') = \text{gcd}(a, b)$$

Comparing coefficients gives the current layer's solution:

$$\begin{cases} x = y' \\ y = x' - \lfloor \frac{a}{b} \rfloor \cdot y' \end{cases}$$

Recursing down to the base case $b = 0$, the equation simplifies to $a \cdot x + 0 \cdot y = a$, where the solution is $x = 1, y = 0$. Backtracking yields a particular solution $(x_0, y_0)$ for the original equation.

Algorithm Derivation and State Design

For a more general linear congruence equation (or binary linear indeterminate equation):

$$a \cdot x + b \cdot y = c$$

The necessary and sufficient condition for the existence of a solution is $\text{gcd}(a, b) \mid c$ (i.e., $c$ is a multiple of $\text{gcd}(a, b)$). If this condition is not met, the equation has no solution.

If a solution exists, we first use EXGCD to find a particular solution $(x_0, y_0)$ for $a \cdot x_0 + b \cdot y_0 = \text{gcd}(a, b)$. Then, we multiply both sides of the equation by $\frac{c}{\text{gcd}(a, b)}$ to obtain a particular solution for the original equation:

$$\begin{cases} X_0 = x_0 \cdot \frac{c}{\text{gcd}(a, b)} \\ Y_0 = y_0 \cdot \frac{c}{\text{gcd}(a, b)} \end{cases}$$

The general solution structure for this equation is:

$$\begin{cases} x = X_0 + k \cdot \frac{b}{\text{gcd}(a, b)} \\ y = Y_0 - k \cdot \frac{a}{\text{gcd}(a, b)} \end{cases} \quad (k \in \mathbb{Z})$$

In NOIP competitions, it is often required to output the minimum positive integer solution for $x$. Let $g = \text{gcd}(a, b)$ and step size $t = \frac{b}{g}$. The correction formula for the minimum positive integer solution is:

$$x_{\min} = (X_0 \bmod t + t) \bmod t$$

If we require the corresponding $y$, we can directly substitute into the original equation $y = \frac{c - a \cdot x_{\min}}{b}$ to find its value.

C++ Standard Source Code

#include <iostream>

// Extended Euclidean Algorithm, returns gcd(a, b) and updates x and y by reference
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; // Must perform division before multiplication to prevent changing operation precedence
    return g;
}

// Solve for the minimum positive integer solution x in a * x + b * y = c
bool solve(long long a, long long b, long long c, long long &x, long long &y, long long &g) {
    g = exgcd(a, b, x, y);
    if (c % g != 0) return false; // Bézout's theorem condition check, if not divisible, there is no solution

    long long t = b / g;
    x = x * (c / g); // Obtain particular solution, note the risk of overflow in intermediate results (usually test data will limit the range)
    x = (x % t + t) % t; // Force mapping to the range [0, t-1]
    if (x == 0) x += t;  // If strictly positive integer is required, 0 must be incremented by the step size

    y = (c - a * x) / b; // Calculate corresponding y
    return true;
}

int main() {
    // Optimize standard input and output stream, break synchronization with stdin/stdout to improve IO efficiency
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    long long a, b, c;
    if (std::cin >> a >> b >> c) {
        long long x = 0, y = 0, g = 0;
        if (solve(a, b, c, x, y, g)) {
            std::cout << x << " " << y << "\n";
        } else {
            std::cout << "-1\n";
        }
    }
    return 0;
}

NOIP Practical Pitfall Guide

Negative Trap in Modular Subtraction When handling operations of the form $(a - b) \bmod m$, if $a < b$, the C++ % operator returns a negative result (e.g., -3 % 5 = -3). In number theory problems, this can lead to out-of-bounds indexing or logical errors. It must be written as:
```
long long ans = ((a - b) % m + m) % m;
```
Overflow in exgcd and Intermediate Multiplication Results Exceeding long long When $a, b, c$ approach $10^{18}$ and $\text{gcd}(a, b) = 1$, executing x = x * (c / g) can easily exceed the long long range (causing integer overflow truncation). If necessary, __int128_t should be used as an intermediate variable to handle multiplication, and then modulo back to the target range.

Classic NOIP/Luogu Problems

1. Luogu P1516 Frog Meeting

Problem Description: Two frogs are on a circular track of length $L$. Frog A starts at $x$ and jumps $m$ meters each time; Frog B starts at $y$ and jumps $n$ meters each time. The question is how many jumps (denoted as $t$) it takes for the two frogs to meet.
Core Problem: Set up the displacement congruence equation: $x + m \cdot t \equiv y + n \cdot t \pmod L$.
Core Solution Idea: Rearranging gives $(m - n) \cdot t + L \cdot k = y - x$. Let $a = m - n, b = L, c = y - x$, transforming the equation into the standard form $a \cdot t + b \cdot k = c$. Use exgcd to solve for the minimum positive integer solution for $t$. If $a < 0$, the signs of $a$ and $c$ can be reversed for positive handling.

2. Luogu P1082 Congruence Equation (NOIP 2012 Advanced Group)

Problem Description: Find the minimum positive integer solution for the congruence equation $a \cdot x \equiv 1 \pmod b$. The problem guarantees that $a$ and $b$ are coprime.
Core Problem: Find the multiplicative inverse of $a$ modulo $b$.
Core Solution Idea: Transform the congruence equation into the indeterminate equation $a \cdot x - b \cdot y = 1$. Introducing a negative sign leads to $a \cdot x + b \cdot Y = 1$ (where $Y = -y$). Directly call exgcd(a, b, x, Y), and the obtained $x$ can be corrected using (x % b + b) % b to yield the answer.