Cod sursa(job #250614)

Utilizator MihaiBunBunget Mihai MihaiBun Data 31 ianuarie 2009 12:38:34
Problema Algoritmul lui Euclid extins Scor 100
Compilator fpc Status done
Runda Arhiva educationala Marime 2.13 kb
program eucl;
var f,g:text;
t,i,a,b,a1,a2,b1,b2,u,v,x,y,c,r,x0,y0:longint;
begin
  assign(f,'euclid3.in');
  assign(g,'euclid3.out');
  rewrite(g);
  reset(f);
  readln(f,t);
  for i:=1 to t do
   begin
     readln(f,a,b,c);
     if (a=0)and(b=0) then writeln(g,0,' ',0)
     else if (a=0)and(b<>0) then if c mod b=0 then writeln(g,0,' ',c div b)
                                              else writeln(g,0,' ',0)
                            else if (a<>0)and(b=0) then
                                    if c mod a=0 then writeln(g,c div a,' ',0)
                                                 else writeln(g,0,' ',0)
                                                   else begin
     a1:=abs(a);
     b1:=abs(b);
     r:=a1 mod b1;
     while r<>0 do
       begin
         a1:=b1;
         b1:=r;
         r:=a1 mod b1
       end;
     if abs(c) mod b1<>0 then writeln(g,0,' ',0)
                    else begin
                             a2:=abs(a) div b1;
                             if c>0 then c:=c div b1
                                    else c:=-(abs(c) div b1);
                             b2:=abs(b) div b1;
                             r:=a2 mod b2;
                             x0:=0;y0:=1;
                             x:=1;y:=-(a2 div b2);
                             while r<>0 do
                               begin
                                 a2:=b2;
                                 b2:=r;
                                 r:=a2 mod b2;
                                 u:=x;v:=y;
                                 x:=x0-(a2 div b2)*x;
                                 y:=y0-(a2 div b2)*y;
                                 x0:=u;y0:=v
                               end;
                                if (a>0)and(b>0) then writeln(g,x0*c,' ',y0*c);
                                if (a>0)and(b<0) then writeln(g,x0*c,' ',-y0*c);
                                if (a<0)and(b>0) then writeln(g,-x0*c,' ',y0*c);
                                if (a<0) and(b<0) then writeln(g,-x0*c,' ',-y0*c);
                          end
                         end;
   end;
close(f);
close(g);
end.