高斯消元

用于求$n$元一次线性方程组的方法，复杂度$O(n^3)$

例题 洛谷P2455

已知 $n$ 元线性一次方程组。

$$\left\{\begin{array}{l}a_{1,1} x_{1}+a_{1,2} x_{2}+\cdots+a_{1, n} x_{n}=b_{1} \\a_{2,1} x_{1}+a_{2,2} x_{2}+\cdots+a_{2, n} x_{n}=b_{2} \\\cdots \\a_{n, 1} x_{1}+a_{n, 2} x_{2}+\cdots+a_{n, n} x_{n}=b_{n}\end{array}\right.$$

请根据输入的数据，编程输出方程组的解的情况。

如果有唯一解，则输出解（小数点后保留两位小数）。

如果方程组无解输出 -1； 如果有无穷多实数解，输出 0；

AC代码（存在缺陷）

#include <bits/stdc++.h>
#define Android ios::sync_with_stdio(false), cin.tie(NULL)
using namespace std;

double matrix[120][120], ans[120] = {0}, eps = 1e-8;

inline bool isZero(double val){return fabs(val) < eps;}

bool cmp(int n, int col, int i, int j){
    if(!isZero(fabs(matrix[i][col]) - fabs(matrix[j][col]))) 
        return fabs(matrix[i][col]) > fabs(matrix[j][col]);
    // 若当前系数相同，则使得后面的系数尽量小，否则后面某些元无法消去 
    // 当然，若不需要区分无解和多解的情况，则不必如此
    // 当发现当前列(元)的最大系数为0即为无解/多解
    for(int c=col+1;c<=n;c++){
        if(!isZero(fabs(matrix[i][c]) - fabs(matrix[j][c])))
            return fabs(matrix[i][c]) < fabs(matrix[j][c]);
    }
    return false;
}

void solve(){
    int n;
    cin >> n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n + 1;j++)
            cin >> matrix[i][j];
    }

    for(int i=1;i<=n;i++){
        int mx_row = i;
        for(int j=i;j<=n;j++)
            if(cmp(n, i, j, mx_row)) mx_row = j;

        if(i != mx_row) swap(matrix[i], matrix[mx_row]);
        if(isZero(matrix[i][i])) continue;

        double ori_factor = matrix[i][i];
        for(int j=i;j<=n+1;j++) matrix[i][j] /= ori_factor;

        for(int j=i+1;j<=n;j++){
            double factor = matrix[j][i];
            for(int k=i;k<=n+1;k++)
                matrix[j][k] -= factor * matrix[i][k];
        }
    }

    //无解或多解
    bool noans = false, multians = false;

    for(int i=n;i>0;i--){
        ans[i] = matrix[i][n+1];
        for(int j=i+1;j<=n;j++)
            ans[i] -= matrix[i][j] * ans[j];
        if(isZero(ans[i]) && isZero(matrix[i][i])) multians = true;
        if(!isZero(ans[i]) && isZero(matrix[i][i])) noans = true;
    }

    if(noans || multians){
        cout << (noans?-1:0) << '\n';
    }else{
        for(int i=1;i<=n;i++)
            cout << "x" << i << "=" << fixed << setprecision(2) << ans[i] << '\n';
    }
}

signed main(){
    Android;
    solve();
}

AC代码2

上述模板当$n$较大时，可能被精心构造的数据卡（原因在于cmp函数）。因此在上述模板的基础上稍作修改，当当前列的最大系数为0时，并不基于若当前系数相同，则使得后面的系数尽量小来交换行，而是直接忽略当前列。

#include <bits/stdc++.h>
#define ll long long
#define Android ios::sync_with_stdio(false), cin.tie(NULL)
using namespace std;

double matrix[120][120], ans[120] = {0}, eps = 1e-8;

inline bool isZero(double val){return fabs(val) < eps;}

void solve(){
    int n;
    cin >> n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n + 1;j++)
            cin >> matrix[i][j];
    }

    int row = 1; // 用来保存最终遍历到第几行
    for(int col=1; col<=n ;row++, col++){
        int mx_row = row;
        for(int j=row + 1;j<=n;j++){
            if(fabs(matrix[mx_row][col]) < fabs(matrix[j][col])) mx_row = j;
        }

        if(isZero(matrix[mx_row][col])) {
            row--;
            continue;
        }

        if(row != mx_row) swap(matrix[row], matrix[mx_row]);

        double ori_factor = matrix[row][col];
        for(int j=col;j<=n+1;j++) matrix[row][j] /= ori_factor;

        for(int j=row+1;j<=n;j++){
            double factor = matrix[j][col];
            for(int k=col;k<=n+1;k++)
                matrix[j][k] -= factor * matrix[row][k];
        }
    }
    
    row--;

    bool noans = false, multians = row < n; // 方程个数小于未知量个数，则可能多解
    for(int i=row + 1; i<=n; i++){ // 遍历未知量系数全为0的方程
        if(!isZero(matrix[i][n + 1])) noans = true;
    }

    fill(ans, ans + 120, 0.); // 贪心的让自由元等于0
    for(int col = n; row > 0 && !noans; row--, col>0?col--:0){
        while(col > 0 && isZero(matrix[row][col])) col--;
        
        ans[col] = matrix[row][n+1];
        for(int j=col + 1; j<=n; j++) ans[col] -= matrix[row][j] * ans[j];

        if(col == 0 && !isZero(ans[0])) noans = true; // 等式不成立
    }

    if(noans || multians){
        cout << (noans?-1:0) << '\n';
    }else{
        for(int i=1;i<=n;i++)
            cout << "x" << i << "=" << fixed << setprecision(2) << ans[i] << '\n';
    }
}

signed main(){
    Android;
    solve();
}

模意义下的高斯消元

模数为质数

当式$i,j$消元时，设式$x$的主元系数为$a_x$，则式$i$乘上$lcm(a_i,a_j)/a_i$，式$j$乘上$lcm(a_i,a_j)/a_j$，接着两式相减即可。

倒推求解时，使用逆元进行模意义下的除法即可。