欧几里得算法就是我们常说的辗转相除法，辗转相除法可以用来求最大公约数，知道最大公约数还可以求最小公倍数。gcd在好像也有库函数__gcd

int Gcd(int a, int b){    while(b != 0)    {    　　int r = b;    　　b = a % b;    　　a = r;    }    return a;}

int gcd(int a,int b){
     return b ? gcd(b,a%b) : a;}

扩展欧几里得算法是在解决一个什么问题呢，解方程，解二元一次方程的通解。

扩展欧几里得算法是欧几里得算法（又叫辗转相除法）的扩展。除了计算a、b两个整数的最大公约数，此算法还能找到整数x、y（其中一个很可能是负数）。通常谈到最大公因子时, 我们都会提到一个非常基本的事实: 给予二整数 a 与 b, 必存在有整数 x 与 y 使得ax + by = gcd(a,b)。有两个数a,b，对它们进行辗转相除法，可得它们的最大公约数——这是众所周知的。然后，收集辗转相除法中产生的式子，倒回去，可以得到ax+by=gcd(a,b)的整数解。by百度百科

int exgcd(int a,int b,int &x,int &y){    if(b==0)    {        x=1;        y=0;        return a;    }    int r=exgcd(b,a%b,x,y);    int t=x;    x=y;    y=t-a/b*y;    return r;}

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;}

扩展欧几里德算法的应用主要有以下三方面：

（1）求解不定方程；

（2）求解模线性方程（线性同余方程）；

（3）求解模的逆元；

模逆元的代码，当时用来加AA小姐接的QQ

#include 
     
      __int64 la(__int64 a,__int64 b,__int64 &x,__int64 &y){    __int64 d;    if(!b){        x=1;y=0;return a;    }    d=la(b,a%b,y,x);    y-=a/b*x;    return d;    }__int64  Inv(__int64 a,__int64 n){    __int64 d,x,y;    d=la(a,n,x,y);    if(d==1)    return (x%n+n)%n;    else    return -1;}int main(){   __int64 a,n;    scanf("%I64d%I64d",&a,&n);    printf("%I64d",Inv(a,n));        return 0;}