模方程组解法

2019-04-13 14:47发布

站内文章 / 模拟电子
10046 0 1570
void exgcd(int a,int b,int &d,int &x,int &y){ if(!b) { d=x; x=1,y=0; } else { exgcd(b,a%b,d,y,x); y-=x*(a/b); } } int Abs(int x) { return x<0?-x:x; } int Gauss_mod(int A[][100],int n,int m){//n个方程，m-1个变量，最后一列是系数列 int i,j; for(i=0,j=0;i//化成上三角阵 int maxr=i; for(int k=i+1;kif(Abs(A[k][j])>Abs(A[maxr][j])) maxr=k;//第i列最大行 if(Abs(A[maxr][j])==0) {j++,i--; continue; } if(maxr!=i) for(int jj=j;jj//交换行 for(int k=i+1;k//消元 if(A[k][j]){ int tmpa=A[i][j],tmpb=A[k][j]; for(int l=j;l*tmpa-A[i][l]*tmpb)%p; if(A[k][l]<0) A[k][l]+=p; } } } j++; } for(int k=i;kif(A[k][m-1]) return -1; }//之后的行的最后一列如果存在非0元素，则无解 int free_num=n-i;//自由变量个数 for(int k=0;k//交换列，使得对角元非0 ----不确定此步正确性 if(!A[k][k]){ int l=k; for(int l=k+1;lif(A[k][l]) break; if(l>k) for(int h=0;h0,sizeof(x)); for(int i=n-1;i>=0;i--){//代入求解 int tmp=A[i][n]; for(int j=i+1;j*A[i][j])%p+p)%p; } int d,xx,yy; exgcd(A[i][i],p,d,xx,yy); x[i]=(tmp*((xx%p+p)%p))%p;; } return 1<//返回解的个数 }