INTEGER7 - Số nguyên

Tác giả: RR

Ngôn ngữ: Pascal

{$R+,Q+}
procedure ee(a,b:int64;var x,y:int64);
var
  x2,y2:int64;
begin
  if (a<b) then ee(b,a,y,x)
  else if (b=0) then
    begin
      x:=1;
      y:=0;
    end
  else
    begin
      ee(b,a mod b,x2,y2);
      x:=y2;
      y:=x2-(a div b)*y2;
    end;
end;
function gcd(a,b:int64):int64;
begin
  if (a=0) or (b=0) then exit(a+b)
  else if a<b then exit(gcd(b,a))
  else exit(gcd(b,a mod b));
end;
var
  d,x1,y1,x2,y2,b,a1,b1,a2,b2,k:int64;
begin
  read(a1,b1,a2,b2);
  d:=gcd(a1,a2);
  b:=(b2-b1) div d;
  ee(a1,a2,y1,y2);
  k:=(y2-y1)*b*d div (a1+a2);
  repeat
    dec(k);
  until (y1-y2)*b+k*(a1+a2) div d<0;
  repeat
    inc(k);
  until (y1-y2)*b+k*(a1+a2) div d>=0;
  writeln(y1*b+k*a2 div d,' ',-y2*b+k*a1 div d);
end.

Download