Định Lý Thặng Dư Trung Hoa (Chinese Remainder Theorem)

Xin chào anh em, lại là tôi - Jim đây!

Trong thế giới lập trình thi đấu, có những công cụ toán học không chỉ mạnh mẽ mà còn mang trong mình vẻ đẹp của lịch sử và sự tinh tế của tư duy. Định lý Thặng dư Trung Hoa (Chinese Remainder Theorem - CRT) chính là một trong những công cụ như vậy. Nó không chỉ là một định lý khô khan mà còn là một vũ khí lợi hại giúp anh em giải quyết những bài toán phức tạp một cách nhanh chóng.

Trong bài viết này, chúng ta sẽ cùng nhau thực hiện một hành trình chi tiết, từ câu chuyện huyền thoại của một vị tướng quân Trung Hoa, đến việc nắm vững lý thuyết, và cuối cùng là tham khảo đoạn code minh họa để hiểu thêm và chinh phục các kỳ thi. Dù anh em là người mới bắt đầu hay đã có kinh nghiệm, bài viết này sẽ cung cấp một cái nhìn toàn diện và sâu sắc về Định lý Thặng dư Trung Hoa.

1. Khởi Nguồn Từ Binh Pháp Hàn Tín

Để bắt đầu, hãy cùng quay ngược thời gian về Trung Quốc thời Hán-Sở tranh hùng, lắng nghe một giai thoại nổi tiếng về danh tướng Hàn Tín. Tương truyền, sau một trận chiến ác liệt, Hàn Tín cần phải kiểm tra lại số quân lính còn lại. Thay vì cho đếm từng người, một công việc tốn thời gian và dễ sai sót, ông đã dùng một phương pháp cực kỳ thông minh.

• Đầu tiên, ông ra lệnh cho binh lính xếp thành hàng 3. Kết quả là còn dư ra 2 người.
• Sau đó, ông lại cho họ xếp thành hàng 5, thì dư ra 3 người.
• Cuối cùng, khi xếp thành hàng 7, lại dư ra 2 người.

Chỉ với ba thông tin về số dư này, Hàn Tín đã có thể nhanh chóng tính toán ra số quân sĩ của mình. Câu chuyện này không chỉ cho thấy tài trí của một vị tướng mà còn đặt nền móng cho một trong những định lý đẹp nhất của số học sơ cấp.

Khi anh em gặp một bài toán yêu cầu tìm một số nguyên thỏa mãn nhiều điều kiện về số dư khác nhau, hãy nhớ đến hình ảnh những người lính xếp hàng. Khuôn mẫu này sẽ giúp anh em nhận ra ngay lập tức rằng Định lý Thặng dư Trung Hoa có thể là chìa khóa.

---

2. Từ Binh Pháp Đến Đồng Dư Thức

Bây giờ, hãy dịch câu chuyện của Hàn Tín sang ngôn ngữ của toán học. Gọi $x$ là tổng số binh lính mà chúng ta cần tìm. Dựa trên lời kể, chúng ta có một hệ các điều kiện sau:

• Khi xếp hàng 3 thì dư 2, nghĩa là $x$ chia cho 3 dư 2. Ta viết: $x \equiv 2 \pmod{3}$.
• Khi xếp hàng 5 thì dư 3, nghĩa là $x$ chia cho 5 dư 3. Ta viết: $x \equiv 3 \pmod{5}$.
• Khi xếp hàng 7 thì dư 2, nghĩa là $x$ chia cho 7 dư 2. Ta viết: $x \equiv 2 \pmod{7}$.

Đây chính là một hệ phương trình đồng dư tuyến tính. Nhiệm vụ của Định lý Thặng dư Trung Hoa là tìm ra giá trị của $x$ thỏa mãn đồng thời tất cả các phương trình này.

Ôn tập nhanh: Đồng dư thức là gì?

Trước khi đi sâu hơn, tôi và anh em hãy cùng đảm bảo nắm vững khái niệm cơ bản về đồng dư thức. Trong toán học, ký hiệu $a \equiv b \pmod{m}$ (đọc là a đồng dư với b modulo m) có nghĩa là $a$ và $b$ có cùng số dư khi chia cho $m$. Một cách định nghĩa tương đương là hiệu $(a-b)$ chia hết cho $m$.

Ví dụ:

• $17 \equiv 2 \pmod{5}$ vì cả 17 và 2 đều chia 5 dư 2.
• $10 \equiv 4 \pmod{6}$ vì $(10-4) = 6$ chia hết cho 6.
• $23 \equiv -1 \pmod{8}$ vì $(23 - (-1)) = 24$ chia hết cho 8.

---

3. Định Lý & Công Cụ Vạn Năng

3.1. Định lý Thặng dư Trung Hoa

Định lý Thặng dư Trung Hoa (CRT) được phát biểu một cách chính thức như sau: Cho một hệ gồm $k$ phương trình đồng dư tuyến tính:

$$\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}$$

Trong đó, các số modulo $m_1, m_2, \dots, m_k$ là các số nguyên dương đôi một nguyên tố cùng nhau (tức là $gcd(m_i, m_j) = 1$ với mọi $i \neq j$).

Định lý khẳng định rằng hệ phương trình trên luôn có nghiệm, và nghiệm này là duy nhất theo modulo $M$, với $M = m_1 \cdot m_2 \cdot \dots \cdot m_k$. Điều này có nghĩa là, nếu anh em tìm được một nghiệm $x_0$, thì tất cả các nghiệm khác của hệ sẽ có dạng $x_0 + c \cdot M$ với $c$ là một số nguyên bất kỳ.

3.2. Nghịch đảo Modulo & Giải thuật Euclid Mở rộng

Để xây dựng nên nghiệm của hệ CRT, chúng ta cần một công cụ cực kỳ quan trọng: nghịch đảo modulo.

Nghịch đảo modulo $m$ của một số nguyên $a$ là một số nguyên $x$ sao cho $a \cdot x \equiv 1 \pmod{m}$. Ta thường ký hiệu $x$ là $a^{-1}$. Ví dụ, nghịch đảo modulo 7 của 3 là 5, vì $3 \cdot 5 = 15 \equiv 1 \pmod{7}$.

Điều kiện quan trọng là: nghịch đảo modulo $m$ của $a$ chỉ tồn tại khi và chỉ khi $a$ và $m$ là hai số nguyên tố cùng nhau, tức là $gcd(a, m) = 1$.

Để tìm nghịch đảo modulo, phương pháp hiệu quả nhất là Giải thuật Euclid Mở rộng (Extended Euclidean Algorithm - EEA). Nền tảng của EEA là Đồng nhất thức Bézout, phát biểu rằng: với hai số nguyên $a$ và $b$, luôn tồn tại hai số nguyên $x$ và $y$ sao cho $ax + by = gcd(a, b)$.

Khi $gcd(a, m) = 1$, đồng nhất thức trở thành $ax + my = 1$. Nếu ta lấy phương trình này theo modulo $m$, vế $my$ sẽ trở thành 0. Khi đó, ta có:

$$ax \equiv 1 \pmod{m}$$

Rõ ràng, hệ số $x$ mà EEA tìm được chính là nghịch đảo modulo $m$ của $a$. Dưới đây là cài đặt C++ cho thuật toán.

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

// Hàm Euclid mở rộng để tìm x, y sao cho ax + by = gcd(a, b)
long long extendedEuclid(long long a, long long b, long long &x, long long &y)
{
    // Trường hợp cơ sở của đệ quy
    if (a == 0)
    {
        x = 0;
        y = 1;
        return b;
    }
    long long x1, y1;
    // Gọi đệ quy cho các bước tiếp theo của thuật toán Euclid
    long long d = extendedEuclid(b % a, a, x1, y1);
    // Cập nhật x và y dựa trên kết quả từ lời gọi đệ quy
    x = y1 - (b / a) * x1;
    y = x1;
    return d;
}

// Hàm tìm nghịch đảo modulo m của a
long long modInverse(long long a, long long m)
{
    long long x, y;
    long long g = extendedEuclid(a, m, x, y);
    // Nghịch đảo không tồn tại nếu a và m không nguyên tố cùng nhau
    if (g != 1)
        return -1;
    // Đảm bảo kết quả x luôn là số dương trong khoảng [0, m-1]
    return (x % m + m) % m;
}

---

4. Xây Dựng Lời Giải

Phần hấp dẫn nhất của CRT chính là phép chứng minh mang tính xây dựng của nó. Thay vì chỉ nói nghiệm tồn tại, nó chỉ cho chúng ta cách để tìm ra nghiệm đó. Ý tưởng cốt lõi ở đây là chia để trị.

4.1. Các bước xây dựng nghiệm

1. Tính $M$: Tính tích của tất cả các modulo: $M = m_1 \cdot m_2 \cdot \dots \cdot m_k$.
2. Tính $M_i$: Với mỗi phương trình thứ $i$, ta tính $M_i = M / m_i$. Dễ thấy rằng $M_i$ chia hết cho mọi $m_j$ (với $j \neq i$), và $gcd(M_i, m_i) = 1$.
3. Tìm nghịch đảo $y_i$: Vì $gcd(M_i, m_i) = 1$, ta có thể tìm được nghịch đảo modulo của $M_i$ theo $m_i$. Gọi nghịch đảo này là $y_i$. Tức là $M_i \cdot y_i \equiv 1 \pmod{m_i}$. Đây là lúc ta dùng đến hàm modInverse đã viết ở trên.
4. Tổng hợp nghiệm cuối cùng: Nghiệm $x$ của hệ là tổng của tất cả các thành phần $a_i \cdot M_i \cdot y_i$, và để tìm nghiệm nhỏ nhất không âm, ta lấy kết quả theo modulo $M$:

   $$x = \left( \sum_{i=1}^{k} a_i \cdot M_i \cdot y_i \right) \pmod{M}$$

4.2. Áp dụng vào bài toán Hàn Tín

Hãy quay lại bài toán điểm binh để xem các bước trên hoạt động như thế nào.

• Hệ phương trình:
  • $x \equiv 2 \pmod{3}$ ($a_1=2, m_1=3$)
  • $x \equiv 3 \pmod{5}$ ($a_2=3, m_2=5$)
  • $x \equiv 2 \pmod{7}$ ($a_3=2, m_3=7$)
• Bước 1: Tính M: $M = 3 \cdot 5 \cdot 7 = 105$.
• Bước 2: Tính các $M_i$:
  • $M_1 = 105 / 3 = 35$.
  • $M_2 = 105 / 5 = 21$.
  • $M_3 = 105 / 7 = 15$.
• Bước 3: Tìm các nghịch đảo $y_i$:
  • $y_1 = 35^{-1} \pmod{3}$. Vì $35 \equiv 2 \pmod{3}$, ta cần tìm $2^{-1} \pmod{3}$. Dễ thấy $2 \cdot 2 = 4 \equiv 1 \pmod{3}$. Vậy $y_1 = 2$.
  • $y_2 = 21^{-1} \pmod{5}$. Vì $21 \equiv 1 \pmod{5}$, ta có $1^{-1} \pmod{5} = 1$. Vậy $y_2 = 1$.
  • $y_3 = 15^{-1} \pmod{7}$. Vì $15 \equiv 1 \pmod{7}$, ta có $1^{-1} \pmod{7} = 1$. Vậy $y_3 = 1$.
• Bước 4: Tổng hợp nghiệm:
  • $x = (a_1 M_1 y_1 + a_2 M_2 y_2 + a_3 M_3 y_3) \pmod{M}$
  • $x = (2 \cdot 35 \cdot 2 + 3 \cdot 21 \cdot 1 + 2 \cdot 15 \cdot 1) \pmod{105}$
  • $x = (140 + 63 + 30) \pmod{105}$
  • $x = 233 \pmod{105}$
  • $233 = 2 \cdot 105 + 23$, vậy $x \equiv 23 \pmod{105}$.

Nghiệm nhỏ nhất không âm là 23. Đây chính là đáp án của bài toán cổ.

---

5. Vì Sao Lời Giải Là Duy Nhất?

Giả sử có hai nghiệm khác nhau là $x$ và $y$ cùng thỏa mãn hệ phương trình. Khi đó, với mọi $i$ từ 1 đến $k$, ta có: $x \equiv a_i \pmod{m_i}$ và $y \equiv a_i \pmod{m_i}$.

Trừ vế theo vế, ta được $x - y \equiv 0 \pmod{m_i}$. Điều này có nghĩa là hiệu $(x - y)$ chia hết cho mọi $m_i$. Vì tất cả các $m_i$ là đôi một nguyên tố cùng nhau, nên $(x - y)$ cũng phải chia hết cho tích của chúng, tức là $M = m_1 \cdot m_2 \cdot \dots \cdot m_k$.

Do đó, $x - y \equiv 0 \pmod{M}$, hay $x \equiv y \pmod{M}$. Điều này chứng tỏ rằng mọi nghiệm của hệ đều đồng dư với nhau theo modulo $M$. Nói cách khác, trong khoảng từ 0 đến $M-1$, chỉ có một nghiệm duy nhất.

---

6. Vũ Khí Lập Trình Thi Đấu

Lý thuyết là nền tảng, nhưng trong lập trình thi đấu, một đoạn code chạy đúng và hiệu quả mới là mục tiêu cuối cùng.

6.1. Cạm bẫy cần tránh: Tràn số

Một trong những lỗi phổ biến nhất khi cài đặt CRT là tràn số. Hãy nhìn lại công thức tính nghiệm:

$$x = \left( \sum_{i=1}^{k} a_i \cdot M_i \cdot y_i \right) \pmod{M}$$

Tích $M$ có thể rất lớn, và các tích trung gian như $a_i \cdot M_i \cdot y_i$ có thể dễ dàng vượt qua giới hạn của kiểu long long trong C++ (khoảng $9 \cdot 10^{18}$). Để giải quyết, anh em có thể sử dụng kiểu dữ liệu lớn hơn như __int128_t được hỗ trợ bởi các trình biên dịch GCC và Clang.

6.2. Code minh họa

Dưới đây là đoạn code C++ hoàn chỉnh để giải hệ phương trình đồng dư bằng CRT, có xử lý vấn đề tràn số bằng __int128_t.

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

// Sử dụng __int128_t cho các phép tính trung gian để tránh tràn số.
using int128 = __int128_t;

// Hàm Euclid mở rộng
long long extendedEuclid(long long a, long long b, long long &x, long long &y)
{
    if (a == 0)
    {
        x = 0;
        y = 1;
        return b;
    }
    long long x1, y1;
    long long d = extendedEuclid(b % a, a, x1, y1);
    x = y1 - (b / a) * x1;
    y = x1;
    return d;
}

// Hàm tìm nghịch đảo modulo
long long modInverse(long long a, long long m)
{
    long long x, y;
    long long g = extendedEuclid(a, m, x, y);
    if (g != 1)
        return -1; // Nghịch đảo không tồn tại
    return (x % m + m) % m;
}

// Hàm giải hệ phương trình đồng dư bằng CRT
long long solveCrt(const vector<long long>& a, const vector<long long>& m)
{
    long long totalMod = 1;
    
    for (long long mi : m)
        totalMod *= mi;

    long long result = 0;
    for (size_t i = 0; i < a.size(); ++i)
    {
        long long miProduct = totalMod / m[i];
        long long inverseY = modInverse(miProduct, m[i]);
        
        // Sử dụng int128 để nhân các số lớn, sau đó mới lấy modulo
        int128 term = (int128)a[i] * miProduct * inverseY;
        result = (result + term) % totalMod;
    }

    // Đảm bảo kết quả cuối cùng không âm
    return (result % totalMod + totalMod) % totalMod;
}

int main()
{
    // Ví dụ: Bài toán Hàn Tín điểm binh
    vector<long long> a = {2, 3, 2};
    vector<long long> m = {3, 5, 7};
    
    long long solution = solveCrt(a, m);
    cout << "Nghiem nho nhat khong am la: " << solution << '\n'; // Output: 23

    // Ví dụ khác
    vector<long long> a2 = {1, 2, 3};
    vector<long long> m2 = {11, 13, 17};
    cout << "Nghiem cho vi du 2 la: " << solveCrt(a2, m2) << '\n';
    
    return 0;
}

---

7. Ứng Dụng Thực Chiến

Nhận biết được khi nào cần áp dụng CRT là một kỹ năng quan trọng. Dưới đây là một số dạng bài toán phổ biến.

• Dạng bài cơ bản: Yêu cầu tìm số $x$ thỏa mãn một hệ các phương trình đồng dư, với các modulo đôi một nguyên tố cùng nhau. Đây là ứng dụng trực tiếp của hàm solveCrt.
• Mở rộng: Khi các Modulo không nguyên tố cùng nhau: Nhiều bài toán khó hơn sẽ cho các modulo không nguyên tố cùng nhau. Cách tiếp cận hiệu quả là giải hệ bằng cách gộp dần từng cặp phương trình lại với nhau.
• Bài toán kinh điển: Tính nCr mod M với M là hợp số: Đây là một trong những ứng dụng mạnh mẽ nhất của CRT. Chiến lược là "Phân tích -> Giải -> Kết hợp".
  1. Phân tích: Phân tích $M$ ra thừa số nguyên tố: $M = p_1^{e_1} \cdot p_2^{e_2} \cdot \dots \cdot p_r^{e_r}$.
  2. Giải: Với mỗi thừa số $p_i^{e_i}$, tính $ans_i = \binom{n}{k} \pmod{p_i^{e_i}}$. Đây là một bài toán con dễ hơn.
  3. Kết hợp: Sau khi có các $ans_i$, ta có một hệ phương trình mới: $x \equiv ans_i \pmod{p_i^{e_i}}$. Vì các modulo $p_i^{e_i}$ là đôi một nguyên tố cùng nhau, ta dùng CRT để tìm ra nghiệm cuối cùng.

• Bài tập luyện tập:
  • Cơ bản (Co-prime moduli):
    • KATTIS - Chinese Remainder
    • LIGHTOJ - Monkey Tradition
  • Mở rộng (Non-coprime moduli):
    • KATTIS - Chinese Remainder Theorem (non-relatively prime moduli)
    • CODEFORCES - Remainders Game
    • CODEFORCES - Two chandeliers
  • Kết hợp với các kỹ thuật khác:
    • SPOJ - Product of factorials
    • SPOJ - The Ultimate Riddle
    • Hackerrank - Cheese and Random Toppings

---

8. Tổng Kết

Qua bài viết này, chúng ta đã khám phá Định lý Thặng dư Trung Hoa từ nhiều góc độ. CRT là hiện thân của tư duy "chia để trị" trong số học, cho phép chúng ta giải quyết một bài toán lớn bằng cách chia nó thành các bài toán nhỏ hơn rồi kết hợp lại.

Một điều thú vị là sự tương đồng đáng kinh ngạc giữa CRT và Đa thức Nội suy Lagrange. Điều kiện $x \equiv a_i \pmod{m_i}$ trong CRT tương tự về cấu trúc với điều kiện $P(x) \equiv y_i \pmod{(x-x_i)}$ trong nội suy Lagrange, cho thấy sự thống nhất sâu sắc của toán học.

Cách tốt nhất để làm chủ một kỹ năng là thực hành. Anh em có thể thử sức với một số bài toán luyện tập ở mục 7 để nắm chắc hơn về CRT.

Hy vọng bài viết này đã cung cấp cho anh em một cái nhìn chi tiết, dễ hiểu và đầy đủ về Định lý Thặng dư Trung Hoa. Chúc anh em có những giờ phút lập trình vui vẻ và chinh phục được nhiều bài toán thú vị. Hẹn gặp lại anh em ở các bài viết tiếp theo, see ya~