Tác giả:
- Hà Phước Vũ - Lớp 10A5, trường THPT chuyên Lê Quý Đôn, Đà Nẵng.

## I. Giới thiệu.
Chắc hẳn khi học Toán, các bạn đã từng giải một số bài bằng cách lập hệ phương trình. Đa phần những hệ phương trình đó là hệ phương trình bậc nhất hai ẩn có dạng như sau:
\begin{cases}
ax + by = c \\
dx + ey = f \\
\end{cases}
Ngoài ra, trong một số bài nâng cao, không quá khó để ta bắt gặp những bài toán cần lập hệ phương trình bậc nhất ba ẩn có dạng như sau:
\begin{cases}
a_1x + b_1y + c_1z = d_1 \\
a_2x + b_2y + c_2z = d_2 \\
a_3x + b_3y + c_3z = d_3 \\
\end{cases}
Không chỉ có vậy, ta cũng có thể gặp một số dạng khá ảo diệu như tìm $\frac{1}{x}$ và $\frac{1}{y}$, $\frac{1}{x+y}$ và $\frac{1}{x-y}$, $...$ Tuy nhiên, tất cả đều có một dạng chung là.
\begin{cases}
a_{1, 1}x_1 + a_{1, 2}x_2 + ... + a_{1, n}x_n = b_1 \\
a_{2, 1}x_1 + a_{2, 2}x_2 + ... + a_{2, n}x_n = b_2 \\
... \\
a_{n, 1}x_1 + a_{n, 2}x_2 + ... + a_{n, n}x_n = b_n \\
\end{cases}

Hôm nay, ta sẽ xem qua cách giải hệ phương trình trên bằng một phương pháp khá phổ biến là Gaussian Elimination (hay là Khử Gauss trong tiếng Việt).
## II. Nội dung chính.
### 1. Ý tưởng.
Để đơn giản và dễ hiểu thì, phương pháp này thực chất là phiên bản mở rộng hơn của phương pháp Cộng đại số mà phần lớn chúng ta sử dụng hiện nay. Tại lần thứ $i$ khử hệ số của $x_i$ $(1 \le i \le n)$, ta sẽ tìm một phương trình $j$ $(1 \le j \le n)$ có $a_{j, i} \ne 0$ và $a_{j, 1} = a_{j, 2}$ $=$ $...$ $=$ $a_{j, i-1} = 0$ và khử hệ số của $x_i$ của $n-1$ phương trình còn lại (tức là đưa về $0$). Để sử dụng phương trình $j$ trên khử hệ số $x_i$ của các phương trình khác, ta chỉ đơn giản làm như sau:
- Ta chọn $2$ số thực khác nhau và nhân mỗi số cho mỗi phương trình sao cho hệ số của $x_i$ ở cả $2$ phương trình sau khi thực hiện bằng nhau.
- Trừ $2$ phương trình cho nhau và đặt phương trình bị khử là phương trình mới đó.

Ta cứ tiếp như thế cho đến khi nào các hệ số $x_i$ ở tất cả phương trình bị khử về $0$ là xong, sau đó tiếp tục khử các hệ số $x_{i+1}$, $x_{i+2}$, $...$, $x_n$.
### 2. Cài đặt.
Dựa vào ý tưởng của ta ở trên, ta có cài đặt như sau:

double a[N][N], b[N], X[N];
void flo() {
    int n; cin >> n; 
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> a[i][j];
        }
        cin >> b[i];
    }
    for (int x = 1; x <= n; x++) {
        int cur = -1; double coef;
        for (int i = 1; i <= n; i++) {
            if (a[i][x] != 0) {
                bool check = 1;
                for (int j = 1; j < x; j++) {
                    if (a[i][j] != 0) {
                        check = 0; break;
                    }
                }
                if (check == 1) {
                    cur = i; break;
                }
            }
            if (cur != -1) break;
        }
        coef = a[cur][x];
        for (int j = 1; j <= n; j++) {
            a[cur][j] *= 1.0/coef;
        }
        b[cur] *= 1.0/coef;
        for (int i = 1; i <= n; i++) {
            coef = a[i][x];
            if (i == cur) continue;
            if (coef == 0) continue;
            for (int j = 1; j <= n; j++) {
                a[i][j] *= 1.0/coef;
            }
            b[i] *= 1.0/coef;
            for (int j = 1; j <= n; j++) {
                a[i][j] -= a[cur][j];
            }
            b[i] -= b[cur];
        }
    }
    for (int i = 1; i <= n; i++) {
        int cur = -1;
        for (int j = 1; j <= n; j++) {
            if (a[i][j] != 0) {
                cur = j; break;
            }
        }
        X[cur] = b[i]*(1.0/a[i][cur]);
    }
    for (int i = 1; i <= n; i++) {
        cout << X[i] << " ";
    }
    cout << "\n"; return;
}

Độ phức tạp của ý tưởng trên là $O(n^3)$ về thời gian, $O(n^2)$ về bộ nhớ.

**Lưu ý:** Không phải hệ phương trình nào cũng có nghiệm, sẽ có một số rơi vào trường hợp vô nghiệm hoặc vô số nghiệm. Khi đó, bạn cần phải kiểm tra trước khi lấy nghiệm.
### 3. Hệ phương trình đồng dư.
Cụ thể hơn, chúng sẽ có dạng như sau:
\begin{cases}
a_{1, 1}x_1 + a_{1, 2}x_2 + ... + a_{1, n}x_n \equiv b_1 \ (mod\ p)\\
a_{2, 1}x_1 + a_{2, 2}x_2 + ... + a_{2, n}x_n \equiv b_2 \ (mod\ p)\\
... \\
a_{n, 1}x_1 + a_{n, 2}x_2 + ... + a_{n, n}x_n \equiv b_n \ (mod\ p)\\
\end{cases}
Nhìn có vẻ sussy baka như thế nhưng thực chất bạn chỉ việc giải như bình thường và cài đặt tương tự như trên. Khác cái là, vì đây là hệ phương trình đồng dư nên các ẩn sẽ là số nguyên, ta có thể các hệ số bằng cách đưa các hệ số của mỗi ẫn trong mỗi lần khử về bội chung nhỏ nhất của nó.

Với $p = 2$, ta nhận thấy các hệ số chỉ nhận giá trị $0$ và $1$. Từ đó, ta có thể sử dụng Bitset để tối ưu từ $O(n^3)$ xuống $O(\frac{n^3}{64})$ về thời gian. Việc trừ các hệ số khi đó chỉ đơn giản là thực hiện phép XOR giữa $2$ phương trình. Cụ thể hơn, ta có thể cài đặt như sau:

bitset<N> a[N], X;
void flo() {
    int n, c; cin >> n; 
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> c; a[i][j] = c;
        }
        cin >> c; a[i][n+1] = c; // b[i]
    }
    for (int x = 1; x <= n; x++) {
        int cur = -1; 
        for (int i = 1; i <= n; i++) {
            if (a[i]._Find_next(0) == x) {
                cur = i; break;
            }
        }
        for (int i = 1; i <= n; i++) {
            if (i == cur) continue;
            if (a[i][x] != 0) a[i] ^= a[cur];
        }
    }
    for (int i = 1; i <= n; i++) {
        X[a[i]._Find_next(0)] = a[i][n+1]; // b[i]
    }
    for (int i = 1; i <= n; i++) {
        cout << X[i] << " ";
    }
    cout << "\n"; return;
}

Ngoài ra, bộ nhớ của chúng ta cũng sẽ giảm từ $O(n^2)$ xuống $O(\frac{n^2}{64})$. Điều này đơn giản là vì khả năng thao tác bit nhanh và cắn ít bộ nhớ của kiểu dữ liệu Bitset.
### 4. Phương pháp khác.
Ngoài sử dụng phương pháp Khử Gauss, ta còn có một cách khác có lẽ ít phổ biến hơn là Quy tắc Cramer, và bạn có thể tìm đọc tại đây:
- [Determinants and Cramer's Rule for $n\times n$ matrices](https://math.libretexts.org/Courses/Cosumnes_River_College/Math_420%3A_Differential_Equations_(Breitenbach)/11%3A_Appendices/04%3A_Determinants_and_Cramer's_Rule_for_n_x_n_Matrices).

Tóm tắt lại, cách trên sẽ đưa về hệ phương trình về một [ma trận](https://en.wikipedia.org/wiki/Matrix_(mathematics)#:~:text=16%20External%20links-,Definition,array%20of%20elements%20of%20F.), sau đó tìm các nghiệm một cách độc lập dựa trên định thức của ma trận. Khác với Khử Gauss, cách này chỉ có một ứng dụng là tìm nghiệm trong khi Khử Gauss lại có thể tìm hạng của ma trận hay tính ma trận nghịch đảo của một ma trận vuông khả nghịch bất kỳ.
## III. Tổng kết.
Đây là một bài viết với mục đích giải trí nhưng mình vẫn hy vọng nó vẫn sẽ giúp ích cho bạn một phần nào. Chúc bạn có một ngày vui vẻ.

Về phần bài tập để luyện tập thì hiện tại, mình vẫn chưa tiếp xúc và làm nhiều bài sử dụng món này. Những thứ bên trên phần lớn là do mình tự nghĩ ra.

Nguồn tham khảo:
- [Wikipedia - Gaussian Elimination](https://en.wikipedia.org/wiki/Gaussian_elimination).