Cod sursa(job #294966)

Utilizator mimarcelMoldovan Marcel mimarcel Data 2 aprilie 2009 21:22:39
Problema Algoritmul lui Euclid extins Scor 100
Compilator fpc Status done
Runda Arhiva educationala Marime 1.19 kb
Program Algoritmul_lui_Euclid_extins;
type semn=(nedeterminat,minus,plus);
var t,i:byte;
	 a,b,c,d,x,y:longint;
	 semnx:semn;

function cmmdc(a,b:longint):longint;
var r:longint;
begin
while b<>0 do
  begin
  r:=a mod b;
  a:=b;
  b:=r;
  end;
cmmdc:=a;
end;

begin
assign(input,'euclid3.in');
reset(input);
assign(output,'euclid3.out');
rewrite(output);
readln(t);
for i:=1 to t do
  begin
  readln(a,b,c);
  if a=0 then begin
				  if b=0 then writeln('1 1')
							else if c mod b=0 then writeln('1 ',c div b)
													else writeln('0 0');
				  continue;
				  end
			else if b=0 then begin
								  if c mod a=0 then writeln(c div a,' 1')
													else writeln('0 0');
								  continue;
								  end;
  d:=cmmdc(a,b);
  if c mod d<>0 then writeln('0 0')
					 else
	 begin
	 a:=a div d;
	 b:=b div d;
	 c:=c div d;
	 x:=0;
	 semnx:=nedeterminat;
	 while semnx=nedeterminat do
		begin
		inc(x);
		if(c-a*x)mod b=0 then semnx:=plus
							  else if (c-a*(-x))mod b=0 then semnx:=minus;
		end;
	 if semnx=minus then x:=-x;
	 y:=(c-a*x)div b;
	 writeln(x,' ',y);
	 end;
  end;
close(input);
close(output);
end. {nimeni nu vede ce am scris aici}