欧几里得 1.含义：欧几里德算法又称辗转相除法，用于计算两个整数a,b的最大公约数。 原理公式：gcd(a,b)=gcd(b,a mod b) 因此(a,b)和(b,a mod b)的公约数是一样的，其最大公约数也必然相等. 2.实现： int gcd(int a,int b) { return b?gcd(b,a%b):a; }   扩展欧几里得   1. 含义：对于不完全为 0 的非负整数 a，b，gcd（a，b）表示a，b 的最大公约数，必然存在整数对 x，y ，使得 gcd（a，b）=ax+by。 2.结果：得到（a,b）最大公约数d，同时得到一组 整数解x、y。 3.实现： （递归） int exgcd(int a,int b,int &x,int &y) { if(b==0) { x=1; y=0; return a; } int d=exgcd(b,a%b,x,y); int temp=x; x=y; y=temp-a/b*y; return d; } （迭代） int exgcd(int m,int n,int &x,int &y) { int x1,y1,x0,y0; x0=1; y0=0; x1=0; y1=1; x=0; y=1; int r=m%n; int q=(m-r)/n; while(r) { x=x0-q*x1; y=y0-q*y1; x0=x1; y0=y1; x1=x; y1=y; m=n; n=r; r=m%n; q=(m-r)/n; } return n; } 4.应用 <1>求解不定方程 形如：ax+by=c      a、b、c已知，求一组 整数x、y使得方程成立。 解：由上述<实现>代码可得  最大公约数d=gcd（a，b）、一组x0、y0；（此x、y是方程ax+by=gcd（a，b）的解） ①方程ax+by=gcd（a，b） 的通解：x=x0+b/d*k；y=y0-a/d*k ; （k为任意常数，下同） ②方程ax+by=c的通解：x=x0*c/d+b/d*k ;  y=y0*c/d-a/d*k ; 另：判断是否有解的方法  ：  c%d=0 则有解，否则反之。 <2>求解模线性方程 模线性方程 ： ax≡b(mod m)      其中a,b和m是已知的（m>0），要求解出满足上式的对模m的x值。满足同余方程的x可能有多个，也可能一个都没有，上述模线性方程也称为一次同余方程。     解：模线性方程ax≡b(mod m)的步骤如下： （1）求 d=gcd（a,m） （2）若d%b！=0，则ax≡b(mod m)无解；否则有解（且有d个解） （3）求x0,y0,是a*x0+m*y0=d; （4）由于d是b的因数，将a*x0+m*y0=d改写，得a(x0*(b/d))+m*(y0*(b/d))=b,           于是ax+my=b的一个特解为 x=x0*(b/d),y=y0*(b/d); （5）x0*(b/d)是ax≡（mod m）的一个特解，由此的ax≡b(mod m)的所有解        （共d个）为：x= (x0*(b/d)+ i*(m/d) ) (mod m),    i=0,1,2,3,4.……d-1 <3>用欧几里德算法求模的逆元：        同余方程ax≡b (mod n)，如果 gcd(a,n)== 1，则方程只有唯一解。       在这种情况下，如果 b== 1，同余方程就是 ax=1 (mod n ),gcd(a,n)= 1。       这时称求出的 x 为 a 的对模 n 乘法的逆元。       对于同余方程 ax= 1(mod n )， gcd(a,n)= 1 的求解就是求解方程       ax+ ny= 1，x, y 为整数。这个可用扩展欧几里德算法求出，原同余方程的唯一解就是用扩展欧几里德算法得出的 x 。