最大整数扩展欧几里得

时间紧张，先记一笔，后续优化与完善。

辗转相除法求最大公约数，相信大家都在高中学过了，它也叫做欧几里得算法。

那么扩展欧几里得算法呢?它也能求出两个数的最大公约数，不过这不是他的目的，他用来解一个线性方程组

扩展欧几里德定理

对于不完全为 0 的非负整数 a，b，gcd（a，b）表现 a，b 的最大公约数，必然存在整

数对 x，y ，使得 gcd（a，b）=ax+by。

这个方程是建立的，这我们不给予证明，只讲他的求法

根据欧几里得定理 gcd(a,b)=gcd(b,a%b)，代入下面那个线性方程组有gcd(a,b) = a*x1+b*y1 = gcd(b,a%b) = b*x2+(a%b)*y2

即a*x1+b*y1=b*x2+(a%b)*y2

而a%b = a-a/b*b 这里的a/b是盘算机的除法运算也就是结果向下取整。比如9%5 = 9-9/5*5 = 9-1*5=4。

代入上式得 a*x1+b*y1=b*x2+(a-a/b*b)*y2 =>a*x1+b*y1 = a*y2+b(x2-a/b*y2)

下面那个等式很重要，因为这建立了x1 y1 x2 y2之间的联系(可以递归求解方程)

这个关系就是 x1 = y2 y1=x2-a/b*y2; //直接看那个红色的的等式

于是等到递归到b = 0的时候(欧几里得盘算最大公约数就是当b为0的时候，a为最大公约数)

每日一道理
在每个人心中，都曾停留过那些值得怀念的人，也许还在，也许早已消逝，在茫茫人海中丢失，于是，那份怀念便得凄凉，因为模糊的记忆中只剩下一个“空壳”，没有什么，甚至连自己的心都装不下，时间把一切抹平，也把当日的泪水封锁，因为已经没有，怀念只是悲凉！

这时候我们再来看看等式 a*x+b*y = a 这里的b即是0 于是我们可以直接写上一组解(x=1,y=0);

这个时候递归往回走于是解就出来了，到这里我们应当可以看懂模板了

int extend_Eulid(int a,int b,int &x,int &y)  
{  
       if(b == 0)  
      {  
	x = 1;y = 0;
	return a;   
       }  
     else  
      {  
	ans = extend_Eulid(b,a%b,x,y);  
	int temp = x;  
	x = y;  
	y = temp - a/b*y; 
	return ans; 
       }  
}

这只是求出来了一组解，有时候一组解往往不能满意我们，我们需要知道通解。

假设我们求出来的一组解为x0,y0 另外一组解为x1,y1;

显然有a*x0+b*y0 = a*x1+b*y1

变形得a(x0-x1) = b(y1-y0)

方程两边同时除以gcd(a,b) 得a'(x0-x1) = b'(y1-y0)

显然这里a'和b'是互素的(因为他们是a,b除以gcd(a,b)得来的)

那么确定有（x0-x1）是b'的整数倍（因为y1-y0是整数，而a'，b'互素嘛）

我们假设x0-x1 = b*k(k为整数) 于是失掉x0 = x1+b*k

带入到a(x0-x1) = b(y1-y0) 得a*b*k = b(y1-y0) => y0 = y1-a*k