高斯消元专题 - c++编程基础

}
void init()
{
memset(a,0,sizeof(a));
memset(x,0,sizeof(x));
for(int i=0;i {
scanf("%d",&a[i][var]);
a[i][i]=1;
}
for(int i=0;i {
int p,q;
if(i-m>=0) p=i-m;else p=0;
if(i+m for(int j=p;j<=q;j++)
a[j][i]=1;
}
return ;
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
//cout<<"*"< equ=n;var=n;
init();
int ans=Gauss();
if(ans==inf) puts("impossible");
else printf("%d\n",ans);
}
return 0;
}

http://poj.org/problem id=2947
同余题
[cpp]
#include
#include
#include
#include

using namespace std;
const int maxn=301;
const int inf=0x3fffffff;
int a[maxn][maxn+1],x[maxn];
int equ,var,free_num;
char str[8][4]={"MON","TUE","WED","THU","FRI","SAT","SUN"};
__int64 exGcd(__int64 a,__int64 b, __int64 &xx, __int64 &yy)
{
if(b == 0)
{
xx = 1;
yy = 0;
return a;
}
__int64 r = exGcd(b, a % b, xx, yy);
__int64 t = xx;
xx = yy;
yy = t - a / b * yy;
return r;
}
int gcd(int a,int b)
{
if(a<0) return gcd(-a,b);
if(b<0) return gcd(a,-b);
return b==0 a:gcd(b,a%b);
}
void Gauss()
{

int k,col=0;
__int64 xx,yy;
for(k=0;k {
int mx=k;
for(int i=k+1;i if(abs(a[i][col])>abs(a[mx][col])) mx=i;
if(mx!=k)

for(int i=k;i if(!a[k][col]) { k--;continue; }
for(int i=k+1;i if(a[i][col]!=0)
{
int lcm=a[k][col]/gcd(a[k][col],a[i][col])*a[i][col];
int ta=lcm/a[i][col],tb=lcm/a[k][col];
if(a[i][col]*a[k][col] < 0) tb = -tb;
for(int j=col;j a[i][j]=((a[i][j]*ta)%7 - (a[k][j]*tb)%7+7)%7;
}
}
for(int i=k;i if(a[i][col]!=0) {puts("Inconsistent data.");return ;}
if(var>k){puts("Multiple solutions.");return ;}
for(int i=0,j;i if(a[i][i]==0)
{
for(j=i+1;j if(a[i][j]) break;
//if(var==j) break;
if(j>=var) break;
for(int r=0;r }

for(int i=k-1;i>=0;i--)
{
int tmp=a[i][var]%7;
for(int j=i+1;j if(a[i][j]) tmp=(tmp-a[i][j]*x[j]%7+7)%7;
__int64 d=exGcd(a[i][i],7,xx,yy);
if(tmp%d!=0){puts("Inconsistent data.");return ;}
else{
x[i]=tmp/d*xx%7+7;
x[i]=x[i]%(7/d);
}
while(x[i]<3) x[i]=x[i]+7;
}

for(int i=0;i {
if(i==0) cout< else cout<<" "< }
puts("");

}

void init()
{
memset(a,0,sizeof(a));
memset(x,0,sizeof(x));
int d;
char s1[4],s2[4];
for(int i=0;i {
scanf("%d%s%s",&d,s1,s2);
int q1,q2;
for(int j=0;j<8;j++)
if(!strcmp(s1,str[j])){q1=j;break;}
for(int j=0;j<8;j++)
if(!strcmp(s2,str[j])){q2=j;break;}
while(d--)
{
int num;
scanf("%d",&num); num--;a[i][num]++;
a[i][num]%=7;
}
a[i][var]=(q2-q1+1+7)%7;
}
return ;
}
int main()
{
while(scanf("%d%d",&var,&equ)!=EOF)
{
if(var==0&&equ==0) break;
init();
Gauss();

高斯消元专题(四)