什么是扩展欧几里得算法？
exgcd适用于处理一次不定方程的一个算法，可以求出不定方程的一组特解
例如可以用于求解：ax+by=k。给定a，b，k的值，便可以求出一组x，y的解
算法的实现
在exgcd中，我们实际是求不定方程ax+by=gcd(a,b)，并且，我们所返回的值，是这组解（x，y）的最大公因数（gcd(x,y)）。
所以我们最后得到的解，要通过X=x?k/gcd(a,b)，Y=(k?a?x)/gcd(a,b)来进行一个小小的转换，得到一组解
下面对算法实现过程给出一个证明
我们通过递归，就可以得到一组特解
给出模板
ll Exgcd(ll a, ll b, ll &x, ll &y) {if (!b) {x = 1;y = 0;return a;}ll d = Exgcd(b, a % b, x, y);ll t = x;x = y;y = t - (a / b) * y;return d;
}