Khóa học CTDL và GT

Bài 2.2: Lý thuyết đồng dư và phương trình đồng dư tuyến tính

Chào mừng các bạn quay trở lại với chuỗi bài blog về Cấu trúc dữ liệu và Giải thuật! Sau khi khám phá những khái niệm cơ bản, hôm nay chúng ta sẽ lặn sâu vào một lĩnh vực toán học đầy quyền năng và có ứng dụng rộng rãi trong khoa học máy tính, đặc biệt là mật mã học và các bài toán liên quan đến số học: Lý thuyết đồng dư và Phương trình đồng dư tuyến tính.

Đừng lo lắng nếu bạn cảm thấy những thuật ngữ này nghe có vẻ xa lạ. Chúng ta sẽ bắt đầu từ những nền tảng cơ bản nhất và cùng nhau xây dựng kiến thức một cách vững chắc.

1. Lý thuyết Đồng dư (Modular Arithmetic) - Phép Toán Trên "Đồng Hồ"

Hãy tưởng tượng một chiếc đồng hồ 12 giờ. Khi kim giờ chỉ đến 12, nó lại quay về 1, 2,... Thời gian 13 giờ thực chất là 1 giờ chiều, 25 giờ là 1 giờ sáng ngày hôm sau. Đây chính là ý tưởng cốt lõi của đồng dư: chúng ta chỉ quan tâm đến phần dư khi chia cho một số nhất định.

1.1. Định nghĩa Quan hệ Đồng dư

Hai số nguyên a và b được gọi là đồng dư (congruent) theo modulo m (với m là một số nguyên dương) nếu a và b có cùng phần dư khi chia cho m. Ký hiệu là:

$a \equiv b \pmod{m}$

Điều này tương đương với việc m chia hết cho hiệu a - b, hay a - b = k * m với k là một số nguyên nào đó. Nói cách khác, $m | (a - b)$.

Ví dụ:

• $13 \equiv 1 \pmod{12}$ vì 13 chia 12 dư 1, và 1 chia 12 cũng dư 1.
• $25 \equiv 1 \pmod{12}$ vì 25 chia 12 dư 1.
• $10 \equiv 4 \pmod{3}$ vì 10 chia 3 dư 1, và 4 chia 3 cũng dư 1. Hoặc $10 - 4 = 6$, và 3 chia hết cho 6.
• $ -5 \equiv 7 \pmod{12}$ vì $-5 = -1 \times 12 + 7$. $-5$ và $7$ cùng dư $7$ khi chia cho $12$.
• $17 \not\equiv 5 \pmod{10}$ vì 17 chia 10 dư 7, còn 5 chia 10 dư 5.

Trong lập trình, phép toán % (modulo) thường trả về phần dư. Tuy nhiên, cần lưu ý cách xử lý số âm giữa các ngôn ngữ. Trong C++, a % m có thể âm nếu a âm. Để đảm bảo phần dư luôn không âm và nằm trong khoảng $[0, m-1]$, ta thường dùng công thức (a % m + m) % m.

1.2. Các Tính chất cơ bản của Đồng dư

Quan hệ đồng dư có nhiều tính chất giống như quan hệ bằng nhau:

• Tính phản xạ: $a \equiv a \pmod{m}$
• Tính đối xứng: Nếu $a \equiv b \pmod{m}$ thì $b \equiv a \pmod{m}$.
• Tính bắc cầu: Nếu $a \equiv b \pmod{m}$ và $b \equiv c \pmod{m}$ thì $a \equiv c \pmod{m}$.

1.3. Các phép toán trên Đồng dư

Điều tuyệt vời là chúng ta có thể thực hiện các phép cộng, trừ, nhân trên các số đồng dư. Nếu $a \equiv b \pmod{m}$ và $c \equiv d \pmod{m}$, thì:

• Cộng: $a + c \equiv b + d \pmod{m}$
• Trừ: $a - c \equiv b - d \pmod{m}$
• Nhân: $a \cdot c \equiv b \cdot d \pmod{m}$

Ví dụ minh họa các phép toán:

Giả sử ta làm việc với modulo 5. Ta có $11 \equiv 1 \pmod{5}$ và $8 \equiv 3 \pmod{5}$.

• Cộng: $11 + 8 = 19$. $19 \equiv 4 \pmod{5}$. Theo tính chất: $1 + 3 = 4$. $4 \equiv 4 \pmod{5}$. Kết quả khớp!
• Trừ: $11 - 8 = 3$. $3 \equiv 3 \pmod{5}$. Theo tính chất: $1 - 3 = -2$. $-2 \equiv 3 \pmod{5}$ (vì $-2 = -1 \times 5 + 3$). Kết quả khớp!
• Nhân: $11 \cdot 8 = 88$. $88 = 17 \times 5 + 3$, nên $88 \equiv 3 \pmod{5}$. Theo tính chất: $1 \cdot 3 = 3$. $3 \equiv 3 \pmod{5}$. Kết quả khớp!

Lưu ý về phép chia: Phép chia trong đồng dư phức tạp hơn. Chúng ta không thể nói chung rằng nếu $ac \equiv bc \pmod{m}$ thì $a \equiv b \pmod{m}$. Ví dụ: $2 \cdot 3 \equiv 6 \pmod{4}$ và $4 \cdot 3 \equiv 12 \equiv 0 \pmod{4}$. Rõ ràng $6 \equiv 0 \pmod{4}$. Ta có $2 \cdot 3 \equiv 4 \cdot 3 \pmod{4}$. Nhưng $2 \not\equiv 4 \pmod{4}$.

Để "chia" trong đồng dư, ta cần đến khái niệm nghịch đảo đồng dư.

1.4. Nghịch đảo Đồng dư (Modular Inverse)

Nghịch đảo đồng dư của số nguyên a theo modulo m (nếu tồn tại) là một số nguyên x sao cho:

$a \cdot x \equiv 1 \pmod{m}$

Nghịch đảo đồng dư của a modulo m tồn tại khi và chỉ khi ước chung lớn nhất của a và m là 1, tức là $\gcd(a, m) = 1$. Khi đó, a và m là nguyên tố cùng nhau.

Nếu $\gcd(a, m) = 1$, thì nghịch đảo đồng dư của a modulo m là duy nhất trong khoảng $[0, m-1]$.

Tại sao lại cần nghịch đảo đồng dư? Nó giống như phép chia. Nếu ta muốn giải phương trình $ax \equiv b \pmod{m}$ và $\gcd(a, m) = 1$, ta có thể nhân cả hai vế với nghịch đảo đồng dư $a^{-1}$ của a modulo m: $a^{-1} \cdot (ax) \equiv a^{-1} \cdot b \pmod{m}$ $(a^{-1} a) x \equiv a^{-1} b \pmod{m}$ $1 \cdot x \equiv a^{-1} b \pmod{m}$ $x \equiv a^{-1} b \pmod{m}$

Làm thế nào để tìm nghịch đảo đồng dư? Phương pháp phổ biến và hiệu quả nhất để tìm nghịch đảo đồng dư khi $\gcd(a, m) = 1$ là sử dụng Giải thuật Euclid mở rộng (Extended Euclidean Algorithm).

Chúng ta sẽ thảo luận chi tiết về giải thuật này và cách áp dụng nó để tìm nghịch đảo đồng dư ở phần sau.

2. Phương trình Đồng dư Tuyến tính (Linear Congruences)

Một phương trình đồng dư tuyến tính có dạng:

$ax \equiv b \pmod{m}$

Trong đó a, b, m là các số nguyên đã biết ($m > 0$), và x là ẩn số cần tìm. Mục tiêu là tìm tất cả các giá trị nguyên của x thỏa mãn phương trình này.

2.1. Điều kiện có nghiệm

Một phương trình đồng dư tuyến tính $ax \equiv b \pmod{m}$ có nghiệm khi và chỉ khi ước chung lớn nhất của a và m chia hết cho b. Tức là, nếu $d = \gcd(a, m)$, thì phương trình có nghiệm nếu và chỉ nếu $b$ chia hết cho $d$ ($d | b$).

2.2. Số lượng nghiệm

• Nếu $d = \gcd(a, m)$ và $d$ không chia hết cho $b$, phương trình không có nghiệm.
• Nếu $d = \gcd(a, m)$ và $d$ chia hết cho $b$, phương trình có đúng d nghiệm không đồng dư theo modulo $m$.

Ví dụ:

• $2x \equiv 3 \pmod{4}$: $\gcd(2, 4) = 2$. 2 không chia hết cho 3. Phương trình vô nghiệm.
• $2x \equiv 2 \pmod{4}$: $\gcd(2, 4) = 2$. 2 chia hết cho 2. Phương trình có $\gcd(2, 4) = 2$ nghiệm modulo 4. Các nghiệm là $x=1$ ($2 \cdot 1 = 2 \equiv 2 \pmod{4}$) và $x=3$ ($2 \cdot 3 = 6 \equiv 2 \pmod{4}$).
• $3x \equiv 5 \pmod{7}$: $\gcd(3, 7) = 1$. 1 chia hết cho 5. Phương trình có $\gcd(3, 7) = 1$ nghiệm modulo 7. Ta sẽ tìm nghiệm này sau.

2.3. Cách giải Phương trình Đồng dư Tuyến tính

Cách giải phụ thuộc vào giá trị của $d = \gcd(a, m)$.

• Trường hợp 1: $\gcd(a, m) = 1$ Trong trường hợp này, a có nghịch đảo đồng dư $a^{-1}$ modulo m. Nhân cả hai vế của $ax \equiv b \pmod{m}$ với $a^{-1}$: $a^{-1}(ax) \equiv a^{-1}b \pmod{m}$ $x \equiv a^{-1}b \pmod{m}$ Nghiệm duy nhất modulo m là $x \equiv (a^{-1} \cdot b) \pmod{m}$. Để tìm $a^{-1}$, ta dùng Giải thuật Euclid mở rộng.

• Trường hợp 2: $\gcd(a, m) = d > 1$ và $d | b$ Vì $d | a$ và $d | m$, ta có thể chia cả ba số $a, b, m$ cho $d$. Đặt $a' = a/d$, $b' = b/d$, $m' = m/d$. Phương trình $ax \equiv b \pmod{m}$ tương đương với $ax = b + km$ cho một số nguyên $k$. Chia cả hai vế cho $d$: $(a/d)x = (b/d) + k(m/d)$, tức là $a'x = b' + km'$. Điều này tương đương với phương trình đồng dư mới: $a'x \equiv b' \pmod{m'}$. Quan trọng: $\gcd(a', m') = \gcd(a/d, m/d) = \gcd(a, m) / d = d/d = 1$. Phương trình mới $a'x \equiv b' \pmod{m'}$ thuộc Trường hợp 1, có nghiệm duy nhất modulo $m'$. Gọi nghiệm đó là $x_0'$. Ta tìm $x_0'$ bằng cách nhân $b'$ với nghịch đảo đồng dư của $a'$ modulo $m'$: $x_0' \equiv (a')^{-1} b' \pmod{m'}$. Các nghiệm của phương trình ban đầu $ax \equiv b \pmod{m}$ là các số có dạng $x_0' + k \cdot m'$, với $k$ là số nguyên. Khi xét theo modulo m, chúng ta có $d$ nghiệm không đồng dư: $x \equiv x_0' \pmod{m'}$ $x \equiv x_0' + m' \pmod{m}$ $x \equiv x_0' + 2m' \pmod{m}$ ... $x \equiv x_0' + (d-1)m' \pmod{m}$ Nghĩa là, các nghiệm là $x_0', x_0' + m/d, x_0' + 2(m/d), \dots, x_0' + (d-1)(m/d)$ modulo $m$.

• Trường hợp 3: $\gcd(a, m) = d > 1$ và $d \nmid b$ Như đã nói, phương trình vô nghiệm.

Để thực hiện các bước giải này, đặc biệt là trong Trường hợp 1 và 2, chúng ta cần một công cụ mạnh mẽ: Giải thuật Euclid mở rộng.

3. Giải thuật Euclid mở rộng (Extended Euclidean Algorithm)

Giải thuật Euclid chuẩn được dùng để tìm ước chung lớn nhất $\gcd(a, b)$ của hai số nguyên a và b. Giải thuật Euclid mở rộng không chỉ tìm $\gcd(a, b)$ mà còn tìm được hai số nguyên x và y thỏa mãn Đồng nhất thức Bézout:

$ax + by = \gcd(a, b)$

Đồng nhất thức này là chìa khóa để tìm nghịch đảo đồng dư. Nếu ta muốn tìm nghịch đảo của a modulo m, ta cần tìm x sao cho $ax \equiv 1 \pmod{m}$. Điều này tương đương với $ax = 1 + ky$ cho một số nguyên $k$, hay $ax - ky = 1$. Nếu $\gcd(a, m) = 1$, Giải thuật Euclid mở rộng có thể tìm được x và y sao cho $ax + my = 1$. Khi đó, $ax \equiv 1 \pmod{m}$, và x chính là nghịch đảo đồng dư của a modulo m. (Lưu ý: x có thể âm, ta cần điều chỉnh nó về khoảng $[0, m-1]$ bằng cách lấy (x % m + m) % m).

3.1. Hoạt động của Giải thuật Euclid mở rộng

Giải thuật này thường được biểu diễn dưới dạng đệ quy hoặc lặp. Ý tưởng chính dựa trên quan sát: $\gcd(a, b) = \gcd(b, a \pmod b)$

Và từ đó, ta có thể xây dựng lại các hệ số x và y từ các bước đệ quy/lặp.

Nếu $ax + by = \gcd(a, b)$, và ở bước tiếp theo ta xét $b \cdot x_1 + (a \pmod b) \cdot y_1 = \gcd(b, a \pmod b)$, ta cần liên hệ $(x_1, y_1)$ với $(x, y)$. Ta có $a \pmod b = a - \lfloor a/b \rfloor \cdot b$. Thay vào phương trình thứ hai: $b \cdot x_1 + (a - \lfloor a/b \rfloor \cdot b) \cdot y_1 = \gcd(a, b)$ $b \cdot x_1 + a \cdot y_1 - \lfloor a/b \rfloor \cdot b \cdot y_1 = \gcd(a, b)$ $a \cdot y_1 + b \cdot (x_1 - \lfloor a/b \rfloor \cdot y_1) = \gcd(a, b)$

So sánh với $ax + by = \gcd(a, b)$, ta thấy: $x = y_1$ $y = x_1 - \lfloor a/b \rfloor \cdot y_1$

Base case của đệ quy là khi $b=0$. Khi đó, $\gcd(a, 0) = a$. Phương trình Bézout trở thành $a \cdot 1 + 0 \cdot y = a$. Vậy khi $b=0$, ta có $\gcd=a$, $x=1$, $y=0$.

3.2. C++ Code cho Giải thuật Euclid mở rộng

#include <iostream>
#include <vector>
#include <numeric> // for std::gcd in C++17, or implement manually

// Hàm tính gcd (dùng cho C++14 trở xuống hoặc để tự luyện)
long long manual_gcd(long long a, long long b) {
    while (b) {
        a %= b;
        std::swap(a, b);
    }
    return a;
}

// Cấu trúc để trả về kết quả từ Extended Euclidean Algorithm
struct ExtendedGcdResult {
    long long gcd;
    long long x;
    long long y;
};

// Hàm triển khai Extended Euclidean Algorithm (đệ quy)
ExtendedGcdResult extendedEuclidean(long long a, long long b) {
    // Base case: khi b = 0
    if (b == 0) {
        return {a, 1, 0};
    }

    // Bước đệ quy: gọi cho (b, a % b)
    ExtendedGcdResult recursiveResult = extendedEuclidean(b, a % b);

    // Tính x và y cho bước hiện tại từ kết quả đệ quy
    long long gcd = recursiveResult.gcd;
    long long x1 = recursiveResult.x;
    long long y1 = recursiveResult.y;

    // Sử dụng công thức x = y1, y = x1 - (a/b) * y1
    long long x = y1;
    long long y = x1 - (a / b) * y1; // Integer division automatically floors

    return {gcd, x, y};
}

// Hàm tìm nghịch đảo đồng dư
// Trả về nghịch đảo của 'a' modulo 'm'
// Trả về -1 nếu nghịch đảo không tồn tại (khi gcd(a, m) != 1)
long long modularInverse(long long a, long long m) {
    ExtendedGcdResult result = extendedEuclidean(a, m);
    long long gcd = result.gcd;
    long long x = result.x;

    // Kiểm tra nếu nghịch đảo tồn tại (gcd phải bằng 1)
    if (gcd != 1) {
        return -1; // Nghịch đảo không tồn tại
    }

    // Đảm bảo kết quả x nằm trong khoảng [0, m-1]
    // (x % m + m) % m xử lý trường hợp x âm
    return (x % m + m) % m;
}

/*
int main() {
    // Ví dụ về Extended Euclidean Algorithm
    long long a = 48, b = 18;
    ExtendedGcdResult result = extendedEuclidean(a, b);
    std::cout << "Extended Euclidean Algorithm for " << a << " and " << b << ":\n";
    std::cout << "gcd(" << a << ", " << b << ") = " << result.gcd << std::endl;
    std::cout << "Such that " << a << "*" << result.x << " + " << b << "*" << result.y << " = " << result.gcd << std::endl;
    std::cout << "Check: " << a * result.x + b * result.y << std::endl; // Verify the identity

    std::cout << "\n--------------------\n";

    // Ví dụ về Modular Inverse
    long long base = 3, mod = 7; // gcd(3, 7) = 1
    long long inv = modularInverse(base, mod);
    std::cout << "Modular inverse of " << base << " modulo " << mod << ":\n";
    if (inv != -1) {
        std::cout << "Inverse is " << inv << std::endl; // Expected: 5
        std::cout << "Check: (" << base << "*" << inv << ") % " << mod << " = " << (base * inv) % mod << std::endl; // Expected: 1
    } else {
        std::cout << "Inverse does not exist." << std::endl;
    }

    std::cout << "\n--------------------\n";

    base = 2, mod = 4; // gcd(2, 4) = 2 != 1
    inv = modularInverse(base, mod);
    std::cout << "Modular inverse of " << base << " modulo " << mod << ":\n";
    if (inv != -1) {
        std::cout << "Inverse is " << inv << std::endl;
    } else {
        std::cout << "Inverse does not exist." << std::endl; // Expected: Inverse does not exist.
    }


    return 0;
}
*/

Giải thích Code:

1. manual_gcd(long long a, long long b): Đây là hàm tính $\gcd$ thủ công, hữu ích nếu bạn không dùng C++17 trở lên (có std::gcd). Nó sử dụng thuật toán Euclid chuẩn.
2. ExtendedGcdResult struct: Một cấu trúc đơn giản để gói gọn ba giá trị trả về từ thuật toán Euclid mở rộng: $\gcd(a, b)$, và hai hệ số $x, y$ trong đồng nhất thức Bézout $ax + by = \gcd(a, b)$.
3. extendedEuclidean(long long a, long long b):
   • Đây là hàm triển khai đệ quy của Giải thuật Euclid mở rộng.
   • Base Case: Khi b bằng 0, $\gcd(a, 0) = a$. Theo đồng nhất thức $ax + by = \gcd(a, b)$, ta có $a \cdot 1 + 0 \cdot 0 = a$. Do đó, khi b == 0, ta trả về {a, 1, 0}.
   • Bước đệ quy: Gọi hàm đệ quy với cặp số $(b, a \% b)$. Giả sử kết quả trả về là {gcd, x1, y1}, thỏa mãn $b \cdot x1 + (a \% b) \cdot y1 = \gcd(b, a \% b) = \gcd(a, b)$.
   • Kết hợp kết quả: Sử dụng công thức suy luận từ đồng nhất thức Bézout ở bước đệ quy:
     • Hệ số x cho cặp $(a, b)$ là y1 (hệ số của b trong bước đệ quy).
     • Hệ số y cho cặp $(a, b)$ là x1 - (a / b) * y1 (hệ số của a % b trong bước đệ quy). Phép chia / trong C++ tự động làm tròn xuống với số nguyên, tương ứng với $\lfloor a/b \rfloor$.
   • Hàm trả về cấu trúc ExtendedGcdResult chứa $\gcd$, x, và y cho cặp số đầu vào $(a, b)$.
4. modularInverse(long long a, long long m):
   • Hàm này sử dụng extendedEuclidean để tìm nghịch đảo đồng dư.
   • Nó gọi extendedEuclidean(a, m).
   • Kiểm tra nếu result.gcd khác 1. Nếu có, nghĩa là a và m không nguyên tố cùng nhau, và nghịch đảo không tồn tại, hàm trả về -1.
   • Nếu $\gcd(a, m) = 1$, thì result.x là một giá trị thỏa mãn $a \cdot result.x + m \cdot result.y = 1$. Theo modulo m, ta có $a \cdot result.x \equiv 1 \pmod{m}$.
   • result.x có thể là một số âm. Để đưa nó về khoảng $[0, m-1]$, ta sử dụng công thức (result.x % m + m) % m. Hàm trả về giá trị này.

3.3. Ví dụ minh họa từng bước Giải thuật Euclid mở rộng (cho 48 và 18)

Tìm $\gcd(48, 18)$ và $x, y$ sao cho $48x + 18y = \gcd(48, 18)$.

1. extendedEuclidean(48, 18):
   • Gọi extendedEuclidean(18, 48 % 18) hay extendedEuclidean(18, 12).
2. extendedEuclidean(18, 12):
   • Gọi extendedEuclidean(12, 18 % 12) hay extendedEuclidean(12, 6).
3. extendedEuclidean(12, 6):
   • Gọi extendedEuclidean(6, 12 % 6) hay extendedEuclidean(6, 0).
4. extendedEuclidean(6, 0):
   • Base case! b=0. Trả về {gcd=6, x=1, y=0}. (Nghĩa là $6 \cdot 1 + 0 \cdot 0 = 6$)
5. Quay lại extendedEuclidean(12, 6):
   • recursiveResult = {gcd=6, x1=1, y1=0} (từ bước 4)
   • a=12, b=6. $\lfloor a/b \rfloor = \lfloor 12/6 \rfloor = 2$.
   • $x = y1 = 0$
   • $y = x1 - (a/b) y1 = 1 - 2 0 = 1$.
   • Trả về {gcd=6, x=0, y=1}. (Kiểm tra: $12 \cdot 0 + 6 \cdot 1 = 6$. Đúng!)
6. Quay lại extendedEuclidean(18, 12):
   • recursiveResult = {gcd=6, x1=0, y1=1} (từ bước 5)
   • a=18, b=12. $\lfloor a/b \rfloor = \lfloor 18/12 \rfloor = 1$.
   • $x = y1 = 1$
   • $y = x1 - (a/b) y1 = 0 - 1 1 = -1$.
   • Trả về {gcd=6, x=1, y=-1}. (Kiểm tra: $18 \cdot 1 + 12 \cdot (-1) = 18 - 12 = 6$. Đúng!)
7. Quay lại extendedEuclidean(48, 18):
   • recursiveResult = {gcd=6, x1=1, y1=-1} (từ bước 6)
   • a=48, b=18. $\lfloor a/b \rfloor = \lfloor 48/18 \rfloor = 2$.
   • $x = y1 = -1$
   • $y = x1 - (a/b) y1 = 1 - 2 (-1) = 1 + 2 = 3$.
   • Trả về {gcd=6, x=-1, y=3}. (Kiểm tra: $48 \cdot (-1) + 18 \cdot 3 = -48 + 54 = 6$. Đúng!)

Kết quả cuối cùng: $\gcd(48, 18) = 6$, và $48 \cdot (-1) + 18 \cdot 3 = 6$.

4. Giải Phương trình Đồng dư Tuyến tính hoàn chỉnh bằng C++

Bây giờ chúng ta đã có công cụ để tìm $\gcd$ và nghịch đảo đồng dư, ta có thể xây dựng hàm giải phương trình đồng dư tuyến tính $ax \equiv b \pmod{m}$.

#include <iostream>
#include <vector>
#include <numeric> // for std::gcd if available
#include <algorithm> // for std::swap

// Re-include or ensure the previous code for extendedEuclidean and modularInverse is available

// Hàm tính gcd (dùng cho C++14 trở xuống hoặc để tự luyện)
long long manual_gcd(long long a, long long b) {
    a = std::abs(a); // GCD is always non-negative
    b = std::abs(b);
    while (b) {
        a %= b;
        std::swap(a, b);
    }
    return a;
}

// Cấu trúc để trả về kết quả từ Extended Euclidean Algorithm
struct ExtendedGcdResult {
    long long gcd;
    long long x;
    long long y;
};

// Hàm triển khai Extended Euclidean Algorithm (đệ quy)
ExtendedGcdResult extendedEuclidean(long long a, long long b) {
    if (b == 0) {
        return {a, 1, 0};
    }
    ExtendedGcdResult recursiveResult = extendedEuclidean(b, a % b);
    long long gcd = recursiveResult.gcd;
    long long x1 = recursiveResult.x;
    long long y1 = recursiveResult.y;
    long long x = y1;
    long long y = x1 - (a / b) * y1;
    return {gcd, x, y};
}


// Hàm giải phương trình đồng dư tuyến tính ax = b (mod m)
// Trả về vector chứa các nghiệm trong khoảng [0, m-1]
// Trả về vector rỗng nếu không có nghiệm
std::vector<long long> solveLinearCongruence(long long a, long long b, long long m) {
    std::vector<long long> solutions;

    // Đảm bảo a, b nằm trong khoảng modulo [0, m-1]
    // Cẩn thận với a âm
    a = (a % m + m) % m;
    b = (b % m + m) % m;

    // Tính gcd(a, m) bằng Extended Euclidean Algorithm
    ExtendedGcdResult result = extendedEuclidean(a, m);
    long long d = result.gcd;
    long long x_particular = result.x; // Một giá trị x từ ax + my = d

    // Bước 1: Kiểm tra điều kiện có nghiệm
    if (b % d != 0) {
        // Không có nghiệm
        return solutions; // Trả về vector rỗng
    }

    // Bước 2: Nếu có nghiệm, tìm một nghiệm riêng
    // Ta có ax + my = d. Nhân cả hai vế với b/d:
    // a * (x * b/d) + m * (y * b/d) = d * b/d = b
    // So sánh với ax' + my' = b, ta thấy x' = x * b/d là một nghiệm riêng của ax + my = b
    // Từ đó suy ra a * (x * b/d) = b (mod m)
    // Vậy (x * b/d) là một nghiệm của ax = b (mod m)
    // Ta dùng x_particular từ kết quả extendedEuclidean
    long long x0 = x_particular * (b / d);

    // Đảm bảo nghiệm riêng ban đầu nằm trong khoảng [0, m-1]
    x0 = (x0 % m + m) % m;

    // Bước 3: Tìm tất cả d nghiệm không đồng dư modulo m
    // Các nghiệm có dạng x = x0 + k * (m/d) (mod m) với k = 0, 1, ..., d-1
    for (int k = 0; k < d; ++k) {
        solutions.push_back((x0 + k * (m / d)) % m);
    }

    // Các nghiệm tìm được có thể chưa được sắp xếp,
    // nếu cần, có thể sắp xếp vector solutions.
    // std::sort(solutions.begin(), solutions.end());

    return solutions;
}

int main() {
    // Ví dụ 1: 3x = 5 (mod 7)
    // gcd(3, 7) = 1. 1 chia hết cho 5. Có 1 nghiệm.
    // Inverse of 3 mod 7: 3*x = 1 (mod 7). 3*5 = 15 = 1 (mod 7). Inverse is 5.
    // x = 5 * 5 = 25 = 4 (mod 7).
    long long a1 = 3, b1 = 5, m1 = 7;
    std::vector<long long> sols1 = solveLinearCongruence(a1, b1, m1);
    std::cout << "Solving " << a1 << "x = " << b1 << " (mod " << m1 << ")\n";
    if (sols1.empty()) {
        std::cout << "No solution.\n";
    } else {
        std::cout << "Solutions: ";
        for (long long sol : sols1) {
            std::cout << sol << " ";
        }
        std::cout << "\n"; // Expected: Solutions: 4
    }
    std::cout << "--------------------\n";

    // Ví dụ 2: 2x = 3 (mod 4)
    // gcd(2, 4) = 2. 2 không chia hết cho 3. Vô nghiệm.
    long long a2 = 2, b2 = 3, m2 = 4;
    std::vector<long long> sols2 = solveLinearCongruence(a2, b2, m2);
    std::cout << "Solving " << a2 << "x = " << b2 << " (mod " << m2 << ")\n";
    if (sols2.empty()) {
        std::cout << "No solution.\n"; // Expected: No solution.
    } else {
        std::cout << "Solutions: ";
        for (long long sol : sols2) {
            std::cout << sol << " ";
        }
        std::cout << "\n";
    }
     std::cout << "--------------------\n";

    // Ví dụ 3: 2x = 2 (mod 4)
    // gcd(2, 4) = 2. 2 chia hết cho 2. Có 2 nghiệm.
    // Reduce: 1x = 1 (mod 2). Nghiệm mod 2 là x=1.
    // Nghiệm ban đầu: x = 1 + k * (4/2) = 1 + 2k (mod 4).
    // k=0: x = 1 (mod 4)
    // k=1: x = 1 + 2 = 3 (mod 4)
    // Nghiệm: 1, 3.
    long long a3 = 2, b3 = 2, m3 = 4;
    std::vector<long long> sols3 = solveLinearCongruence(a3, b3, m3);
    std::cout << "Solving " << a3 << "x = " << b3 << " (mod " << m3 << ")\n";
    if (sols3.empty()) {
        std::cout << "No solution.\n";
    } else {
        std::cout << "Solutions: ";
        for (long long sol : sols3) {
            std::cout << sol << " ";
        }
        std::cout << "\n"; // Expected: Solutions: 1 3 (order might vary depending on initial x0)
    }
    std::cout << "--------------------\n";

     // Ví dụ 4: 6x = 15 (mod 21)
    // gcd(6, 21) = 3. 3 chia hết cho 15. Có 3 nghiệm.
    // Reduce: 2x = 5 (mod 7). gcd(2, 7) = 1.
    // Inverse of 2 mod 7: 4 (2*4=8=1 mod 7)
    // Nghiệm mod 7: x = 4 * 5 = 20 = 6 (mod 7). Nghiệm x0' = 6 (mod 7).
    // Nghiệm ban đầu: x = 6 + k * (21/3) = 6 + 7k (mod 21).
    // k=0: x = 6 (mod 21)
    // k=1: x = 6 + 7 = 13 (mod 21)
    // k=2: x = 6 + 14 = 20 (mod 21)
    // Nghiệm: 6, 13, 20.
    long long a4 = 6, b4 = 15, m4 = 21;
    std::vector<long long> sols4 = solveLinearCongruence(a4, b4, m4);
    std::cout << "Solving " << a4 << "x = " << b4 << " (mod " << m4 << ")\n";
    if (sols4.empty()) {
        std::cout << "No solution.\n";
    } else {
        std::cout << "Solutions: ";
        for (long long sol : sols4) {
            std::cout << sol << " ";
        }
        std::cout << "\n"; // Expected: Solutions: 6 13 20 (order might vary)
    }


    return 0;
}

Giải thích Code:

1. solveLinearCongruence(long long a, long long b, long long m): Hàm chính để giải phương trình.
2. a = (a % m + m) % m; b = (b % m + m) % m;: Bước quan trọng để chuẩn hóa a và b về phạm vi $[0, m-1]$ trước khi tính $\gcd$ hoặc xử lý, tránh các vấn đề với số âm và phép modulo.
3. ExtendedGcdResult result = extendedEuclidean(a, m); long long d = result.gcd;: Tính $d = \gcd(a, m)$ và lấy giá trị x (x_particular) từ đồng nhất thức $ax + my = d$.
4. if (b % d != 0): Kiểm tra điều kiện có nghiệm. Nếu $b$ không chia hết cho $d$, trả về vector rỗng.
5. long long x0 = x_particular * (b / d);: Đây là cách tìm một nghiệm riêng. Từ $ax + my = d$, nhân với $b/d$ (vì ta biết $d|b$, phép chia này là nguyên): $a(x \cdot b/d) + m(y \cdot b/d) = d(b/d) = b$. Theo modulo $m$, $a(x \cdot b/d) \equiv b \pmod{m}$. Vậy $x_0 = x \cdot b/d$ là một nghiệm.
6. x0 = (x0 % m + m) % m;: Chuẩn hóa nghiệm riêng $x_0$ về phạm vi $[0, m-1]$.
7. for (int k = 0; k < d; ++k): Vòng lặp để tìm tất cả $d$ nghiệm không đồng dư. Công thức nghiệm là $x_0 + k \cdot (m/d)$, với $k$ chạy từ 0 đến $d-1$. Mỗi nghiệm được tính và chuẩn hóa modulo $m$ trước khi thêm vào vector solutions.
8. Hàm trả về vector chứa tất cả các nghiệm tìm được.

Bài tập ví dụ:

Số Smith

Đề bài

Cho số tự nhiên N. Nhiệm vụ của bạn là hãy kiểm tra N có phải là số Smith hay không.

Một số được gọi là số Smith nếu:

• N không phải là số nguyên tố
• Tổng các chữ số của N bằng tổng các chữ số của các thừa số nguyên tố trong phân tích của N.

Ví dụ: N = 666 có các thừa số nguyên tố là 2, 3, 3, 37 có tổng các chữ số là 2 + 3 + 3 + (3 + 7) = 18, và tổng các chữ số của 666 là 6 + 6 + 6 = 18.

Input Format

Số nguyên dương N (1 ≤ N ≤ 10^8).

Constraints

Không có ràng buộc thêm.

Output Format

In ra YES nếu N là số Smith, ngược lại in ra NO.

Sample Input 0

12

Sample Output 0

NO

Sample Input 1

22

Sample Output 1

YES

Hướng dẫn giải bài Số Smith bằng C++ (ngắn gọn, không code hoàn chỉnh):

1. Hiểu định nghĩa: Số Smith N phải thỏa 2 điều kiện:

   • N không phải là số nguyên tố.
   • Tổng các chữ số của N bằng tổng các chữ số của các thừa số nguyên tố trong phân tích của N (có tính bội).

2. Hàm tính tổng chữ số: Viết một hàm riêng để tính tổng các chữ số của một số nguyên bất kỳ. Ví dụ: sum_digits(int num).

3. Phân tích thừa số nguyên tố và tính tổng chữ số của chúng:

   • Cần một biến để lưu tổng chữ số của các thừa số nguyên tố (sum_prime_factor_digits).
   • Duyệt các số i từ 2 lên đến căn bậc hai của số N ban đầu.
   • Nếu i là ước của N, thì i là một thừa số nguyên tố.
     • Cộng sum_digits(i) vào sum_prime_factor_digits.
     • Chia N cho i. Lặp lại bước này cho đến khi N không còn chia hết cho i nữa (để xử lý các thừa số lặp lại, ví dụ: 666 = 2 3 3 * 37, số 3 được xử lý hai lần).
   • Sau khi vòng lặp kết thúc, nếu N vẫn còn lớn hơn 1, thì phần còn lại của N chính là một thừa số nguyên tố lớn (lớn hơn căn bậc hai của N ban đầu). Cộng sum_digits(N) (phần còn lại này) vào sum_prime_factor_digits.

4. Kiểm tra tính nguyên tố/hợp số trong quá trình phân tích:

   • Trong quá trình phân tích ở bước 3, nếu chúng ta tìm được bất kỳ ước nào i từ 2 trở lên và chia N xuống, điều đó có nghĩa là N ban đầu là số hợp số (vì nó có ít nhất một ước nhỏ hơn chính nó, lớn hơn 1). Sử dụng một biến cờ (flag) để ghi nhớ điều này.
   • N ban đầu là số nguyên tố nếu và chỉ nếu sau khi kết thúc quá trình phân tích ở bước 3, số N ban đầu không bị giảm xuống 1, và ta chưa từng tìm thấy ước nào nhỏ hơn nó (ngoại trừ chính nó). Một cách khác để kiểm tra: nếu số N ban đầu không bị giảm xuống (tức là phần còn lại của N sau vòng lặp bước 3 bằng N ban đầu), thì N ban đầu là số nguyên tố.
   • Số 1 không phải là số nguyên tố cũng không phải là hợp số. Bài toán yêu cầu N >= 1. N=1 không phải là số Smith.

5. Logic chính:

   • Đọc số N.
   • Xử lý trường hợp đặc biệt N = 1: In ra NO.
   • Lưu lại N ban đầu để so sánh sau này.
   • Tính sum_digits(N ban đầu).
   • Thực hiện quá trình phân tích thừa số nguyên tố và tính sum_prime_factor_digits trên một bản sao của N (để không làm mất giá trị N ban đầu). Đồng thời sử dụng cờ để kiểm tra xem N ban đầu có phải là hợp số không.
   • Kiểm tra hai điều kiện:
     • N có phải là hợp số không? (Dựa vào cờ hoặc so sánh N ban đầu với phần còn lại sau phân tích).
     • sum_digits(N ban đầu) có bằng sum_prime_factor_digits không?
   • Nếu cả hai điều kiện đều đúng, in ra YES. Ngược lại, in ra NO.

Lưu ý: Khi phân tích thừa số nguyên tố, việc lặp i đến căn bậc hai của N là đủ để tìm tất cả các ước nguyên tố nhỏ, và nếu sau đó N > 1, phần còn lại đó sẽ là ước nguyên tố lớn nhất.

Làm thêm nhiều bài tập miễn phí tại đây