Cod sursa(job #257714)
Utilizator | Data | 13 februarie 2009 20:59:35 | |
---|---|---|---|
Problema | Algoritmul lui Euclid extins | Scor | 100 |
Compilator | fpc | Status | done |
Runda | Arhiva educationala | Marime | 2.41 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.