Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- { Free Pascal }
- var a,b: array[1..8000] of longint; c,d,g: longint;
- o: text; i,j,k,l,m,n,i0,ii,jj,jk,kk,m1: word;
- function gcd(j,k:longint):longint; var a,b,c:longint; begin
- if j=0 then gcd:=abs(k) else
- if k=0 then gcd:=abs(j) else begin
- a:=abs(j); b:=abs(k); repeat c:=a mod b; a:=b; b:=c
- until b=0; gcd:=a end end;
- {‡зЁвгў п ¤ Ёе} begin
- assign(o,'linear.in'); reset(o); read(o,n,m); m1:=m+1;
- for j:=1 to m1*n do read(o,a[j]); close(o); i0:=1;
- for j:=1 to m1*n do b[j]:=1;
- assign(o,'linear.out'); rewrite(o);
- {‚бв ®ў«Ґп Ґбг¬чб®бвч,
- ўЁ«гзҐп в®в®¦®б⥩ ч cЄ®а®зҐп Є®Ґдчжчхвчў ачўпм}
- j:=0; while j<n do begin
- g:=a[j*m1+1]; for k:=j*m1+2 to j*m1+m do begin
- g:=gcd(g,a[k]); if g=1 then break end;
- j:=j+1; if g=0 then begin
- if (a[j*m1]<>0) then begin
- writeln(o,' ‘Ёб⥬ Ґбг¬чб !'); close(o); halt end
- else begin
- {‚Ё«гзҐп в®в®¦®бвч} n:=n-1; j:=j-1; kk:=(n-j)*m1;
- for k:=j*m1+1 to (j+1)*m1 do a[k]:=a[k+kk] end end
- else begin
- g:=gcd(g,a[j*m1]); if g<>1 then
- for k:=(j-1)*m1+1 to j*m1 do a[k]:=a[k] div g end end;
- {‚ЁЄ«озҐп §¬ч®щ i} for i:=1 to m do begin
- ii:=(i0-1)*m1; if a[ii+i]=0 then for j:=i0+1 to n do
- if a[(j-1)*m1+i]<>0 then begin
- {Њчпх¬® ап¤ЄЁ j, i0 ¬чбжп¬Ё}
- l:=(j-i0)*m1; for k:=(i0-1)*m1+1 to i0*m1 do begin
- kk:=k+l; c:=a[k]; a[k]:=a[kk]; a[kk]:=c;
- d:=b[k]; b[k]:=b[kk]; b[kk]:=d end;
- break end;
- {‚бв ®ў«Ґп § «Ґ¦®бвч §¬ч®щ i ўч¤ чиЁе §¬чЁе}
- if a[ii+i]<>0 then begin
- c:=a[ii+i]; d:=b[ii+i]; if c<0 then begin c:=-c; d:=-d end;
- a[ii+i]:=1; b[ii+i]:=1; for k:=ii+i+1 to ii+m1 do begin
- a[k]:=a[k]*d; b[k]:=b[k]*c; g:=gcd(a[k],b[k]);
- a[k]:=a[k] div g; b[k]:=b[k] div g end;
- {‚Ё«гзҐп i-®щ §¬ч®щ § гбче ачўпм, Єач¬ i0-Ј®}
- j:=0; while j<n do begin
- jj:=j*m1; j:=j+1;
- jk:=jj+i; if (j<>i0) and (a[jk]<>0) then begin
- for k:=1 to m1 do if k<>i then begin
- c:=a[jk]*a[ii+k]; d:=b[jk]*b[ii+k]; g:=gcd(c,d);
- c:=c div g; d:=d div g; kk:=jj+k;
- a[kk]:=a[kk]*d-b[kk]*c; b[kk]:=b[kk]*d;
- g:=gcd(a[kk],b[kk]); if g<>1 then begin
- a[kk]:=a[kk] div g; b[kk]:=b[kk] div g end end;
- a[jj+i]:=0; b[jj+i]:=1;
- k:=1; {ЏҐаҐўчаЄ ачўпп j бг¬чбчбвм}
- while (k<m1) and (a[jj+k]=0) do k:=k+1; if k=m1 then begin
- if a[jj+m1]<>0 then begin
- writeln(o,'No solution'); close(o); halt end;
- kk:=(n-j)*m1; n:=n-1; j:=j-1;
- {‚Ё«гзҐп в®в®¦®бвч} for k:=jj+1 to jj+m1 do begin
- a[k]:=a[k+kk]; b[k]:=b[k+kk] end end end end;
- i0:=i0+1 end;
- if i0>n then break end;
- if i0=m1 then begin
- for j:=1 to m do begin
- k:=j*m1; write(o,' ',a[k]);
- if b[k]>1 then write(o,'/',b[k]) end;
- writeln(o) end
- else for j:=0 to i0-2 do begin
- jj:=j*m1; for i:=1 to m1 do begin
- kk:=jj+i; write(o,' ',a[kk]);
- if b[kk]>1 then write(o,'/',b[kk]) end; writeln(o) end;
- close(o); halt end.
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement