广义欧几里得除法：(求最大公因数)

欧几里得的定理： gcd(a, b) = gcd(b , a%b)

int gcd(int a,int b)
{
    if(b==0) return a;//出口
    else   return gcd(b,a%b);
}

扩展欧几里得算法:(求sa+tb=(a,b)中s和t)

ax+by==gcd(a,b) (解一定存在，根据数论中的相关定理）

下面我们来证明ta:

(1)...ax+by==gcd(a,b);

(2)...bx1+a%by1==gcd(b,a%b);  (运用欧几里算法)

(3)...gcd(a,b)==gcd(b,a%b);  (欧几里得算法)

(4)...ax+by==bx1+a%b*y1;  (在计算机里a%b==(a-a/b*b))

(5)...ax+by==bx1+ay1-a/b*by1;

(6)...ax+by==ay1+b(x1-a/b)y1;  (合并同类项)

(7)...x==y1,y==x1-a/b*y1;  (结论)
所以我们知道x,y和方程的下一个状态量(x1,y1)有关
而方程最后一个状态（即gcd(a,b)终点，b==0）此时：
ax+0==a;  (gcd(a,b)的最终返回值为a)  可以得到一组解{x==1; y==0}，根据此解层层回溯即可得到最开始的x,y.

int exgcd(int a,int b,int &x,int &y)//扩展欧几里得算法
{
    if(b==0)
    {
        x=1;y=0;
        return a;  //到达递归边界开始向上一层返回
    }
    int r=exgcd(b,a%b,x,y);
    int temp=y;    //把x y变成上一层的
    y=x-(a/b)*y;
    x=temp;
    return r;     //得到a b的最大公因数
}

(1613,3589)
广义欧几里得除法
3589=2*1613+363
1613=4*363+161
363=2*161+41
161=3*41+38
41=1*38+3
38=12*3+2
3=1*2+1
2=1*2+0

扩展欧几里得算法:
1=3-1*2
=3-1*(38-12*3)
=13*(41-38)-38
=13*41-14*38
=13*41-14*(161-3*41)
=-14*161+55*41
=-14*161+55*(363-2*161)
=-124*161+55*363
=-124*(1613-4*363)+55*363
=-124*1613+551*363
=-124*1613+551*(3589-2*1613)
=-1226*1613+551*3589

∴s=-1226,t=551

例题：

image.png

#include<stdio.h>
int main()
{
    int a,b,s,t,gcd;
    int exgcd(int a,int b,int *x,int *y);
    while(scanf("%d%d",&a,&b)!=EOF)
    {
        gcd=exgcd(a,b,&s,&t);
        printf("%d %d\n",s,t);
    }
    return 0;
}
int exgcd(int a,int b,int *x,int *y)//扩展欧几里得算法;
{
    if(b==0)
    {
        *x=1;
        *y=0;
        return a;
    }
    int ret=exgcd(b,a%b,x,y);
    int t=*x;
    *x=*y;
    *y=t-a/b*(*y);
    return ret;
}

参考文章：
1.https://blog.csdn.net/zhjchengfeng5/article/details/7786595
2.https://blog.csdn.net/AAMahone/article/details/79320635