扩展欧几里得（exgcd）

这里先说一下最大公约数怎么求，辗转相除法都会用，这里讲一下站桩相除法的原理。
例如两个数假设这两个数大小，设是这两个数的最大公约数。
可得
因为这里都是一个正整数不会对最大公因子造成影响所以相等。即
如果的时候说明b可以被整除，最大公因子就是。

Code：

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

接下来就是扩展欧几里得
设和都是正整数我们会得到一个式子
如果我们要求得这个式子的值，这个值是非常多的，但是最小值只有一个那就是即： 即如果是整数，那么一定存在整数使得。这个式子是怎么推的，我们可以使用逆推的方式。假设这个式子成立。
由上面推导最大公因子的过程可知，
设

当 时，
贝祖等式即 ，解得 可以取

当时，
假设假设 的贝祖等式的解为即：

1. 
2. 
   由上面的推理我们可知：
   所以：
   即：
   注：
   
   可得恒等式：

即贝祖等式 1 的解可以由 贝祖等式 2 的解得到，这是一个递归求解的过程，并且随着对 进行辗转相除，贝祖等式的系数会越来越小，直至变为情况，而情况1贝祖等式的解是有具体的值的，
即 。然后进行回溯计算，最终可以得到。

Code：

ll exgcd(int a,int b,int &x,int &y)
{
    if(b==0)
    {
        x=1;
        y=0;
        return a;
    }
    int g=exgcd(b,a%b,x,y);
    int t=x;
    x=y;
    y=t-a/b*y;
    return g;
}