1.欧几里得求gcd

int gcd(int a,int b)
{
      if(b==0) return a;
      return gcd(b,a%b);
}   

2.扩展欧几里得求解线性方程

首先根据Bezout定理，对于任意的a,b:ax+by=gcd(a,b);

然后根据欧几里得求gcd的方法构成等价方程，在递归的同时求出x，y；

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

另外一种写法：(不只是long long 的事情)

void exgcd(long long a,long long b,long long& x,long long& y)
{
	if(!b){
		x=1;y=0;
		return;
	}
	exgcd(b,a%b,x,y);
	long long tmp=x; x=y; y=tmp-a/b*y;
}