POJ 1061(exgcd)

内容目录

这题是exgcd……

我居然连wa了2天……

至少知道DIV函数的性质了   (-x) div t =-(x div t)    

                           (-x) div (-t) = (x div t)

发现自己数论蒟蒻……

Program p1061;
var
   x,y,n,m,l,t:int64;
   a,b,c,c2:int64;
function exgcd(a,b:int64):int64;
var
   x1,y1:longint;
begin
   if b=0 then
   begin
      x:=1;
      y:=0;
      exit(a);
   end;
   exgcd:=exgcd(b,a mod b);
   x1:=y;
   y1:=x-(a div b)*y;
   x:=x1;
   y:=y1;
end;
begin

   read(x,y,m,n,l);
   a:=n-m;
   c:=x-y;
   b:=l;
   c2:=exgcd(a,b);
   if (c mod c2<>0) then writeln('Impossible')
   else
   begin
      x:=x*(c div c2);
      y:=y*(c div c2);
      t:=b div c2;


      if t<0 then
         while (x<0) do
         begin

            x:=x-t*abs(x div t)-t;
         end;
      if t>0 then while (x<0) do x:=x+t*abs(x div t)+t;

      x:=x mod (b div c2);
      writeln(x);
   end;


end.