记录编号	483789	评测结果	AAAAAAAAAA
题目名称	[NOIP 2012]同余方程	最终得分	100
用户昵称	李宴彬	是否通过	通过
代码语言	Pascal	运行时间	0.004 s
提交时间	2018-01-19 15:49:24	内存使用	0.17 MiB

program wto;
var 
   a,b,d,x,y: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;
begin
   assign(input,'mod.in');
   reset(input);
   assign(output,'mod.out');
   rewrite(output);
   read(a,b);
   d:=exgcd(a,b,x,y);
   while(x<0) do inc(x,b);
   writeln(x);
   close(input);
   close(output);
end.