欧几里得算法和扩展欧几里得算法

当时学gcd的时候学长没解释,说句实话,要是我是学长,首先得教学弟栈和队列,然后再教迷宫,最后教递归.不然怎么看的懂gcd的代码哎...确实浪费了半年在学校.下面是gcd的讲解.

/*
求两个数的gcd,首先得知道 if(d|a&&d|b),那么d|(a+b)也可以d|(n*a+m*b).因为都可以提取出一个d的倍数呐~
gcd的写法就是说,我们每次把a当成大的,把b当成小的,我们就可以通过把大的变小来求最大公约数了.至于变小就是拿(a,b)->(b,a%b).上面证明了.
递归出口就是当b＝0了,那么a就是最大公约数了,我们无法再将a变小了,以及a%b==0了,那么a就是最小公倍数了.
*/
int gcd(int a,int b)
{
    return b==0?a:gcd(b,a%b);
}

下面讲下ex_gcd.ex_gcd就是求出一组解使得ax+b*y=gcd(a,b).由gcd的原理,当递归到最后,存在x=1,y=0使得gcd(a,b)成立,但是此时的a,b已经不是a,b的初始值了.我们来推一下相邻的两步关系.
下一步的b(x1)+(a%b)(y1)=gcd(a,b).a%b=a-(a/b)b.bx1+(a-(a/b)b)y1=gcd(a,b).然后把a,b项合并.
a*y1+b(x1-a/by1).那么我们发现x=y1,y=(x1-a/by1).然后进行递归即可.

int x,y;
void ex_gcd(int a,int b)
{
    if(b==0)
    {
        x=1,y=0;
        return;
    }
    ex_gcd(b,a%b);
    int cx=x,cy=y;
    x=cy,y=(cx-a/b*cy);
}