高斯消元想必大家应该都不陌生
对于数学中的解多元一次方程组使用的一般都是高斯消元（当年蒟蒻的我还不知道高斯消元这么low）
我们知道，对于高斯消元解普通线性方程时，
只需将方程造成一个倒三角即可
即每个方程比上一个方程少一个未知数，
然后从最后一个方程开始依次计算出每个未知数的大小
当然有些情况下，在我们消元到某一个方程时，会发现将要消去的未知数已经没了
于是我们可以在后面找到一个该未知数系数不为0的方程，与当前方程进行交换
当然如果在后面找不到这样一个方程，无视这个未知数将他当成0就好了
毕竟一般的解方程都是输出一组解即可
代码如下： int a[M][M],ans[M],Id[M]; //a[1~n][1~m]代表每个方程每个未知数的系数，a[1~n][0]代表这个方程的值 //ans[1~m]代表每个未知数的解 //Id[1~n]代表每个方程解出的是哪一个未知数 void solve(){ memset(Id,-1,sizeof(Id)); for(int i=1,id=1;i<=n;i++){ if(id==m+1){ for(int j=id;j<=n;j++) if(a[j][0]){puts("-1");exit(0);} //解完后剩下的方程所有的未知数系数均为0，值确不为0，所以此时无解 break; } bool f=0; while(!f&&id<=m){ for(int j=i;j<=n;j++) if(a[j][id]){f=1;break;} if(f){ for(int j=i;j<=n;j++) if(a[j][id]){//找到第一个第id个未知数系数不为0的方程 for(int k=0;k<=m;k++)swap(a[i][k],a[j][k]); break; } for(int j=i+1;j<=n;j++) if(a[j][id])for(int k=0,tmp=a[j][id];k<=m;k++) a[j][k]=a[i][id]*a[j][k]-tmp*a[i][k];//消元，构造倒三角 Id[i]=id; } id++;//该未知数不存在，无视之，但当前方程还存在，应用其去解下一个未知数 } } for(int i=n;i>=1;i--){ if(Id[i]==-1)continue; ans[Id[i]]=a[i][0]/a[i][Id[i]];//计算解 for(int j=i-1;j>=1;j--)a[j][0]=a[j][0]-ans[Id[i]]*a[j][Id[i]]; } } 那么又怎么解模线性方程组呢
模线性方程组，顾名思义，即多个形如(a1x1+a2x2+a3x3+…+anxn)%P=k的方程组成的方程组
这种方程这么解呢，其实和普通的线性方程组没有什么区别
现在%P意义用上述方法得到以下n个式子
b1x1=k1
b2x2=k2
b3x3=k3
…
bnxn=kn
而后在P范围内枚举，找到第一个j满足b∗j%P==k即是一组解
然而这仅适用于P为质数的情况
由于质数与小于它的所有数都互质，所以可以这样计算
但若不是互质我们只需将其分解为n个质数，在这%primei都进行一次解方程
最后从小到大找到以一个满足每一个方程的数即可
代码就不给出了，只需在之前代码的基础上稍作改动即可