数论 高斯消元法

0.1 概述

既然名为“高斯消元法”，肯定是高斯小朋友发明的。是一个复杂度(O(n^3))的算法。（对不起，floyd君！再也不嘲讽你的复杂度了::>_<::）

这个算法的应用主要分为两类：“辗转相除法”和“列主元消元”

1.1 列主元消元

嘿，我就不按顺序来

这个方法的适用特征为：出现实数，提高精度。简单概括，就是多适用于解方程的时候

将方程的系数和常数结起来，得到一个(ntimes （n+1）)的矩阵。如果这个矩阵可以被化简成上三角矩阵，且主对角线上值不为零，则此时必对应着一个唯一解；否则，就是无解或多解的情况。后两者都不属于高斯消元考虑的范围。

方法也很简单：枚举每一列，挑一行，用这一行去化简所其它行，使该列系数化为零。（原谅我的表达能力）

举个栗孑：

至此便得到了一个上三角矩阵，对应着一个唯一解。比下往上回溯代入即可φ(゜▽゜*)♪

int calc(){
        lor(i,1,n){
            double top=0.0; int pos=0;
            lor(j,i,n) if(fabs(num[j][i])>EPS&&fabs(num[j][i])>top) pos=j,top=fabs(num[j][i]);
            if(!pos) return false;
            swap(num[i],num[pos]);
            lor(j,i+1,n){
                double ratio=num[j][i]/num[i][i];
                lor(k,i,n+1) num[j][k]-=ratio*num[i][k];
            }
        }
        ror(i,1,n){
            ans[i]=num[i][n+1];
            lor(j,i+1,n) ans[i]=ans[i]-num[i][j]*ans[j];
            ans[i]=ans[i]/num[i][i];
        }
        return true;
    }

tips:

1. 由于是实数间的操作，因此应当注意精度误差

2. 为了保证精度，每一次应当挑选绝对值最大的作为主元

2.1 辗转相除法

这种方法适用于：仅出现整数，避免出现实数。简单说，多用于：行列式求值

行列式求值中常常会遇到系数均为整的情况，此时若使用“列主元法”将会导致引入实数，从而致使精度降低。

“辗转相除法”便可以做到在不引入实数的同时消元

回想一下欧几里得算法里的辗转相除：

借用过来其实别无二致，举个例子：

为了方便，设(t=lfloorfrac{6}{3}rfloor=2)

到这一步了，行列式求值什么的自然不在话下了( •̀ ω •́ )✧

lor(i,1,cnt){
        int pos=0;
        lor(j,i,cnt) if(f[j][i]) {pos=j; break;}
        if(!pos) {ans=0; break;}
        lor(j,i,cnt) swap(f[i][j],f[pos][j]);
        if(i!=pos) ans=-ans;
        lor(j,i+1,cnt){
            while(f[j][i]){
                swap(f[i],f[j]);
                ll t=f[j][i]/f[i][i];
                lor(k,i,cnt) f[j][k]=((f[j][k]-t*f[i][k])%MOD+MOD)%MOD;
//              lor(k,i,cnt) f[j][k]-=t*f[i][k];
                ans=-ans;
            }
        }
        ans=((ans*f[i][i]%MOD)+MOD)%MOD;
    }