Cod sursa(job #226194)

Utilizator johnyJohny Deep johny Data 1 decembrie 2008 10:23:35
Problema Algoritmul lui Euclid extins Scor 70
Compilator fpc Status done
Runda Arhiva educationala Marime 1.03 kb
program tema;
var a,b,c,d: longint;
    x,y: longint;
    i,n: longint;

function ext_euclid(a,b:longint;var lx,ly:longint):longint;
var x,y,q,t: longint;
begin
  x:=0;  lx:=1;
  y:=1; ly:=0;
  while b<>0 do
  begin
    t:=b;
    q:=a div b;
    b:=a mod b;
    a:=t;

    t:=x;
    x:=lx-q*x;
    lx:=t;

    t:=y;
    y:=ly-q*y;
    ly:=t;
  end;
  ext_euclid:=a;
end;

function rec_euclid(a,b:longint; var x,y:longint):longint;
var t: longint;
begin
  if b=0 then
  begin
    x:=1; y:=0;
    rec_euclid:=a;
  end
  else
  begin
    rec_euclid:=rec_euclid(b,a mod b,x,y);
    t:=x;
    x:=y;
    y:=t-y*(a div b);
  end;
end;

begin
  assign(input,'euclid3.in');
  reset(input);
  assign(output,'euclid3.out');
  rewrite(output);
  readln(n);
  for i:=1 to n do
  begin
    readln(a,b,c);
    d:=rec_euclid(a,b,x,y);
    if c mod d>0 then
       writeln(0,' ',0)
    else
       writeln(x*(c div d),' ',y*(c div d));
       {writeln(a*x+b*y);}

  end;
  close(input);
  close(output);
end.