Cod sursa(job #448997)

Utilizator marta_diannaFII Filimon Marta Diana marta_dianna Data 5 mai 2010 11:38:44
Problema Algoritmul lui Euclid extins Scor 0
Compilator fpc Status done
Runda Arhiva educationala Marime 1.5 kb
program p1;
var f,g:text;
    n,i,a,b,c,d,m,u,v:longint;
    x,y,r:array[1..1000] of longint;

function cmmdc(x,y:longint):longint;
var rr:longint;
begin
     rr:=x mod y;
     while rr>0 do
     begin
          x:=y;
          y:=rr;
          rr:=x mod y;
     end;
     cmmdc:=y;
end;

procedure generalizare;
var ct,rr:longint;
begin
     while r[m]<>0 do
     begin
          m:=m+1;
          r[m]:=r[m-2] mod r[m-1];
          ct:=r[m-2] div r[m-1];
          x[m]:=x[m-2]-ct*x[m-1];
          y[m]:=y[m-2]-ct*y[m-1];
     end;
end;

begin
     assign(f,'euclid3.in');reset(f);
     assign(g,'euclid3.out');rewrite(g);
     read(f,n);
     for i:=1 to n do
     begin
          read(f,a,b,c);
          d:=cmmdc(a,b);
          if c mod d>0 then writeln(g,'0 0')
          else
          begin
               if a mod b=0 then
               begin
                    u:=0;
                    v:=1;
               end
               else
               if b mod (a mod b)=0 then
               begin
                    u:=1;
                    v:=-(b div(a mod b));
               end
               else
               begin
               m:=2;
               x[1]:=0;y[1]:=1;r[1]:=b;
               x[2]:=1;y[2]:=-a div b;r[2]:=a mod b;
               generalizare;
               u:=x[m-1];
               v:=y[m-1];
               end;
               writeln(g,(c div d)*u,' ',(c div d)*v);
          end;
     end;
     close(f);
     close(g);
end.