Advertisement
Guest User

Untitled

a guest
Feb 17th, 2018
67
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 4.14 KB | None | 0 0
  1. { Free Pascal }
  2. var a,b: array[1..8000] of longint; c,d,g: longint;
  3. o: text; i,j,k,l,m,n,i0,ii,jj,jk,kk,m1: word;
  4.  
  5. function gcd(j,k:longint):longint; var a,b,c:longint; begin
  6. if j=0 then gcd:=abs(k) else
  7. if k=0 then gcd:=abs(j) else begin
  8. a:=abs(j); b:=abs(k); repeat c:=a mod b; a:=b; b:=c
  9. until b=0; gcd:=a end end;
  10. {‡зЁвгў ­­п ¤ ­Ёе} begin
  11. assign(o,'linear.in'); reset(o); read(o,n,m); m1:=m+1;
  12. for j:=1 to m1*n do read(o,a[j]); close(o); i0:=1;
  13. for j:=1 to m1*n do b[j]:=1;
  14. assign(o,'linear.out'); rewrite(o);
  15. {‚бв ­®ў«Ґ­­п ­Ґбг¬чб­®бвч,
  16. ўЁ«г祭­п в®в®¦­®б⥩ ч cЄ®а®зҐ­­п Є®Ґдчжчх­вчў ачў­п­м}
  17. j:=0; while j<n do begin
  18. g:=a[j*m1+1]; for k:=j*m1+2 to j*m1+m do begin
  19. g:=gcd(g,a[k]); if g=1 then break end;
  20. j:=j+1; if g=0 then begin
  21. if (a[j*m1]<>0) then begin
  22. writeln(o,' ‘Ёб⥬  ­Ґбг¬чб­ !'); close(o); halt end
  23. else begin
  24. {‚Ё«г祭­п в®в®¦­®бвч} n:=n-1; j:=j-1; kk:=(n-j)*m1;
  25. for k:=j*m1+1 to (j+1)*m1 do a[k]:=a[k+kk] end end
  26. else begin
  27. g:=gcd(g,a[j*m1]); if g<>1 then
  28. for k:=(j-1)*m1+1 to j*m1 do a[k]:=a[k] div g end end;
  29.  
  30. {‚ЁЄ«о祭­п §¬ч­­®щ i} for i:=1 to m do begin
  31. ii:=(i0-1)*m1; if a[ii+i]=0 then for j:=i0+1 to n do
  32. if a[(j-1)*m1+i]<>0 then begin
  33. {Њч­пх¬® ап¤ЄЁ j, i0 ¬чбжп¬Ё}
  34. l:=(j-i0)*m1; for k:=(i0-1)*m1+1 to i0*m1 do begin
  35. kk:=k+l; c:=a[k]; a[k]:=a[kk]; a[kk]:=c;
  36. d:=b[k]; b[k]:=b[kk]; b[kk]:=d end;
  37. break end;
  38. {‚бв ­®ў«Ґ­­п § «Ґ¦­®бвч §¬ч­­®щ i ўч¤ ч­иЁе §¬ч­­Ёе}
  39. if a[ii+i]<>0 then begin
  40. c:=a[ii+i]; d:=b[ii+i]; if c<0 then begin c:=-c; d:=-d end;
  41. a[ii+i]:=1; b[ii+i]:=1; for k:=ii+i+1 to ii+m1 do begin
  42. a[k]:=a[k]*d; b[k]:=b[k]*c; g:=gcd(a[k],b[k]);
  43. a[k]:=a[k] div g; b[k]:=b[k] div g end;
  44.  
  45. {‚Ё«г祭­п i-®щ §¬ч­­®щ § гбче ачў­п­м, Єач¬ i0-Ј®}
  46. j:=0; while j<n do begin
  47. jj:=j*m1; j:=j+1;
  48. jk:=jj+i; if (j<>i0) and (a[jk]<>0) then begin
  49. for k:=1 to m1 do if k<>i then begin
  50. c:=a[jk]*a[ii+k]; d:=b[jk]*b[ii+k]; g:=gcd(c,d);
  51. c:=c div g; d:=d div g; kk:=jj+k;
  52. a[kk]:=a[kk]*d-b[kk]*c; b[kk]:=b[kk]*d;
  53. g:=gcd(a[kk],b[kk]); if g<>1 then begin
  54. a[kk]:=a[kk] div g; b[kk]:=b[kk] div g end end;
  55. a[jj+i]:=0; b[jj+i]:=1;
  56. k:=1; {ЏҐаҐўчаЄ  ачў­п­­п j ­  бг¬чб­чбвм}
  57. while (k<m1) and (a[jj+k]=0) do k:=k+1; if k=m1 then begin
  58. if a[jj+m1]<>0 then begin
  59. writeln(o,'No solution'); close(o); halt end;
  60. kk:=(n-j)*m1; n:=n-1; j:=j-1;
  61. {‚Ё«г祭­п в®в®¦­®бвч} for k:=jj+1 to jj+m1 do begin
  62. a[k]:=a[k+kk]; b[k]:=b[k+kk] end end end end;
  63. i0:=i0+1 end;
  64. if i0>n then break end;
  65. if i0=m1 then begin
  66. for j:=1 to m do begin
  67. k:=j*m1; write(o,' ',a[k]);
  68. if b[k]>1 then write(o,'/',b[k]) end;
  69. writeln(o) end
  70. else for j:=0 to i0-2 do begin
  71. jj:=j*m1; for i:=1 to m1 do begin
  72. kk:=jj+i; write(o,' ',a[kk]);
  73. if b[kk]>1 then write(o,'/',b[kk]) end; writeln(o) end;
  74. close(o); halt end.
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement