欧几里得算法 最大公约数欧几里得算法

欧几里得算法：辗转相除法，用来求两个数的最大公约数。【在数学里面最大公约数是没有负的定义的，所以负数是不谈最大公约数的】

它是个递归算法，gcd(a,b)=gcd(b,a%b)。

证明：设a=x*b+r，设d为a，b的最大公约数，d|a，d|b，可得d|r，那么a%b=r，也就是gcd(a,b)=gcd(b,a%b)。

具体代码：

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

重点是扩展欧几里得和贝祖公式。

贝祖公式告诉我们:a*x+b*y=gcd(a,b)，【x,y为一组正整数】。

那么当我们要求a*m+b*n=q时，如果q%gcd(a,b)！=0【q%gcd(a,n)！=0，q%gcd(m,b)！=0，q%gcd(m,n)！=0，其实都要满足，但是一般题目不会给你那么多已知量】，那么此方程无解。反之有无数组解【二元一次方程，要么无解，要么有无数组解】。

我们来一遍推导：

首先，gcd(a,b)=gcd(b,a%b)。 gcd(a,b)=a*x1+b*y1，

那么很容易推导出gcd(b,a%b)=b*x2+(a-a/b*b)*y2【此处为整除】，

按照a和b整理一下得到，a*x1=a*y2，b*y1=b*(x2-a/b*y2)。所以，x1=y2，y1=x2-a/b*y2。

我们可以通过递归过程和引用将结果返回。

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

关于扩展欧几里得，还有个比较重要的东西，我们可以通过这个简单的得到一组x,y使得a*x+b*y=gcd(a,b)或者是a*x+b*y=c【可以判断有无解或者得到一组解】

但是刚刚也说了，二元一次方程如果有解是无数组的，那么如何通过这一组特解得到他们的通解呢。

设特解为x0,y0,通解为x0+m,y0+n。

a*x0+b*y0=gcd(a,b)。

也就是说我们需要求出a*m+b*n=0。a*b/gcd(a,b)=b*a/gcd(a,b)，

所以我们可以令m=b/gcd(a,b)*t，n=-a/gcd(a,b)*t。于是通解可以表示为x=x0+b/gcd(a,b)*t，y=y0-a/gcd(a,b)*t。

在计算机中，负数mod正数，如果负数可以整除这个正数，返回0，否则就反悔满足同余的情况下的最大负数。所以说如果要求最小的非负x，

如果x>=0，那么直接x%(b/gcd(a,b))。

如果x<0，那么应该用x%(b/gcd(a,b))，得到满足同余的最大负数后，再加上b/gcd(a,b)得到最小正数解。也就是x%(b/gcd(a,b))+(b/gcd(a,b))