扩展欧几里得 exgcd

•扩展欧几里德算法是用来在已知a, b求解一组x，y，使它们满足贝祖等式： ax+by = gcd(a, b) = d（解一定存在，根据数论中的相关定理）。扩展欧几里德常用在求解模线性方程及方程组中。

 

•设 a>b。

•1，显然当 b=0，gcd（a，b）=a。此时 x=1，y=0；

•2，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;

•也就是ax1+by1==ay2+b(x2-[a/b]*y2);

•根据恒等定理得：x1=y2; y1=x2-[a/b]*y2;

•这样我们就得到了求解 x1,y1 的方法：x1，y1 的值基于 x2，y2.

•上面的思想是以递归定义的，因为 gcd 不断的递归求解一定会有个时候 b=0，所以递归可以结束。

 

代码：

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