NOIP 2012 同余方程

依据gcd(a,b)=gcd(b,a mod b);

设ax1+by1=gcd(a,b)=1

则bx2+(a mod b)y2=gcd(b,a mod b);

ax1+by1=bx2+(a mod b)y2;

ax1+by1=bx2+(a-[a/b]*b)y2=ay2+bx2-(a/b)*by2;

根据恒等定理得：x1=y2; y1=x2-[a/b]*y2;

 1 var a,b,x,y:longint;
 2 procedure gcd(a,b:longint);
 3       var t:longint;
 4 begin
 5   if b=0 then
 6    begin
 7     x:=1;
 8     y:=0;
 9     exit;
10    end else
11    begin
12     gcd(b,a mod b);
13     t:=x;
14     x:=y;
15     y:=t-(a div b)*y;
16    end;
17 end;
18 
19 begin
20  assign(input,'mod.in'); reset(input);
21  assign(output,'mod.out'); rewrite(output);
22  readln(a,b);
23  gcd(a,b);
24  while x<0 do x:=(x+b) mod b;
25  write(x);
26  close(input); close(Output);
27 end.

View Code