In-Depth Analysis of Linear Congruences and Extended Chinese Remainder Theorem

Core Logic and Mathematical Principles

Linear Congruences

An equation of the form $a \cdot x \equiv c \pmod b$ is called a linear congruence. This equation is equivalent to the following binary linear indeterminate equation:

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

According to Bézout's identity, a necessary and sufficient condition for the equation to have a solution is $\gcd(a, b) \mid c$. The equation can be solved directly using the Extended Euclidean Algorithm ($EXGCD$).

Chinese Remainder Theorem (CRT)

The Chinese Remainder Theorem is used to solve a system of linear congruences: $$\begin{cases} x \equiv a_1 \pmod{m_1} \ x \equiv a_2 \pmod{m_2} \ \vdots \ x \equiv a_k \pmod{m_k} \end{cases}$$ Conditions for Application: The moduli $m_1, m_2, \dots, m_k$ must be pairwise coprime.

The construction logic is as follows:

Let the total modulus be $M = \prod_{i=1}^k m_i$.
Let $M_i = \frac{M}{m_i}$$, which is the product of all moduli except $m_i$. Clearly, $\gcd(M_i, m_i) = 1$.
Let $t_i = M_i^{-1}$ be the multiplicative inverse of $M_i$ modulo $m_i$, i.e., $M_i \cdot t_i \equiv 1 \pmod{m_i}$.
The general solution structure of the system is:

$$x = \sum_{i=1}^k a_i \cdot M_i \cdot t_i + k \cdot M \quad (k \in \mathbb{Z})$$

Under modulus $M$, the system has a unique minimal non-negative integer solution.

Algorithm Derivation and State Design

Extended Chinese Remainder Theorem (EXCRT)

When the moduli $m_1, m_2, \dots, m_k$ are not pairwise coprime, the traditional CRT construction method fails (the inverse may not exist). We must use the mathematical induction merging method, which involves decomposition and iteration.

Assume that we have found a particular solution $x_0$ for the system of congruences formed by the first $i-1$ equations. Let $M = \text{lcm}(m_1, m_2, \dots, m_{i-1})$. The general solution form for the first $i-1$ equations is:

$$x = x_0 + k \cdot M \quad (k \in \mathbb{Z})$$

Now we introduce the $i$-th equation: $x \equiv a_i \pmod{m_i}$. Substituting this into the general solution form transforms it into the search for an integer $k$ such that:

$$x_0 + k \cdot M \equiv a_i \pmod{m_i}$$

Rearranging gives the standard form of a linear congruence:

$$M \cdot k \equiv a_i - x_0 \pmod{m_i}$$

Expressed as an indeterminate equation:

$$M \cdot k + m_i \cdot y = a_i - x_0$$

We invoke $EXGCD$ to solve this equation. Let $g = \gcd(M, m_i)$.

If $(a_i - x_0) \bmod g \neq 0$, then the entire system has no solution.
If a solution exists, the particular solution $k_0$ is computed using $EXGCD$, and $k$ is adjusted to the smallest non-negative integer using the step size $t = \frac{m_i}{g}$:

$$k = (k_0 \cdot \frac{a_i - x_0}{g} \bmod t + t) \bmod t$$

Update the particular solution $x_0' = x_0 + k \cdot M$. Update the total modulus $M' = \text{lcm}(M, m_i) = M \cdot \frac{m_i}{g}$. This process can be iterated $k-1$ times to merge all equations.

C++ Standard Source Code

#include <iostream>
#include <vector>

// Extended Euclidean Algorithm
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;
}

// Extended Chinese Remainder Theorem (EXCRT)
// Input system of equations: x \equiv a[i] (mod m[i])
// Note: This template has built-in overflow-safe multiplication conversion
long long excrt(const std::vector<long long> &a, const std::vector<long long> &m) {
    int n = a.size();
    long long M = m[0];
    long long x0 = a[0];

    for (int i = 1; i < n; ++i) {
        long long k0, y0;
        // Solve M * k + m[i] * y = a[i] - x0
        long long c = ((a[i] - x0) % m[i] + m[i]) % m[i];
        long long g = exgcd(M, m[i], k0, y0);

        if (c % g != 0) return -1; // No solution due to indivisibility

        long long t = m[i] / g;
        // Use __int128_t to prevent multiplication overflow of long long
        k0 = (long long)((__int128_t)k0 * (c / g) % t);
        k0 = (k0 + t) % t; // Map to the smallest non-negative integer solution

        x0 = x0 + k0 * M;
        M = M / g * m[i]; // New lcm(M, m[i])
        x0 = (x0 % M + M) % M; // Keep the particular solution within the current modulus range
    }
    return x0;
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n;
    if (std::cin >> n) {
        std::vector<long long> a(n), m(n);
        for (int i = 0; i < n; ++i) {
            // Note the input order: some problems read moduli first, then residues
            std::cin >> m[i] >> a[i];
        }
        long long ans = excrt(a, m);
        std::cout << ans << "\n";
    }
    return 0;
}

NOIP Practical Pitfall Guide

Multiplication Overflow Trap in EXCRT Merging Process When calculating k0 * (c / g) and x0 + k0 * M, the variables involved typically reach magnitudes of $10^{12} \sim 10^{18}$. Direct multiplication can cause immediate truncation in long long, leading to negative numbers or erroneous modulus steps. It is essential to enforce conversion to __int128_t for intermediate calculations, or use $O(\log N)$ slow multiplication (binary peasant multiplication).
Elementary Input Order Mistake In the input formats for the $CRT$ template problems and $EXCRT$ template problems on Luogu, the order of moduli $m_i$ and residues $a_i$ is often reversed (one problem reads $m_i$ first and then $a_i$, while another reads $a_i$ first and then $m_i$). Blindly applying templates without reviewing the problem statement can easily lead to confusion in array meanings, causing input data to get stuck in the exgcd function.

Classic NOIP/Luogu Problems

1. Luogu P3868 [TJOI2009] Guess the Number

Problem Description: Given two sets of integers $a_1, a_2, \dots, a_k$ and $b_1, b_2, \dots, b_k$, knowing that $\gcd(b_i, b_j) = 1$. Find the smallest positive integer $n$ such that for all $i$, $(n - a_i) \bmod b_i = 0$ holds.
Core Problem Essence: A variant application of the standard Chinese Remainder Theorem (CRT).
Core Solution Idea: $(n - a_i) \bmod b_i = 0 \implies n \equiv a_i \pmod{b_i}$. Since the problem explicitly states that $b_i$ are pairwise coprime, this fully complies with the traditional CRT usage conditions. Construct the total product $M$, calculate each component, and then accumulate them. Note that $a_i$ may be negative, so it should be converted when read to (a[i] % b[i] + b[i]) % b[i].

2. Luogu P4777 [Template] Extended Chinese Remainder Theorem (EXCRT)

Problem Description: Solve a system of linear congruences where the moduli $m_i$ are not guaranteed to be pairwise coprime. The data scale is $n \le 10^5$, $\prod m_i \le 10^{18}$.
Core Problem Essence: Incremental merging of congruences when moduli are not coprime.
Core Solution Idea: Since the moduli may have common divisors, directly apply the aforementioned inductive iterative method. Each time, merge the new equation into the current particular solution. If $EXGCD$ reveals that the remainder difference cannot be divided by the greatest common divisor, output that there is no solution. Throughout, utilize __int128_t to safeguard multiplication and avoid data overflow.