202503021827 数论 高斯消元

解线性方程组

能在 n^3 时间复杂度求方程

模拟正常用行列式高斯消元的过程

1. 第一列中选择绝对值最大的一行
2. 放到第一行上
3. 将该列系数化为1
4. 循环123到最后一列
5. 之后逆序求解

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 1e2 + 10;
const double eps = 1e-6;
 
int n;
double a[N][N];
 
int gauss()
{
    int c,r;
    for(c = 0,r = 0; c < n; c++)
    {
        int t = r;
        for(int i = r; i < n; i++)
            if(fabs(a[i][c]) > fabs(a[t][c]))
                t = i;
        
        if(fabs(a[t][c]) < eps) continue;
        
        for(int i = c; i < n+1; i++) swap(a[t][i], a[r][i]); // 交换到第一行
        for(int i = n; i >= c; i--) a[r][i] /= a[r][c]; // 系数化为1
        for(int i = r + 1; i < n; i++) // 把其他行的删去
            if(fabs(a[i][c]) > eps)
                for(int j = n; j >= c; j--)
                    a[i][j] -= a[r][j] * a[i][c]; 
        
        r++;
    }
    
    if(r < n)
    {
        for(int i = r; i < n;i ++)
            if(fabs(a[i][n]) > eps) return 2;
        return 1;
    }
    
    for(int i = n - 2; i >= 0; i--)
        for(int j = i + 1; j < n; j++)
        {
            a[i][n] -= a[j][n] * a[i][j];
        }
    
    
    return 0;
}
 
 
int main()
{
    cin >> n;
    for(int i = 0; i < n;i ++)
        for(int j = 0; j < n + 1;j ++)
        {
            cin >> a[i][j];
        }
    int t = gauss();
    if(t == 0)
    {
        for(int i = 0; i < n;i ++) 
            if(a[i][n] != 0)
                printf("%.2lf\n", a[i][n]);
            else
                printf("0.00\n");
    }
    else if(t == 1) cout << "Infinite group solutions";
    else cout << "No solution";
}

异或线性方程组

类似于高斯消元, 把系数的算术变换改为异或运算, 实际上就是不进位的加法。

6. 依然是寻找最大值, 不过这里找到一个1就行
7. 交换到第一行
8. 不需要去化系数, 本身就是1
9. 将第一行式子与其他行式子相异或, 让该列为0
10. 重复以上操作直到最后一个
11. 然后逆向求解, 将一行中其他未知数的系数异或为0即可

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 110;
 
 
int a[N][N];
int n;
 
int gauss()
{
    int c,r;
    for(c = 0, r = 0; c < n; c++)
    {
        int  t =  -1;
        for(int i = r; i < n; i++)
            if(a[i][c]){t = i; break;}
        if(t == -1) continue;
        
        for(int i = 0; i < n + 1; i++) swap(a[r][i], a[t][i]);
        for(int i = r + 1; i < n; i++)
            if(a[i][c])
                for(int j = 0; j < n + 1; j++)
                    a[i][j] ^= a[r][j];
        r++;
    }
    
    if(r < n)
    {
        for(int i = r; i < n; i++)
            if(a[r][n]) return 2;
        return 1;
    }
    
    for(int i = n  - 1; i >= 0; i--)
        for(int j = i + 1; j < n; j++)
            if(a[i][j])
                a[i][n] ^= a[j][n];
    
    return 0;
}
 
 
 
int main()
{
    cin >> n;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n + 1; j++)
            cin >> a[i][j];
            
    int t = gauss();
    if(t == 0)
    {
        for(int i = 0; i < n;i ++) cout << a[i][n] << endl;
    }
    else if(t == 1) cout << "Multiple sets of solutions";
    else cout << "No solution";
    return 0;
}