gcd的递归写法

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

根据贝祖定理如果a、b是整数，那么一定存在整数x、y使得ax+by=gcd(a,b)。

换句话说，如果ax+by=m有解，那么m一定是gcd(a,b)的若干倍。（可以来判断一个这样的式子有没有解）

有一个直接的应用就是 如果ax+by=1有解，那么gcd(a,b)=1；

扩展欧几里得就是用来求这个式子中的 x ，和 y 的。再所有解中有一组特殊的解x0，y0
$x = x_0 + (b/gcd)*t$

$y = y_0 – (a/gcd)*t$
根据这个特殊解可以求出所有的通解

不是如下这个式子的原因很简单，因为上式比下式包含的范围更大一些，而且是这些范围里面最大的，因为b/gcd,和a/gcd是互质的因此所包含的范围是最大的

$x = x_0 + b*t$

$ y = y_0 – a*t $

对于x0，y0可以在求解gcd的时候顺便求出

我们知道： $a%b = a - (a/b)*b$（这里的 “/” 指的是整除，例如 5/2=2 , 1/3=0），那么，我们可以进一步得到：

$ gcd = b\*x_1 + (a-(a/b)\*b)\*y_1 $

$ = b\*x_1 + a\*y_1 – (a/b)\*b\*y_1$

$ = a\*y_1 + b\*(x_1 – a/b\*y_1) $

随后可得:

$x = y_1$

$y = x_1 – a/b\*y_1$

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的最大公因数
}

参考：
1> https://blog.csdn.net/destiny1507/article/details/81750874?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522163661339416780264021809%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=163661339416780264021809&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~top_positive~default-1-81750874.first_rank_v2_pc_rank_v29&utm_term=%E6%89%A9%E5%B1%95%E6%AC%A7%E5%87%A0%E9%87%8C%E5%BE%97&spm=1018.2226.3001.4187
2> https://blog.csdn.net/zhjchengfeng5/article/details/7786595?ops_request_misc=&request_id=&biz_id=102&utm_term=%E6%89%A9%E5%B1%95%E6%AC%A7%E5%87%A0%E9%87%8C%E5%BE%97&utm_medium=distribute.pc_search_result.none-task-blog-2~all~sobaiduweb~default-0-7786595.nonecase&spm=1018.2226.3001.4187