记录编号	483838	评测结果	AAAAAAAAAA
题目名称	1265.[NOIP 2012]同余方程	最终得分	100
用户昵称	dishierweidu	是否通过	通过
代码语言	Pascal	运行时间	0.001 s
提交时间	2018-01-19 19:05:38	内存使用	0.15 MiB

program cogs1265;
var 
   a,b,x,y,c:int64;
   
function exgcd(a,b:int64;var x,y:int64):int64;
var 
   tx,ty,t:int64;
begin
   if b=0 then 
     begin
        x:=1;
        y:=0;
        exit(a);
     end
   else 
     begin
        t:=exgcd(b,a mod b,tx,ty);
        x:=ty;
        y:=tx-(a div b)*ty;
        exit(t);
     end;
end;

procedure init;
begin
   assign(input,'mod.in');assign(output,'mod.out');
   reset(input);rewrite(output);
   read(a,b);
   c:=exgcd(a,b,x,y);
   while x<0 do x:=x+b;
   write(x);
end;

procedure cf;
begin
   close(input);close(output);
end;
begin
   init;
   cf;
end.