拓展欧几里德

欧几里得算法

欧几里得算法,也即辗转相除法，可以用来求最大公约数，即gcd(a,b) = gcd(b,a%b)。
代码：

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

拓展欧几里得算法

定理：对于不完全为 0 的非负整数 a，b，gcd（a，b）表示 a，b 的最大公约数，必然存在整数对 x，y ，使得 gcd（a，b）=ax+by。拓展欧几里得就是用来求一个可能的一对数x,y。
原理：
设 a>b。
显然当 b=0，gcd（a，b）=a。此时 x=1，y=0；
当ab!=0 时
设 ax1+by1=gcd(a,b);
bx2+(a mod b)y2=gcd(b,a mod b);
根据朴素的欧几里德原理有 gcd(a,b)=gcd(b,a mod b);
则:ax1+by1=bx2+(a mod b)y2;
即:ax1+by1=bx2+(a-(a/b)*b)y2=ay2+bx2-(a/b)*by2;
根据恒等定理得：x1=y2; y1=x2-(a/b)*y2，可以利用此方法递归求解;
这样我们就得到了求解 x1,y1 的方法：x1，y1 的值基于 x2，y2.
代码：

int exgcd(int a,int b,int&x,int&y)
{
    if(!b)//递归边界，得到最大公约数
    {
        x=1;
        y=0;
        return a;
    }
    int d = exgcd(b,a%b,y,x);//递归求最大公约数
    y-=a/b*x;//迭代，回溯。
    return d;
}